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.

This is a little different than the normal case of permutations with repetition. Basically, let's say we have $n$ numbered balls, and there are $n$ spots. However, we can leave a spot empty if we want. The solution I got was basically...

$$ \sum_{i=0}^n {n \choose i} \frac{n!}{(n-i)!} $$

The idea being that for a given number of blank spots, you can calculate the permutations in the remainder...and the combination gives you the distribution of those blank spots for a given number of blank spots. But I'm wondering if there is a way to collapse this sum?

Thanks!

Edit: here is the clarification that was asked for (sorry for the delay). The answer for case 2 would be 7. You have 2 spaces, and three numbers. 012. 1 and 2 can only appear once, but 0 can repeat. The posibilities are as follow:

00,01,02,12,21,10,20

Make sense? For 3 balls, you have to do it out but it turns out to be 34. It follows the equation I posted. I hpoe that helps.

share|improve this question
1  
When you say we can leave a spot empty, do you mean we can leave any number of spots empty? Or just one? Also, there must be a typo in the denominator. –  Eric Naslund Jun 1 '11 at 22:55
    
@A Question Asker: Please clarify your question by giving an example - an enumeration of what you're trying to count for some small $n$. –  Yuval Filmus Jun 2 '11 at 0:04
    
I will delete the solution I had posted until there is clarification of the question. –  André Nicolas Jun 2 '11 at 0:16
    
@Yuval: I don't think the question is about counting the number of permutations, he already did that. I think the OP's question is how to clean up the sum of binomial coefficients, and write it in a nicer form. In any case, it is very confusing what he means. –  Eric Naslund Jun 2 '11 at 0:22
    
@user6312: On a second thought, I think the whole discussion about the answer you posted was because it is just not clear what the OP is asking for.... –  Eric Naslund Jun 2 '11 at 0:24

1 Answer 1

Your expression is OEIS A002720 and does not seem to have a simpler form, apart perhaps from

$$n! \; L_n(-1)$$

where $L_n(x)$ is a Laguerre polynomial and so may not be simpler.

share|improve this answer

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.