See the diagram below, where we start at $A$ and we\u2019d like to get to $B$. In this version, Since we can only walk along roads, we must move East a total of $M$ times and north a total of $N$ times to arrive at our destination. This means we must walk $M+N$ blocks to get to work. Backtracking (moving south or west) will necessarily lead to paths that are longer than necessary, so we can exclude these cases.<\/p>\n

Each path from A to B is a sequence of $M$ \u201ceasts\u201d and $N$ \u201cnorths\u201d in some order. In the example above, $M=4$ and $N=3$. The solution I traced is:
\n\\[
\n\\{\\text{east, east, north, north, east, north, east}\\}
\n\\]Here is another way to think about the problem: out of the $M+N$ decisions we must sequentially make (moving east or moving north), which $M$ of them will be \u201ceast\u201d? The answer is the binomial coefficient<\/a>!<\/p>\n

$\\displaystyle
\n\\text{Ways to work} = \\binom{M+N}{M} = \\frac{(M+N)!}{M!\\cdot N!}
\n$<\/span><\/p>\n

To answer the specific problem posed with $M=5$ and $N=10$, the number of different paths from $A$ to $B$ is $3003$.<\/p>\n<\/div>\n

<\/p>\n<\/body>","protected":false},"excerpt":{"rendered":"

This Riddler puzzle is a classic problem: how many lattice paths connect two points on a grid? Here is a paraphrased version of the problem. The streets of Riddler City are laid out in a perfect grid. You walk to work each morning and back home each evening. Restless and inquisitive mathematician that you are, … Continue reading “Paths to work”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2448,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[9,29,2],"class_list":["post-2445","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-binomial","tag-classics","tag-riddler"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t