Show that if a ≤ b ≤ c ≤ n, then

n c

 c b

 b a

=

n a

 n − a b − a n − b c − b

.

(i) Use the definition of binomial coefficients as ratios of the factorials. (ii) Use directly the interpretation of the binomial coefficients as the number of subsets of a given size.

(iii) How many ways can one choose an a-element subset from a b-element subset from a c-element subset from a d-element subset from a n element set? (where a ≤ b ≤ c ≤

d ≤ n).