1. ## Combinatorial argument

I can prove these algebraically with no problems but I'm having trouble explaining with words why they are true i.e. with a combinatorial argument. Can someone give me a hint?

$\displaystyle C(n, k) = C(n-2, k-2) + 2C(n-2, k-1) + C(n-2, k)$

$\displaystyle P(n, k) = P(n-1, k) + kP(n-1, k-1)$

Thank you.

2. No one knows?

3. Originally Posted by VENI
I can prove these algebraically with no problems but I'm having trouble explaining with words why they are true i.e. with a combinatorial argument. Can someone give me a hint?

$\displaystyle C(n, k) = C(n-2, k-2) + 2C(n-2, k-1) + C(n-2, k)$

$\displaystyle P(n, k) = P(n-1, k) + kP(n-1, k-1)$

Thank you.
For C(n,k), consider breaking the k-subsets of 1, 2, ..., n into 4 sets:

1. Those which include n-1 and n;
2. those which include n-1 but not n;
3. those which include n but not n-1; and
4. those which include neither n-1 nor n.

For P(n,k), consider breaking the k-permutations of 1, 2, ..., n into 2 sets:

1. Those which do not include n; and
2. those which do. In this case, consider the possible positions of n among the other k-1 integers.