permutation formula $P(n, k) = P(n-1, k) + k P(n-1, k-1)$

Question

Can any one explain me the intuition behind this formula ? (with permutation example)

P(n, k) = P(n-1, k) + k* P(n-1, k-1)

Answer 1

Here is an example which should give you some insight into how I believe you should think about the formula.

Let's say $P(n, k)$ counts the number of teams of $k$ people you can make from a roster of $n$ people, where each person on a team has an assigned role. For instance, to make a bobsleigh team you have to pick four people, and you have to decide who sits in front, and so on.

If you only have four people available (Alice, Bob, Charlie and David), then there are $24$ different bobsleigh teams you can make from that. Thus $P(4, 4) = 24$.

Now, what happens if we get a fifth person, Eve? In other words, what is $P(5, 4)$? Well, one possibility is that Eve isn't chosen to sit in the bobsleigh. In that case there are $P(5-1, 4)$ different teams we can make, namely all the teams we already know of which do not include Eve.

Or Eve can be chosen as part of the team. In that case, she can hold any of $4$ positions, and no matter which of those four positions she chooses, the remaining three teammates can be picked and placed in $P(5-1, 4-1)$ ways (there are $5-1$ people left to choose from, and $4-1$ roles left to fill on the team).

In total, the number of different 4-person bobsleigh teams we can make from our five people is $$ P(5, 4) = P(5-1, 4) + 4\cdot P(5-1, 4-1)\\ = 24 + 4\cdot 24 = 120 $$

Answer 2

Okay, define a word $x=x_1\ldots x_k$ of length $k$ over the alphabet $[n]=\{1,\ldots,n\}$ to be a $k$-permutation of $n$ if $x$ contains no symbol more than once. The word $x$ can be viewed as an injective mapping $[k]\rightarrow[n]:i\mapsto x_i$. Indeed, the $k$-permutations of $n$ correspond one-to-one with the injective mappings $[k]\rightarrow[n]$.

Let $P(n,k)$ denote the number of all $k$-permutations of $n$. We have $P(n,1)=n$ and $P(n,n)=n!$ (bijections). For each $1<k<n$, the above formula holds.

This can be proved by a socalled ''Pascal argument''. Let $A$ be the set of $k$-permutations of $n$ which contain $n$, and let $B$ be the set of remaining $k$-permutations of $n$. Then $P(n,k)= |A|+|B|$.

In view of $A$, each $k-1$-permutation of $n-1$, $y=y_1\ldots y_{k-1}$, can be extended to a $k$-permutation of $n$, $y^{(i)}$, such that the symbol $n$ is inserted into position $i$. The assignment $(i,y)\mapsto y^{(i)}$ provides a bijection between $[k]\times \mbox{(set of $k-1$-permutations of $n-1$)}$ and the set $A$. Thus $|A| = k\cdot P(k-1,n-1)$.

In view of $B$, the elements of $B$ are exactly the $k$-permutations of $n-1$ and so $|B|=P(n-1,k)$.

As an example, the 2-permutations of 3, $12, 21, 13, 31, 23, 32$, are decomposed into $A=\{13,31,23,32\}$ and $B=\{12,21\}$.