8
$\begingroup$

How many (labelled) acyclic digraphs are there on the vertex set $[n]$ with exactly $k$ edges and each indegree, outdegree $\leq 1$? The answer is ${n \choose k} {n-1 \choose k} k!.$ Is there a bijective proof? I imagine the ${ n \choose k}$ would represent choosing the set of vertices that have outdegree one, and the $k!$ could represent putting an ordering or cycle structure on these vertices, but I'm not sure what the other factor might represent.

  • 0
    Note: The expected number of edges in a graph uniformly randomly drawn from all graphs of this type on $[n]$ is discussed [here](http://math.stackexchange.com/questions/264698).2012-12-25

3 Answers 3

7

Any acyclic digraph on the vertex set $[n]$ with exactly $k$ edges and each indegree, outdegree $\leq 1$ will consist of $n-k$ components, each of which is essentially an ordered list, or tuple. (Starting with no edges and $n$ tuples, adding edge $(i,j)$ to the graph is equivalent to concatenating the tuple beginning with $j$ onto the end of the tuple that ends in $i$. Thus increasing the number of edges by $1$ decreases the number of tuples by $1$.) Thus the problem is equivalent to counting the number of ways to partition $[n]$ into $n-k$ nonempty tuples.

To construct $n-k$ nonempty tuples from $n$ elements, first choose a permutation of $n$ elements. This can be done in $n!$ ways. Then choose $n-k-1$ of the $n-1$ possible cut points in the permutation to create $n-k$ nonempty tuples. This can be done in $\binom{n-1}{n-k-1} = \binom{n-1}{k}$ ways. However, since there are $(n-k)!$ ways to order the tuples, there are $(n-k)!$ permutations that create the same set of $n-k$ nonempty tuples. Thus the number of ways a set of $n$ elements can be partitioned into $n-k$ nonempty tuples is $\frac{n!}{(n-k)!} \binom{n-1}{k} = \binom{n}{k} \binom{n-1}{k} k!.$

(Incidentally, the number of ways to partition $[n]$ into $k$ nonempty tuples is known to be the Lah number $L(n,k)$.)

  • 0
    Perfect, thanks! That was very helpful.2012-12-23
5

Here's another way to count. As you say, $\binom nk$ can be viewed as the number of ways of choosing $k$ vertices as heads of the $k$ edges. Now choose tails for these heads one by one. There are $n-1$ possibilities for choosing a tail for the first head. In choosing a tail for the $i$-th head, $i\gt1$, there are two cases. Either the $i$-th head has not been chosen as a tail yet; then $i-1$ vertices are excluded because they've already been chosen as tails, and the $i$-th head is different from them and also excluded, leaving $n-i$ possibilities. Or the $i$-th head has already been chosen as a tail; then the $i$-th head is one of the $i-1$ vertices excluded for already having been chosen as a tail, but there is exactly one additional vertex at the head of the chain leading to the $i$-th head that hasn't been chosen as a tail but is excluded because choosing it would create a cycle. Thus in either case there are $n-i$ possibilities, so in all there are

$ \binom nk(n-1)\dotso(n-k)=\binom nk\binom{n-1} kk!\;. $

  • 0
    Ah, that makes sense.2012-12-25
4

This problem may also be answered by using the bivariate (mixed) generating function $ G(z, u) = \sum_{n\ge 1} \sum_{k=0}^{n-1} q_{n,k} \; u^k \frac{z^n}{n!} $ where $q_{n,k}$ is the count of the acyclic digraphs on $n$ nodes and with $k$ edges that we wish to find, and hence is given by $ q_{n,k} = n! [u^k z^n] G(z, u).$

As pointed out the graphs in question are essentially sets of ordered lists, so that their combinatorial class specification is $\mathcal{G} = \mathfrak{P}(\mathcal{L})$ where $\mathcal{L}$ is the class of ordered lists. With $L(z, u)$ being the mixed generating function of ordered labelled lists this translates into $ G(z, u) = \exp L(z, u).$ But $L(z, u)$ is easily obtainable in closed form, we have $ L(z, u) = \sum_{n\ge 1} n! u^{n-1} \frac{z^n}{n!} = z \sum_{n\ge 1} (uz)^{n-1} = \frac{z}{1-uz}$ and thus $ G(z, u) = \exp\left(\frac{z}{1-uz}\right).$ To complete the calculation, we recall that $ [z^n] \frac{1}{(1-z)^s} = \binom{n+s-1}{s-1}$ giving $ n! [u^k z^n] G(z, u) = n! [u^k z^n] \sum_{m\ge 0} \frac{1}{m!} \left(\frac{z}{1-uz}\right)^m = n! [u^k] \sum_{m=0}^n \frac{1}{m!} [z^n]\left(\frac{z}{1-uz}\right)^m $ which is $n! [u^k] \sum_{m=0}^n \frac{1}{m!} [z^{n-m}] \frac{1}{(1-uz)^m} = n! [u^k] \sum_{m=0}^n \frac{1}{m!} u^{n-m} \binom{n-m+m-1}{m-1} \\= n! [u^k] \sum_{m=0}^n \frac{1}{m!} u^{n-m} \binom{n-1}{m-1}.$ Now switch variables in the sum to obtain $ n! [u^k] \sum_{m=0}^n \frac{1}{(n-m)!} u^m \binom{n-1}{n-m-1} = n! [u^k] \sum_{m=0}^n \frac{1}{(n-m)!} u^m \binom{n-1}{m} = n!\frac{1}{(n-k)!} \binom{n-1}{k} = \binom{n}{k} \binom{n-1}{k} k!. $

There is more on this beautiful method at this link at INRIA.

  • 0
    Very nice. I was trying something along these lines, but I wasn't able to quite work it out.2012-12-23