1
$\begingroup$

I'm reading the book An Introduction to Probability Theory and Its Applications by William Feller and trying to solve the problems after chapters. I can figure out the probability can be rewritten as

$$A(r, n+1) = \sum_{k=1}^{r} {r \choose k}A(r-k, n)$$

which explained clearly by this question (Distribution of $r$ balls into $n$ cells leaving none of the cells empty.)

But, I cannot make it out that $$A(r, n+1)$$ has the final result as

$$A(r, n) = \sum_{v=0}^{n} (-1)^v{n \choose v}(n-v)^r$$

How does it get there? Any hints will be really appreciated!

$\endgroup$
1
  • $\begingroup$ Maybe you can try induction? $\endgroup$ – corindo Sep 17 '15 at 2:33
1
$\begingroup$

This is just inclusion exclusion.

In this case $A(r,n)$ seems to be the number of ways to put $r$ balls in $n$ boxes so none is empty.

Clearly The first summad gives us all of the possible asignments ($\binom{n}{0}n^r=n^r$).

The next term is $-1\binom{n}{1}(n-1)^r$. This is equal to all of the permutations in which the first box is empty, plus the number of assignments in which the second box is empty and so on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.