Show that there are just (n-k+1)Ck subsets of {1, 2, ... , n} with k elements and not containing both i and i+1 for any i.
Solution
There is a bijection between subsets of {1, 2, ... , n} with k elements not containing both i and i+1 for any i and subsets of {1, 2, ... , n - k + 1} with k elements. Namely, associate r1 < r2 < ... < rk and r1, r2 - 1, r3 - 2, ... , rk - k + 1. But there are obviously just (n-k+1)Ck such subsets of {1, 2, ... , n - k + 1}.
© John Scholes
jscholes@kalva.demon.co.uk
4 Dec 1999