Consider a directed graph $D(n)$ whose vertex set $V$ consists of the integers $1,2,\dots,n$, and whose edge set $E$ consists of ordered pairs of integers $(i,j)$ whenever $i < j$. In other words, there is a directed edge from $i$ to $j$ if and only if $i < j$. For example, the figure below shows $D(5).$
a. In $D(n)$, a path from $1$ to $n$ is described by a sequence of vertices $v1,v2,...,v_k$ where $v_1= 1$, $v_i< v_{i+1}$ for $i = 1,\dots,k − 1$, and $v_k= n$. For $D(5)$ above, please list all the paths from $1$ to $5$. (There should be $8$ of them.)
b. Suppose $P = v_1,v_2,\dots,v_k$ is a $1$-to-$n$ path in $D(n)$. Let $f(P) = \{v2,\dots,v_{k−1}\}$. For example, for $D(5)$, $f(1,2,4,5) = \{2,4\}$. Please explain why $f$ is one-to-one.
c. Next, explain why $f$ is onto.
d. From b and c, we conclude that $f$ is a bijection. What then does this imply about the number of $1$-to-$n$ paths in $D(n)$? (Note: your answer here should be a generalization of your answer in (a).)
Any ideas or hint or ... ?