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