X is a set of n positive integers with sum s and product p. Show for any integer N >= s, ∑( parity(Y) (N - sum(Y))Cs ) = p, where aCb is the binomial coefficient a!/(b! (a-b)! ), the sum is taken over all subsets Y of X, parity(Y) = 1 if Y is empty or has an even number of elements, -1 if Y has an odd number of elements, and sum(Y) is the sum of the elements in Y.
Solution
(∑ (-1)n binomial) with the sum over all subsets Y of a set X strongly suggests the principle of inclusion and exclusion.
Consider all sequences of length N ≥ s of 0s and 1s with a total of s 1s. We can regard positions 1, 2, ... , a1 as block a1, positions a1 + 1, a2 + 2, ... , a1 + a2 as block a2, positions a1+a2 + 1, a1+a2 + 2, ... , a1+a2 + a3 as block a3, and so on up to a1 + ... + an-1 + 1, ... a1 + ... + an as block an. We are interested in sequences which have just one 1 in each block. Counting directly there are obviously just p such sequences.
But we can also take N' to be the total number of sequences of 0s and 1s with s 1s and NY to be the number with no 1s in block k for k in Y, where Y is a subset of X. Requiring one 1 in each block is equivalent to requiring no block to have no 1s. So the PIE gives that p = N' - NY for Y with one element + NY for Y with 2 elements and so on. N' = NCs and NY = (N - sum(Y))Cs, so we have p = ∑( parity(Y) (N - sum(Y))Cs ), which is the required relation.
© John Scholes
jscholes@kalva.demon.co.uk
23 Aug 2002