Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
    
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!\;. $$

share|improve this answer
    
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.

share|improve this answer
1  
+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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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