Probability/Combinatorics

What is combinatorics?Edit

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}.

Powerset

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.

Sequences

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,  

Multisets

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 PrincipleEdit

 
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 powersetEdit

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 misusedEdit

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

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

 
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]

Proof

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:

Decision              
Choices              

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

 
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 coefficientsEdit

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 triangleEdit

  ←binomial | combination→  

Special cases worth rememberingEdit

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)

PartitionsEdit

Multinomial partitioningEdit

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 valueEdit

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.

 
Partitioning.png

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

 

 
Partitioning2.png

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

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  

 

ExercisesEdit

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

Combinations and k-permutationsEdit

  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 dieEdit

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: ____________________________________________________________________________________

SamplingEdit

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,DEdit

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 theoryEdit

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 ticketsEdit

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.

PartitionsEdit

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 footnotesEdit

  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.