How to compute $\sum_{r=0}^N \frac{N!}{(N-r)!}$? This quantity is the count of $r$-permutations of $N$ items (for $r$ ranging from $0$ to $N$).

45 Views Asked by At

Given $N$ items, how many $r$-permutations are there (for $r$ ranging from $0$ to $N$)?

  1. There is $1$ $0$-permutation (the empty permutation).
  2. There are $N$ $1$-permutations.
  3. There are $N(N-1)$ $2$-permutations.
  4. There are $N(N-1)(N-2)$ $3$-permutations.

...

$r$. There are $\frac{N!}{(N-r)!}$ $r$-permutations.

...

$N$. There are $N!$ $N$-permutations.


So, the number of $r$-permutations of $N$ items is

$$ S(N) = \sum_{r=0}^N \frac{N!}{(N-r)!} = 1 + N + N(N-1) + N(N-1)(N-2) + ... + N! $$

Is there a way to simplify this to simpler terms? My only attack is that

$$S(N) = 1 + N \cdot S(N-1)$$

with

$$S(0) = 1$$

which is very close to the factorial recurrence relation $F(N) = N \cdot F(N-1)$ with $F(0) = 1$, but not quite because of the $1 +$ in $S(N) = 1 + N \cdot S(N-1)$.


I'm aware that

$$ \sum_{r=0}^N \frac{N!}{r!(N-r)!} = \sum_{r=0}^N \binom{N}{r} = 2^N $$

from counting subsets of $N$ distinct items, but not sure if this can be used to solve the other summation.


Could a generating function approach work here?