Introduction

This blog is inspired by this blog, which is an interesting constructive problem:

• How to construct a DAG with no multiple edges, such that there exists exactly $$$k$$$ distinct paths from vertex $$$1$$$ to $$$n$$$?

Obviously, there is a trivial solution which requires $$$2k$$$ edges and $$$k+2$$$ vertices. Simply connect vertex $$$1$$$ to each vertex numbered from $$$2$$$ to $$$k+1$$$, then connect each of these vertices to vertex $$$k+2$$$. In this blog, we shall discuss how to minimise the number of edges used.

Using no more than $$$4 \log k+1$$$ edges

This is likely to be the first way that many people will approach this problem. Consider the following structure:

There are exactly $$$2$$$ distinct paths from $$$1$$$ to $$$3$$$. If we chain them together as such:

There will be $$$2^3=8$$$ distinct paths from $$$1$$$ to $$$7$$$. We can see that it is possible to create $$$2^m$$$ paths using $$$3m$$$ edges.

For simplicity, we will call the chain $$$1 \to 3 \to 5 \to 7 \to \dots$$$ as the backbone, and $$$v_i$$$ to be the $$$i$$$-th vertex from $$$1$$$ on the backbone. For example, $$$v_0=1$$$, $$$v_1=3$$$, $$$v_k=2k+1$$$.

Using the method above, we can only construct a graph when $$$k$$$ is a power of $$$2$$$. Consider the binary representation of $$$k$$$. We first construct the backbone such that the number of paths has the same most significant bit as $$$k$$$. Then, for every non most significant set bit in $$$k$$$, say its the $$$j$$$-th bit, we add an edge from $$$v_j$$$ to the terminal vertex. For example, for $$$k=11$$$, its binary representation is $$$1101$$$, and we can construct the following graph:

Since for each $$$v_i$$$, there are exactly $$$2^i$$$ path ending at that vertex, we simple connect the positions corresponding to the set bits to the terminal vertex. There is a slight detail: we can't connect $$$v_{b-1}$$$ to $$$v_b$$$, as multiple edges are not allowed. In this case, we need to add another vertex and another edge.

In the worst case, where $$$k=2^p-1$$$ for some integer $$$p$$$, we need $$$4p+1$$$ edges: $$$3p$$$ for the backbone, $$$p$$$ for $$$p$$$ set bits, and $$$1$$$ extra for the detail above.

Can we do better?

The answer is Yes. To utilise edges even more, we need to change the structure of the backbone. After some thoughts, I came up with the following structure:

where $$$i$$$ connects to $$$i+1$$$ and $$$i+2$$$ for all $$$i \le n-2$$$, and $$$n-1$$$ connects to $$$n$$$. It is not hard to see that the number of distinct paths ending at vertex $$$i$$$ would be $$$F_i$$$, the $$$i$$$-th fibonacci number. The proof is left as a small exercise (hint: consider dp).

Using this structure, we can create $$$F_m$$$ paths using $$$2m-1$$$ edges.

Surprisingly, we can still use the binary representation idea above. Just like every integer can be represented by the sum of distinct powers of $2$s, every integer can also be represented by the sum of distinct fibonacci numbers. The theorem is called