9
$\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.

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

3 Answers 3

7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Perfect, thanks! That was very helpful. $\endgroup$ Dec 23, 2012 at 6:39
5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Nice! Very convenient that the two cases give the same number of possibilities. $\endgroup$ Dec 23, 2012 at 23:39
  • $\begingroup$ @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.) $\endgroup$ Dec 24, 2012 at 1:02
  • $\begingroup$ Ah, that makes sense. $\endgroup$ Dec 25, 2012 at 2:57
4
$\begingroup$

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 $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{G} = \textsc{SET}(\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.

$\endgroup$
3
  • 1
    $\begingroup$ +1, indeed a very beautiful sledgehammer for this nut :-) $\endgroup$
    – joriki
    Dec 23, 2012 at 23:14
  • $\begingroup$ Very nice. I was trying something along these lines, but I wasn't able to quite work it out. $\endgroup$ Dec 23, 2012 at 23:38
  • $\begingroup$ $H(z,t) = G(tz,1/t)$, the o.g.f.. for the Laguerre polynomials of order -1. See oeis.org/A111596, oeis.org/A105278, and the refinement oeis.org/A130561. Cf. also oeis.org/A008297 and oeis.org/A066667. $\endgroup$ Apr 12, 2020 at 17:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .