Combinatorics, Combinations

Combinations

A box may have 13 different books in it, and you're selecting 4 to take to school. How many 4 book sets are possible?

Start by calling this a truncated permutation. You're going to put the four books on the shelf, left to right, and there are 13!/9! ways to do that. As you gather up the four books and put them in your bookbag, the order doesn't matter, so the 4! arrangements of the 4 books all map onto the same set. The number of combinations is 13!/(9!×4!), or 715.

In general, a set of n elements produces n!/(k!×(n-k)!) k element subsets. This is a common expression, called "n choose k", and written (n:k) for convenience. (Note, (n:k) is my own ascii notation; the standard notation is two dimensional, and shown on the right.)

Although most applications partition a set into two subsets, e.g. the bookbag and the box, the formula can be generalized to handle many subsets. If we placed four books in the bookbag, three in a desk drawer, and two on the mantle, leaving 4 in the box, the number of book distributions is 13!/(4!×3!×2!×4!) = 900900.

Leaving a combination's size unspecified seems, at first, to complicate the problem. If we select an arbitrary number of books from a box containing 13 books, and stuff them into a bookbag, the number of possibilities is (13:0) + (13:1) + … + (13:13) = 8192. The size of the subset is considered first, then the possible combinations for each size. But there is an easier way.

Each book either goes into the bookbag or remains in the box. Two choices for each of 13 independent events yields 2¹³ = 8192 possibilities. Of course, we can have more than two containers. The 13 books can be placed into k different containers in k¹³ ways.

When the elements are indistinguishable (say 13 marbles), they can be placed in k containers in (13+k-1:13) ways. To see this, picture each marble distribution as a row of marbles with k-1 container delimiters inserted into the row. The marbles between delimiter i-1 and i are located in the i^th container. Set k = 2, for instance, and there are (14:13) = 14 possible outcomes. Any of 0 to 13 marbles can be placed in the first box, leaving the rest for the second box.