1

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.

A Question Asker
  • 459
  • 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 01 '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 02 '11 at 00:04
  • I will delete the solution I had posted until there is clarification of the question. – André Nicolas Jun 02 '11 at 00: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 02 '11 at 00: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 02 '11 at 00:24
  • Eric: any number of spots – A Question Asker Jun 02 '11 at 16:13

1 Answers1

3

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.

Henry
  • 157,058