Question 61
Consider the following diagram:
Augusto likes counting paths that start at a point, end at $A$, and never visit a vertex twice. He represents a path by the sequence of points it visits. For example, the dotted path below is represented by $DCBA$.
He calls a path unusual if its sequence is in decreasing alphabetical order; equivalently, it never moves left, whether upward or downward. Thus $DCBA$ is unusual. The path $DBCA$ is not unusual, since, as the source states, the letter $C$ appears before $B$.
(a) How many unusual paths start at $D$ and end at $A$?
(b) Show that the number starting at $E$ is the sum of the numbers starting at $D$ and at $C$.
(c) Augusto calculated the number from $K$ to $A$. What is it?
Augusto likes counting paths that start at a point, end at $A$, and never visit a vertex twice. He represents a path by the sequence of points it visits. For example, the dotted path below is represented by $DCBA$.
He calls a path unusual if its sequence is in decreasing alphabetical order; equivalently, it never moves left, whether upward or downward. Thus $DCBA$ is unusual. The path $DBCA$ is not unusual, since, as the source states, the letter $C$ appears before $B$.
(a) How many unusual paths start at $D$ and end at $A$?
(b) Show that the number starting at $E$ is the sum of the numbers starting at $D$ and at $C$.
(c) Augusto calculated the number from $K$ to $A$. What is it?