Combinatorics

The importance of binomial coefficients comes from another question that arises. How many subsets are contained in a set of objects? A set is just a collection of objects like the three songs on the CD. Subsets are the set itself, the empty set, or the set of nothing, and any smaller groupings of the set. So the first two songs alone would be a subset of the set of three songs. Intuitively, eight subsets could be found on a three song CD by writing out all possible subsets, including the set itself.

Unfortunately, the number of subsets also gets large quickly. The general way to find subsets is not as easily seen as finding the total number of permutations of a deck of cards. It has been found that the number of subsets of a set can be found by taking the number of elements of the set, and raising the number two to that power. So for a CD with three songs, the number of subsets is just two to the third power, 2 × 2 × 2, or 8.

For a deck of 52 cards, the number of subsets comes to about 45 with fourteen zeros behind it. It would take a long time to write all of those subsets down. Binomial coefficients represent the number of subsets of a given size. Binomial coefficients are written C(r;c) and represent "the number of combinations of r things taken c at a time." Binomial coefficients can be calculated using factorials or with Pascal's triangle as seen below (only the first six rows are shown.) Each new row in Pascal's triangle is solved by taking the top two numbers and adding them together to get the number below.

The triangle always starts with one and has ones on the outside.

So for our three song CD, to find the number of two song subsets we want to find C(3,2) which is the third row and second column, or three. The subsets being songs one and two, two and three, and one and three. Binomial coefficients come up in many places in algebra and combinatorics and are very important when working with polynomials. The other formula for calculating C(r;c) is r! divided by c! × (r-c)!.