Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

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

1 Answer 1

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}$$

share|improve this answer
    
From the OP's question: "It's relatively easy to express this as a sum [...], but can we get a closed formula?" –  tj_ Mar 10 '13 at 23:52
    
TJ: I'd have said that a finite sum of closed formulas is a closed formula --- but I suppose there's no definitive authority on what "closed formula" means. –  Steven Landsburg Mar 11 '13 at 0:57
    
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
    
Steve: really? What polynomial in n? Since the sum grows exponentially in n, I think you mean to say something else. Gerhard "Have Polynomials Gotten Bigger Nowadays?" Paseman, 2013.03.11 –  Gerhard Paseman Mar 11 '13 at 15:58
    
Actually, I see where my thinking went astray. For fixed k, the sum is bounded by p(n) and kp(n), where p(n) looks like some constant times n(n-1)...(n-k+1). Never mind. Gerhard "Apologies To Miss Emily Litella" Paseman, 2013.03.11 –  Gerhard Paseman Mar 11 '13 at 16:05

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.