No one knows?
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?
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.