D.1 Derivation of the Binomial Coefficients c(N, r)

The binomial coefficient c(N, r) is the coefficient of x ^r y ^{N ?r} in the expansion of (x + y) ^N , and can be obtained as follows. Think of the product of N brackets (x+ y)(x+ y) . When you multiply the brackets out, you get a term in x ^r y ^{N ?r} by taking x from r of the brackets and y from the rest. How many of these terms are there? Think of each bracket as an object which is assigned either to the x pile (containing r objects) or the y pile (containing N ? r). We do not care in what order the objects are assigned. The number of terms in x ^r y ^{N ?r} is simply the number of different ways the assignment can be made; call this number c(N, r). Now suppose that the objects are labelled and we distinguish between different orderings of them. The r objects in the x pile can be permuted to give r! orderings, ^[1] and those in the y pile (N ?r)! orderings. The product c(N, r)r! (N ?r)! is the total number of orderings of N objects, which is N!. Hence,

Putting gives

This derivation of c(N, r) can be...