From Wikibooks, open books for an open world
Jump to navigation Jump to search

What is combinatorics?[edit | edit source]

See also: Set Theory/Sets, Wikipedia:Set-builder notation, and w:Combinatorics
Figure 1. Venn diagram to illustrate union, intersection, and universe.

Combinatorics involves the counting and enumeration of elements of sets and similar structures such as sequences and multisets. We begin by reviewing the properties of sets, as illustrated in the Venn diagram of figure 1, the integer 2 is both even and prime, while the integer 1 is not a prime number. Letting denote prime and denote even, the figure suggests that we define the two sets, , and If a set has a finite number of elements[1] that number is known as the set's cardinality. Hence the cardinality of and are 3 and 2, respectively. The intersection, and union, of our two sets is probably well known to most of our readers. The value in introducing students to set theory using Venn diagrams is that it is self evident that order is not important in defining the elements of a set. In roster notation, this equivalence can be expressed as,

Two other sets associated with figure 1 are worth mentioning. The universe can be defined as set of items that are under consideration within the context of any given discussion or analysis of a system. In figure 1, the box around suggests that the universe for this discussion should be Another important set is the empty set, which contains no elements whatsoever. The empty set can also be written as .

Figure 2. The dotted circles and ovals define the 8 elements of the powerset of the set {1,2,3}.


The power set (or powerset) of a set is the set of its subsets of , including the empty set and the set itself. The powerset of the set t is illustrated in Figure 2. For reasons that will soon become clear, the convention is to denote the powerset of as . This notation permits us to write:

Note that contains elements, while its powerset contains elements. The generalization to the powerset of a set with elements containing elements follows in the next section.


Like a set, a sequence contains a possibly infinite number of elements (or members.) In contrast, with sets, the order (enumeration) is part of what defines a sequence. Sequences are written with parentheses instead of curly brackets , so that in contrast with the situation for set of (even) in Figure 1, these two sequences are not equal:

... or in string/word notation:

In computer science, a sequence consisting of characters is called a string. For that reason, it is often convenient to write sequences of characters as words (or strings.) For example, the sequence is more efficiently expressed as . Note that repetition plays an essential role in defining a sequence:
Example: While and are pronounced the same,


A multiset (or bag, or mset) combines the properties of a set and a sequence. Order (enumeration) is not important in defining a multiset, but repetition of elements is allowed. It is often convenient to denote multisets with square brackets Example: While represents the equality of two multisets, we have, for sequences (or in string notation.)

Fundamental Counting Principle[edit | edit source]

Figure 3. In set theory this is called the Cartesian product of two sets, with cardinality,
Figure 4. The counting principle is not useful when the number of choices at each step is not unique.
Figure 5. The counting principle only applies if the outcomes are defined so that .
See also: Probability/The Counting Principle and Wikipedia:Rule of Product

The Fundamental Rule of Counting: If a set of choices or trials, , could result, respectively, in possible outcomes, the entire set of choices or trials has possible outcomes. (The numbers cannot depend on which outcomes actually occur.)

The tree diagram of Figure 3 illustrates this for , , and . The number of possible outcomes is This might be visualized by imagining the flip of three-sided die (with outcomes 1,2,3), followed by the flip of a two-sided coin (with outcomes A,B). The first choice (decision) is to select , where [2] The number possible outcomes for this first choice is For the second choice, and

Counting the number of elements in a powerset[edit | edit source]

Let us now count the elements of a superset of set S, where S contains members. This is accomplished by constructing a single element of the superset, while keeping track of the number of choices that were made at each step. The procedure is as follows:

Create an element in the superset of a set with elements, iterate through each member of S and decide whether to include that element.

This procedure requires a sequence of "choices", each involving options. This proves the statement made above that the powerset of a set with elements contains elements.

The counting principle misused[edit | edit source]

Figures 4 and 5 illustrate the fact that the counting principle is not always useful. Figure 4 calculates the ways the three integers can be added to five, if the integers are restricted to the set . Since these three integers are choices (decisions), it is convenient to label the choice indices with capital letters:

What does mean? It is the second choice and that choice is the integer 3. Also, if we know that , we also know that the first choice was

We cannot apply the counting principle to figure 2 because depends on In our case, and and This leads us to an important caveat about using the counting principle:

  • The counting principle cannot be used if the number of outcomes at each step cannot be uniquely defined.

