#Combinatorics

Question

 

Comments

Its dynamic programming, i am getting 33.

---

from where you got this question ?

---

This question might be from Test book test series.

Answer 1

The $2^{nd}$ last nodes before $I$ are $F$ , $H$ and $E$.

Through F ,1 way $F\rightarrow I$

Through H, 2 ways $H\rightarrow I$  or  $H\rightarrow F\rightarrow I$.

Through E, 5 ways.

1. $ E\rightarrow C\rightarrow F\rightarrow I$ and from F its 1 way.
2. $ E\rightarrow H $ and from H its 2 ways.
3. $ E\rightarrow F $ and from F its 1 way.
4. $E\rightarrow I$  1 way

----------------------------------------------------------------------------------------------------------------------

Now lets fix the $1^{st}$ and $2^{nd}$ node from the beginning and see all the cases possible.

1.  A $\rightarrow$ B ..... I ( keeping A $\rightarrow $ B fixed )
   1. A $\rightarrow $ B $\rightarrow $ F ....I  => 1 way.
   2. A $\rightarrow $ B $\rightarrow $ E .... I  => 5 ways.
   3. A $\rightarrow $ B $\rightarrow $ C .... I  => 1 way.
   $\therefore$ 7 ways keeping A $\rightarrow $ B fixed.
2. A $\rightarrow$ E ..... I  ( keeping A $\rightarrow $ E fixed. )
   $\therefore$ 5 ways keeping A $\rightarrow $ E fixed.
3. A $\rightarrow$ D ..... I  ( keeping A $\rightarrow $ D fixed. )
   1. A $\rightarrow $ D $\rightarrow $ E ....I  => 5 ways.
   2. A $\rightarrow $ D $\rightarrow $ H ....I  => 2 ways.
   3. A $\rightarrow $ D $\rightarrow $ B ....I  => 7 ways.
   4. A $\rightarrow $ D $\rightarrow $ G ....I
      1.  G $\rightarrow $ E .... I => 5 ways.
      2.  G $\rightarrow $ H....I  => 2 ways.
   $\therefore$ 5+2+7+5+2 = 21 ways keeping A $\rightarrow $ D fixed.

----------------------------------------------------------------------------------------------------------------------

$\therefore$ Total number of paths possible from A $\rightarrow $.....I $=  7+5+21 = 33 $