Number of acyclic digraphs on $[n]$ with $k$ edges and each indegree, outdegree $\leq 1$

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.

-
Where did you get this formula ? It looks too big. – ashley Dec 23 '12 at 3:57
Note: This is OEIS sequence A089231. – joriki Dec 25 '12 at 15:36
Note: The expected number of edges in a graph uniformly randomly drawn from all graphs of this type on $[n]$ is discussed here. – joriki Dec 25 '12 at 17:37

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

-
Perfect, thanks! That was very helpful. – Jair Taylor Dec 23 '12 at 6:39

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!\;.$$

-
Nice! Very convenient that the two cases give the same number of possibilities. – Jair Taylor Dec 23 '12 at 23:39
@Jair: I'm not sure that there really are two cases. In both scenarios you cannot choose as a tail the vertex at the head of the chain for which $i$ is the current tail, and that's the reason for the $n-i$ possibilities. The first scenario just has $i$ as its own chain. (+1, by the way. I think I was the second upvote on this answer.) – Mike Spivey Dec 24 '12 at 1:02
Ah, that makes sense. – Jair Taylor Dec 25 '12 at 2:57

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.

-
+1, indeed a very beautiful sledgehammer for this nut :-) – joriki Dec 23 '12 at 23:14
Very nice. I was trying something along these lines, but I wasn't able to quite work it out. – Jair Taylor Dec 23 '12 at 23:38