Figure 5 exams two flips of a coin. It calculates the correct number of outcomes to be, but only if we carefully define the outcome. The counting principle is valid only if heads followed by a tails (HT) is a different outcome than tails followed by heads (TH). In other words:

  • When counting outcomes it is important to understand the role that order (enumeration) plays in defining outcomes.

But, if we instead are counting the outcomes in a fashion such that HT and TH are considered to be the same, then a formula such as cannot be used:

  • The counting principle does not hold if two different decision paths lead to the same final outcome.

Permutations: n![edit | edit source]

See also: High_School_Mathematics_Extensions/Supplementary/Basic_Counting
Figure 6. 3!=3·2·1= 6 permutations of {1,2,3}.

To permute is vaguely defined to change the order of something.[3] For example, there are 2 ways to permute the string , namely: and The 6 ways to permute the string 123 are shown in Figure 6. The formula for the number of ways to permute objects involves the factorial, which is defined as, There are at least three justifications for adopting the convention that, [4]

There are n! ways to permute a sequence with n members if all members are unique.

k-permutations: P(n,k)[edit | edit source]

Figure 7: k-permutation

Suppose that instead of listing all n elements in a set S = {1, 2, ... , n}, we list only k elements out of the set where . The number of ways to do this is obviously less than or equal to , and defines the k-permutation coefficient:

Example: A recently formed music group has four original songs they can play. They are asked to perform two different songs at a music festival. We wish to compute the number of song arrangements the group can offer in concert. Using the counting principle, they make two decisions: The first is to select one out of four songs, so that . Since they can't to repeat the song, their second (and final) choice is between three songs, with Therefore there are, possible outcomes, as shown in Figure 7. This result is consistent with our formula for the number of k-permutations, since Our goal is to prove that but first

The formula, is valid only if none of the elements are repeated.

The easiest way to ensure that no elements are repeated is to view the elements as a set (and not a sequence, where repeated elements are allowed.)[5]


Use integers to label the set as Our task is to select integers from this list, removing them one at a time without replacement. We know that decisions must be made, but how many choices were available at each decision. To that end we construct a table:


Here we use the pattern set by the first, second, and third choices to informally "guess" the pattern an state (without rigor) the general formula for the choice. Therefore:


Simple algebra produces a more compact and easily remembered formula:

Combinations: C(n,k)[edit | edit source]

Figure 8: is shown for and The dotted ellipses remind us that these are sets, where order is not important.
Figure 9: combinations.

Wikipedia defines a combination as a selection of items from a set, such that the order of selection does not matter. Since the order in which these items are selected are not important, each selection is a subset of the original set. Figure 8 illustrates for the set The number of elements in this set is From our earlier discussion of the powerset, we know that the total number of subsets is . All 8 subsets are shown in the figure, organized by how many items are in each subset (for example, the subset in the upper-left corner contains 3 elements, while all subsets with 2 elements occupy the lower-right corner.) Let denote the number of elements "chosen" to be in each of the 8 subsets of set (where the number of elements in is, .)

set has elements. It is the empty set: .

sets have element. They are ,,and .

sets have elements. They are ,,and .

set has elements. It is the set itself: .

This is all consistent with the following:

"n-choose-k", or the number of ways to choose k elements from a set of n elements is:

The 6 combinations for a set of 4 elements are displayed in figure 9.

Binomial and multinomial coefficients[edit | edit source]

The proof of our formula for will be postponed to the next section where the multinomial coefficient is introduced. The relationship between combinations and multinomial coefficients is well known.

Two examples Pascal's triangle[edit | edit source]

←binomial | combination→

Special cases worth remembering[edit | edit source]

The formula for counting combinations has special cases that are worth remembering:

(There is only one way to pick no thing and only one way to pick all things.)
(there are n ways to pick one thing or to leave one thing out)
(There are the same number of ways of picking of things as there are of leaving out of things)

Partitions[edit | edit source]

Multinomial partitioning[edit | edit source]

Abstractly, a combination is equivalent to partitioning a set into two subsets, one containing k objects and the other containing the n-k remaining objects. In general, the set S = {1, 2, ... , n } can be partitioned into r subsets. Let be nonnegative integers such that

