Given $N$ items, how many $r$-permutations are there (for $r$ ranging from $0$ to $N$)?
- There is $1$ $0$-permutation (the empty permutation).
- There are $N$ $1$-permutations.
- There are $N(N-1)$ $2$-permutations.
- 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?