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).$

enter image description here

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 ... ?


The map $f$ that you need for (b)-(d) is poorly explained, since the problem does not say what its codomain is. I’ll expand on the definition a bit.

Let $P$ be the set of paths from $1$ to $n$ in $D_n$. Let $Q$ be the set of all paths, including the empty path, in the subgraph of $D_n$ induced by the vertices $\{2,\dots,n-1\}$. For any path $$\langle 1=v_1,v_2,\dots,v_{k-1},v_k=n\rangle\in P$$ let $f\big(\langle 1,v_2,\dots,v_{k-1},n\rangle\big)=\langle v_2,\dots,v_{k-1}\rangle\in Q$.

Example: In $D_5$ the sets $P$ and $Q$ contain the following paths:

$$\begin{array}{l|l} P&Q\\ \hline \langle 1,5\rangle&\varnothing\\ \langle 1,2,5\rangle&\langle 2\rangle\\ \langle 1,3,5\rangle&\langle 3\rangle\\ \langle 1,4,5\rangle&\langle 4\rangle\\ \langle 1,2,3,5\rangle&\langle 2,3\rangle\\ \langle 1,2,4,5\rangle&\langle 2,4\rangle\\ \langle 1,3,4,5\rangle&\langle 3,4\rangle\\ \langle 1,2,3,4,5\rangle&\langle 2,3,4\rangle \end{array}$$

The first column of this table actually answers (a). Parts (b) and (c) are very straightforward, especially if you realize that a path in $D_n$ is completely determined by the set of vertices: if we have the set, we can always order it correctly. Thus, $P$ corresponds in a straightforward way to the subsets of $\{1,\dots,n\}$ that contain both $1$ and $n$, and $Q$ corresponds in an equally straightforward way to the subsets of $\{1,\dots,n\}$ that contain neither of $1$ and $n$.

For (d) they want you to use to use the fact that $P$ and $Q$ have the same cardinality, since there is a bijection between them, and to notice that $|Q|$ is very easy to calculate. If you have trouble here, try counting by hand the paths from $1$ to $n$ in $D_n$ for $n=1,2,3,4,5$; if you do it right, you’ll see a pretty obvious pattern.


I'll leave (a) to you.

For (b) and (c), note that a path from $1$ to $n$ will always start at $1$ and end at $n$, so paths determine, and are uniquely determined by, the set of intermediate vertices on the path. Note that in (c), I'm assuming the codomain is the set of all subsets of $\{2,...,n-1\}$.

For (d), since a path is uniquely determined by the set of intermediate vertices on the path, of which there are $n-2$ (for $n\geq 2$), then there are $2^{n-2}$ possible paths from $1$ to $n$ for $n\ge2$. Of course, for $n=1$, there's only one path, but that's the only one that doesn't really fit the pattern. I suppose that you could say that there are $\left\lceil 2^{n-2}\right\rceil$ paths from $1$ to $n$ possible, if you wanted it to hold for all $n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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