Consider the following iterative algorithm that leads to a partition of S. First, we select a subset of elements from S. Having chosen the first subset, we select a second subset containing elements from the remaining elements. We continue this procedure by successively choosing subsets of elements from the remaining elements, until no element remains. This algorithm yields a partition of S into r subsets, with the p-th subset containing exactly elements.

We wish to count the number of such partitions. We know that there are ways to form the first subset. Examining our algorithm, we see that there are

ways to form the p-th subset. Using the counting principle, the total number of partitions is then given by

This expression is called a multinomial coefficient.

Example: A die is rolled nine times. We wish to compute the number of outcomes for which every odd number appears three times. The number of distinct sequences in which one, three, and five each appear three times is equal to the number of partitions of {1, 2, ... , 9} into three subsets of size three, namely

In the above analysis, we assume that the size of each subset is fixed, three subsets of size three.

Number of ways to sum non-negative integers to some value[edit | edit source]

See also: Wikipedia:Stars and bars (combinatorics)

Suppose instead that we are interested in counting the number of ways of picking the sizes of the subsets, r subsets of size, where the sum of the sizes is a constant. Specifically, we wish to compute the number of ways integers can be selected such that every integer is nonnegative and


We can visualize the number of possible assignments as follows. Picture n balls spaced out on a straight line and consider r-1 vertical markers, each of which can be put between two consecutive balls, before the first ball, or after the last ball.

For instance, if there are five balls and two markers then one possible assignement is illustrated below.


The number of objects in the first subset corresponds to the number balls before the first marker. Similarly, the number of objects in the p-th subset is equal to the number of balls between the p-th marker and the preceding one. Finally, the number of objects in the last subset is simply the number of balls after the last marker. In the figure, the integer assignment is


Two consecutive markers imply that the corresponding subset is empty. There is a natural bijection between an integer assignment and the graphical representation depicted above. To count the number of possible integer assignments, it then suffices to compute the number of ways to position the markers and the balls. In particular, there are n + r - 1 positions, n balls, and r - 1 markers. The number of ways to assign the markers is equal to the number of n-combinations of n + r - 1 elements,

Example - Sampling with Replacement, without Ordering: An urn contains r balls numbered one through r. A ball is drawn from the urn and its number is recorded. The ball is then returned to the urn. This procedure is repeated a total of n times. The outcome of this experiment is a table that contains the number of times each ball has come in sight. We are interested in computing the number of distinct outcomes. This is equivalent to counting the ways a set with n elements can be partitioned into r subsets. The number of possible outcomes is therefore given by

Example - Sampling without Replacement or Ordering: An urn contains n balls numbered one through n. A ball is drawn from the urn and placed in a jar. This process is repeated until the jar contains k balls, where . We wish to compute the number of distinct combinations the jar can hold after the completion of this experiment. Because there is no ordering in the jar, this amounts to counting the number of k-element subsets of a given n-element set, which is given by

Again, let S = {1, 2, ... , n}. Since a combination is also a subset and the number of k-element combinations of S is , the sum of the binomial coefficients over all values of k must be equal to the number of elements in the power set of S. Thus, we get

Stirling's approximation for large n![edit | edit source]

See also: Biological Physics/Stirling's Approximation and Wikipedia:Stirling's approximation

The number n! grows very rapidly as a function of . A good approximation for when n is large is given by Stirling's formula,

as .

The notation signifies that the ratio approaches 1 as tends to infinity. Taking the natural logarithm of both sides and dropping some terms yields (at the expense of accuracy), . A change-of-base formula for logarithms permits us to write this as,

For more precision, the asymptotic expression with a precise range for

Exercises[edit | edit source]

These examples and problems are either copied from, or inspired by material found in a previous version of this chapter.

Combinations and k-permutations[edit | edit source]

  1. Any combination of a set is also called a ______ of that set.
  2. A combination differs from a permutation in that elements in a ____________ have no specific ordering.
  3. The number of possible 2-element subsets of S = {1, 2, 3, 4} is _____. (ENTER THE CORRECT INTEGER)
List these subsets: ___________________________________________________________________
  1. The number of possible 2-permutationsof S = {1, 2, 3, 4} is _____. (ENTER THE CORRECT INTEGER)
List these 2-permutatios: ___________________________________________________________________

