# Putting objects into boxes so that each box gets <=2 objects

We have $k$ different objects and $n$ different boxes. In how many ways can we put those objects into boxes so that each box gets 0, 1 or 2 objects? Each object has to be in a box.

This looks different than any of the standard combinatorial problems (like partitions etc). It's relatively easy to express this as a sum or to get some kind of recursive formula, but can we get a closed formula?

-
When asking a question like this, please compute some examples so that readers don't have to. In this case, the sequence 1, 3, 9, 24, 54, 90, 90 for $n=3$ leads to oeis.org/A141765 – Barry Cipra Mar 10 '13 at 0:55
The general case is oeis.org/A027907 , and the case $k=n$ is oeis.org/A002426 . No explicit closed formula is likely. – Brendan McKay Mar 10 '13 at 3:15
Brendan: I think you are mistaken; the OP asked for $k$ different objects, which I take to mean that they're distinguishable (note that he used exactly the same adjective for the boxes). The sequence you quote assumes the objects are indistinguishable. In that case the sequence in Barry Cipra's comment is certainly correct for the case $n=3$. – Steven Landsburg Mar 10 '13 at 16:10
In fact, the case $k=n$ is oeis.org/A012244 . – Steven Landsburg Mar 10 '13 at 16:24
@Steve: You are quite correct! – Brendan McKay Mar 11 '13 at 0:26

Let $S_n$ be the symmetric group on $n$ letters, so that $S_k\times S_n$ acts on the set of allowable placements in the obvious way.
For a placement with $A$ boxes having 2 balls, $B$ boxes having 1 ball and $C$ boxes having 0 balls, the order of the isotropy subgroup is easily seen to be $$A!B!C!2^A$$ so the orbit size is $n!k!$ divided by this expression.
Adding up the sizes of all the orbits, and accounting for the facts that $k=2A+B$ and $n=A+B+C$, we get the expression $$\sum_{A=0}^{ceiling(k/2)}{n!k!\over A!(k-2A)!(n-k+A)!2^A}$$
TJ: In fact, for fixed $k$, this reduces to a polynomial in $n$, which surely counts as a closed formula by anyone's standards. – Steven Landsburg Mar 11 '13 at 1:06