$$\begin{align}\\ S(n,r) &= \frac1{r!}\sum_{i = 0}^r (-1)^i\binom r i(r-i)^n\\ &= \frac1{r!}\sum_{i = 0}^r (-1)^{r-i}\binom r i i^n\\ \end{align}$$

I know how to derive the formula in the first line using inclusion-exclusion, but:

How did we go from the first line to the second?

  • 1
    $\begingroup$ Let $i=r-k$, since $i$ and $k$ are dummy variables, also $C_k^r=C_{r-k}^r$ , it can be written in the expression in the second line. $\endgroup$ – lEm Mar 8 '16 at 9:33

We have

$$S(n,r)=\frac1{r!}\sum_{i = 0}^r (-1)^i\binom{r}{i}(r-i)^n$$

Note that $i$ runs from $0$ to $r$, but we can also run from $r$ to $0$, which is equivalent with replacing all $i$'s with $r-i$. We get

$$S(n,r)=\frac1{r!}\sum_{i = 0}^r (-1)^{r-i}\binom{r}{r-i}(r-(r-i))^n$$

Note that $\binom{r}{r-i}=\binom{r}{i}$ so that this reduces to

$$S(n,r)=\frac1{r!}\sum_{i = 0}^r (-1)^{r-i}\binom{r}{i}i^n$$

en that's the last line.

  • $\begingroup$ What do you mean we can run from $r$ to $0$. Why is that true? Do you mean, just reversing the order in which sums will appear? For instance $\sum_{i=r}^0$? $\endgroup$ – Al Jebr Mar 10 '16 at 3:38
  • $\begingroup$ @AlJebr, yes, that's what I mean. However, it's quite uncommon to write $\sum_{i=r}^0$, since the lower bound is then higher then the upper bound (which would then be the Empty Sum, since then you're summing no terms). I'm sorry for the confusion. Tell me if anything is still unclear. $\endgroup$ – vrugtehagel Mar 10 '16 at 9:46
  • $\begingroup$ Why does having the sum run from $r$ to $0$ change the $i$'s with $r-i$? $\endgroup$ – Al Jebr Mar 10 '16 at 21:51
  • 1
    $\begingroup$ Because, if we let $i$ run from $0$ to $r$, then $r-i$ runs from $r$ to $0$ $\endgroup$ – vrugtehagel Mar 10 '16 at 22:05

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.