Flipping a coin and rolling a 6-sided die[edit | edit source]

Consider an experiment consisting of flipping a coin and rolling a six-sided die. There are ____ possibilities for the coin, and ____ for the die has six sides. The total number of outcomes for this experiment is ______.

List these outcomes: ____________________________________________________________________________________

Sampling[edit | edit source]

Sampling with Replacement and Ordering

An urn contains balls numbered . A ball is drawn from the urn, and its number is recorded on an ordered list. The ball is then replaced in the urn. This procedure is repeated times. We wish to compute the number of possible sequences that results from this experiment.

Sampling without replacement, but with ordering

An urn contains n balls numbered one through n. A ball is picked from the urn, and its number is recorded on an ordered list. The ball is not replaced in the urn. This procedure is repeated until k balls are selected from the urn, where . What formula calculates the number of possible sequences that results from this experiment.

2-letter permutations of A,B,C,D[edit | edit source]

Begin with permutations of that start with the letter . Remember: Since the order is important, and are NOT the same thing! Fill in the blanks as we count and list all the 2-permutations of

If the first element begins with , the second element can be ____, or ____, or _____, but not ____.

The two letter permutations that begin with are: (___ , ___), (___ , ___), and (___ , ___).

Next, count and list all two letter permutations that begin with the letter :

Continuing for C as the starting letter, count and list:
Finally, for D, count and list:

Consider the integer set To derive the formula for the number permutations of S, we count ways to select any given element of the set, starting with the first member for which there are possible choices. We shall use the index to count the decisions. For example, corresponds to the first decision (with distinct choices.) Express the number of distinct possibilities for the -th element. Hint: Your answer will be an expression involving the variables and . You may assume that

Set theory[edit | edit source]

The power set of S, denoted by , is the set of all subsets of . In set theory, represents the set of all functions . By identifying a function in with the corresponding preimage of one, we obtain a bijection between and the subsets of . In particular, each function in is the characteristic function of a subset of .

Suppose that is finite with elements. For every element of , a characteristic function in is either 0 or 1. There are therefore distinct characteristic functions . Hence, the number of distinct subsets of is given by .

Count and then list all elements of the power set of S={a,b}

Lottery tickets[edit | edit source]

Example - Pick 3 Texas Lottery: The Texas Lottery game Pick 3 is easy to play. A player must pick three numbers from zero to nine, and choose how to play them: exact order, or any order. The Pick 3 balls are drawn using three air-driven machines. These machines use compressed air to mix and select each ball.

The probability of winning while playing the exact order is

The probability of winning while playing any order depends on the numbers selected. If three distinct numbers are selected then the probability of winning is 3/500. If a number is repeated twice, the probability of winning is 3/1000. While, if the same number is selected three times, the probability of winning becomes 1/1000.

Example - Mega Millions Texas Lottery: To play the Mega Millions game, a player must select five numbers from 1 to 56 in the upper white play area of the play board, and one Mega Ball number from 1 to 46 in the lower yellow play area of the play board.

Partitions[edit | edit source]

tba All drawing equipment is stored in a secured on-site storage room. Only authorized drawings department personnel have keys to this door. Upon entry of the secured room to begin the drawing process, a lottery drawing specialist examines the security seal to determine if any unauthorized access has occurred. For each drawing, the Lotto Texas balls are mixed by four acrylic mixing paddles rotating clockwise. High speed is used for mixing and low speed for ball selection. As each ball is selected, it rolls down a chute into an official number display area. We wish to compute the probability of winning the Mega Millions Grand Prize, which require the correct selection of the five white balls plus the gold Mega ball. The probability of winning the Mega Millions Grand Prize is

References and footnotes[edit | edit source]

  1. In set theory, an element is also called a "member".
  2. In plain English: The choice is a member of the set (which of course has 3 members.)
  3. wikt:Special:permalink/62799858#Verb
  4. #1: Assume that n! = n·(n-1)! holds for n=1 and n=0, and do a bit of algebra. #2: Define x! = Γ(x + 1), where Γ is the gamma function. #3: Our formula for k-perturbations gives the correct answer when n=k, since n!/(n-k)!=n!/0!=1.
  5. Some texts permit a set to have multiple entries, with the understanding that, for example, {a,a,b} = {a,b}. But generally speaking, sets are expressed by showing only each element only once.