[AMOF] [GENERATE] [Schoolnet Icon]


Information on Combinations of a Set

[Description | Example | History | Applications | Implementation | Classroom | Links]


Description of the Problem

What are the different ways that Alice, Bob, Carol, and David can pair up to ride on a roller coaster car that has two seats in the front and two in the back? Who sits on the left and who on the right doesn't matter. We can immediately simplify the problem by observing that after the two front seats are taken, there is no choice about who goes into the back. One way of solving the problem is to list all possible front pairs: Alice and Bob, or Alice and Carol, or Alice and David, or Bob and Carol, or Bob and David, or Carol and David; there are exactly six ways. What we have just done is to list all "combinations" of two persons chosen from four persons. Similarly we could form the combinations of any number of persons from a larger group of persons. Below we give a mathematical definition of what constitutes a combination.

A set is a collection of objects, and a subset is a sub-collection of those objects. For example, if the collection consists of the three letters A, B, and C, written as {A,B,C}, then the possible subcollections are {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, and {A,B,C}. A k-combination of an n-set is a subset with k elements chosen from a set with n elements. For example, the 2-combinations of the 4-set {A,B,C,D} are {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D}. Compare this list with the first letters in the names from the example in the first paragraph; i.e., {A,B} corresponds to Alice and Bob.

In the Amazing Mathematical Object Factory (AMOF), the set from which subsets are made is always the set [n] of the first n positive integers (i.e., [n] = {1,2,...,n}). If bitstring output is selected, then each combination S is listed as a bitstring bn···b2b1, where bi = 1 if i is in S and bi = 0 if i is not in S. If subset output is selected, then each subset S (say of size k) is output as an ordered list {s1,s2,...,sk} of its elements.

The number of k-combinations of an n-set is the binomial coefficient C(n,k) = n!/[k!(n-k)!]. [The name binomial coefficient comes from the role these numbers play in the binomial theorem, which gives the expansion of (1+x)n.] The arrangement of binomial coefficients shown below is known as Pascal's triangle. Each number is the sum of the two numbers above it.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1

This triangle mirrors the classic recurrence relation for binomial coefficients:

C(n,k) = C(n-1,k) + C(n-1,k-1)


Example

What are the different ways to make a two person committee, where the persons are chosen from Alice, Bob, Carol, and Dave? Call them A, B, C, and D. There are six ways, namely {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, and {C,D}. This example is identical in concept to the roller-coaster example presented earlier.

To work this problem in AMOF, select lexicographic (or some other) order, and enter n=4 and k=2. If you ask for the first two output options, then the result is shown below.

Bitstring
n...321
Subsets
0011
{1,2}
0101
{1,3}
0110
{2,3}
1001
{1,4}
1010
{2,4}
1100
{3,4}

Since AMOF only generates subsets of numbers we must associate a number with each of the letters. This can be done in the natural way: A = 1, B = 2, C = 3, and D = 4. For example, {1,2} is interpreted as {A,B}. We've also shown the bitstring output for each combination. Recall that the bitstrings are indexed from right-to-left, with a 1 in position i meaning that i is in the subset, and a 0 meaning that it is not in the subset. For example, 1010 represents the subset {2,4} since 2 and 4 are the positions that the 1's occupy.

As another example, consider the familiar 6-49 lottery played across Canada. The object is to choose 6 numbers from the whole numbers 1,2,...,49 that will match the 6 numbers drawn randomly from the ball-machine. Since only the 6 numbers are important and not their order, this is an example of combination of 49 things taken 6 at a time. There are 13,983,816 ways of choosing 6 numbers from {1,2,...,49}. Pretty poor odds of winning it all!


A Brief History

It is impossible to give a historical account of the idea of a combination; its origins lie buried in antiquity. Some of the historical development of the binomial coefficients is known, however.

The arrangement of binomial coefficients is now known as Pascal's triangle, after the famous French mathematician, Blaise Pascal (1623-1662). He was responsible for discovering many of the fundamental properties of binomial coefficients, and a well-known programming language is named after him. This triangular arrangement was compiled and distributed posthumously in 1665 from his works printed in 1654.

Problems involving binomial coefficients and the knowledge of binomial expansions are mentioned in ancient manuscripts in Chinese, Hindu, and Arabic, dating back to around 1100. An illustration of Pascal's triangle first appeared in 1303--three hundred years before Pascal--in a Chinese manuscript, Precious Mirror of the Four Elements, by Chu Shih-chieh. The triangle first appeared in the West some 200 years later, again long before Pascal. However, it was not until around 1650 when Fermat and Pascal examined the probabilities related to gambling that gave the real beginning of modern combinatorial mathematics. Towards the end of 1600, Newton found the generalized binomial coefficients. The first comprehensive textbook on permutation and combination problems, Choice and Chance by Whitworth, appeared in 1901.


Applications to Mathematics and other Areas

Mathematics is defined as the science of patterns, and combinations are one of the most fundamental of all patterns. It is not surprising, therefore, that combinations occur in much of mathematics. A knowledge of combinations is necessary for understanding basic concepts of discrete mathematics and probability theory.

We give now a simple question that can be answered with a knowledge combinations and binomial coefficients. What is the probability of getting a flush in a five card poker hand on the initial deal? (A flush means that all five cards are in the same suit.) First, we have to recognize that a five card poker hand is a combination of 5 cards chosen from 52 cards. Thus the total number of possible hands is the binomial coefficient C(52,5) = 2,598,960. The ranks of the cards making up the flush is a combination of 5 ranks chosen from 13 rank. The suit of the cards making up the flush is a combination of 1 suit chosen from 4 suits. Multiplying, there are thus C(13,5)*C(4,1) = 1287*4 = 5148 ways of getting a flush. The probability of getting a flush is the ratio of the number of ways of getting a flush divided by the total number of hands; it is 5148/2598960 = 33/16660 = .001980792317. Not very high odds --- about 2 in every 1000 hands!


Explanation of AMOF Implementation

In the generation page, you will have the choice of generating:

You choose input values for n and k, where both numbers are not negative, k is not greater than n, and n is at most 20. You must choose at least one of the ways the combinations can be listed. Output can be a list of elements of the subsets and/or the equivalent bitstring representation. If combinations by transpositions is selected then you may also ask for the transition sequence to be output. For example, if you choose to see the combinations of k=3 elements chosen from n=4 things, in lexicographic order, and output by list of elements, then AMOF will return all four combinations of 3 elements chosen from 4 things as follows:

	{1,2,3}, {1,2,4}, {1,3,4}, {2,3,4} 
In AMOF all sets are written with the elements appearing in increasing order. This is just a convention; subsets with the same elements, such as {1,2,3} and {3,2,1} are identical.

"Lexicographic" order means that the subsets, represented by bitstrings, are in increasing order of those bitstrings. Thus all bitstrings with a 0 in the first position precede all bitstrings with a 1 in the first position. In the example above, lexicographic ordering of bitstrings gives 0111, 1011, 1101, 1110, corresponding to the subsets 123, 124, 134, 234. "Co-lexicographic" order means that the reversals of the bitstrings are in lexicographic order. To reverse a string write its letters in opposite order; e.g., the reversal of AMOF is FOMA. Thus all bitstrings with a 0 in the last position precede all bitstrings with a 1 in the last position. In lexicographic order the 2-subsets of {1,2,3,4} are 12, 13, 23, 14, 24, 34, (i.e., 0011, 0101, 0110, 1001, 1010, 1100), and in colex order they are 34, 24, 23, 14, 13, 12, (i.e., 1100, 1010, 0110, 1001, 0101, 0011).

In "transposition" order successive subsets differ by exactly one element. These are often referred to as "revolving door" listings; one element goes in and one goes out. In terms of the bitstring representation, a 0 and a 1 (which are not necessarily adjacent) are transposed. These two bits are colored blue in the AMOF output.


In the Classroom

The study of combinations form a part of the grade 11 and 12 math curriculum in British Columbia. The intended outcome is for students to learn how to compute the number of combinations of n things taken k at a time; to determine the probability of an event by examining combinations; and to learn how to apply the rules of permutations to solve problems. A problem-solving approach with lots of examples that are meaningful to everyday life will make learning this concept more enjoyable.

[NCTM] recommends for students who have finished second year algebra a discrete math course that includes permutations, combinations, Pascal's triangle, and recurrence relations. It also contains a useful chapter "Permutations and Combinations: a Problem Solving Approach for Middle School Students".

AMOF allows students to try many different values of n and k, and very quickly shows the number of solutions and what those solutions look like. They will be able to test their understanding of the subject by trying to compute the number of combinations of n things taken k at a time, and by trying to list the combinations in lexicographic and in transposition order. They may then generate the solutions using AMOF and check their answers.


Links to Other Relevant Sites and Sources of Information


[AMOF] [GENERATE] [Schoolnet Icon]


This page created by Frank Ruskey and Susan Ruskey, June 1996. ©Frank Ruskey, 1996, 1998.