Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following figure depicts the paths from home to work. SAM never travels through the park when going to work.

enter image description here

share|improve this question
manual counting gives 8 ways. Is there a mathematical process which can give the answer without manual counting. –  Rajesh K Singh Feb 5 '13 at 16:11
Counting is a mathematical process. –  Henning Makholm Feb 5 '13 at 16:28

3 Answers 3

up vote 2 down vote accepted

He has to pass through exactly one of E, F, and C. If he passes through E or C then there's trivially only one path (for each) he can take. If he passes through F, there are $\binom{2}{1} = 2$ ways he can get from A to F and $\binom{3}{2} = 3$ ways he can get from F to K, for a total of $2\times 3 = 6$. So in all there are $1+1+6 = 8$ ways he can get home.

share|improve this answer

Write the number of possibilities of reaching a vertex $X$ from $A$. It starts like $A:1$ as getting to $A$ is unique, both $B$ and $D$ also have only $1$ possibilities. They simply add up, for example the possibilities to arrive at $I$ are the possibilities arriving at either to $H$ or to $G$ (plus the unique $GI$ path, resp. $HI$ path). $$A:1,\ B:1,\ D:1,\ F:2,\ E:1,\ G:3,\ H:2,\ I:5,\ C:1,\ J:3,\ K:8 $$

share|improve this answer

If the park were not there, there would be ${3+2 \choose 2}=10$ possible paths.

Adding the park cuts off one possible line segment Sam could walk along (from the $BC$ midpoint to $H$). There is only one way he could get to the top of that line segment, and $2$ possible continuances once he reaches $H$. So the total number of paths that don't go through the park is $10 - 1 \cdot 2 = 8$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.