Probability/Combinatorics
What is combinatorics?Edit
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 .
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
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 threesided die (with outcomes 1,2,3), followed by the flip of a twosided 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
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.
kpermutations: P(n,k)Edit
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 kpermutation 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 kpermutations, 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
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 upperleft corner contains 3 elements, while all subsets with 2 elements occupy the lowerright 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:
"nchoosek", 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 nk 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 pth 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 pth 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 nonnegative integers to some valueEdit
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 r1 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 pth subset is equal to the number of balls between the pth 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 ncombinations 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 kelement subsets of a given nelement set, which is given by
Again, let S = {1, 2, ... , n}. Since a combination is also a subset and the number of kelement 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
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 changeofbase 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 kpermutationsEdit
 Any combination of a set is also called a ______ of that set.
 A combination differs from a permutation in that elements in a ____________ have no specific ordering.
 The number of possible 2element subsets of S = {1, 2, 3, 4} is _____. (ENTER THE CORRECT INTEGER)
 List these subsets: ___________________________________________________________________
 The number of possible 2permutationsof S = {1, 2, 3, 4} is _____. (ENTER THE CORRECT INTEGER)
 List these 2permutatios: ___________________________________________________________________
Answers 

Consider the integer set S = {1, 2, ... , n}. A combination is a subset of S. We emphasize that a combination differs from a permutation in that elements in a combination have no specific ordering. The 2element subsets of S = {1, 2, 3, 4} are {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} , whereas the 2permutations of S are more numerous with (1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3) . There are therefore fewer 2element subsets of S than 2permutations of S. 
Flipping a coin and rolling a 6sided dieEdit
Consider an experiment consisting of flipping a coin and rolling a sixsided 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: ____________________________________________________________________________________
Answers 

There are two possibilities for the coin, heads or tails, and the die has six sides. The total number of outcomes for this experiment is That is, there are twelve outcomes for the roll of a die followed by the toss of a coin:

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

There are drawings and n possibilities per drawing. Using the counting principle, we conclude that the number of distinct sequences is . 
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.
Answer 

The number of possibilities is equivalent to the number of kpermutations of n elements, which is given by n!/(nk)!. 
2letter 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 2permutations 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 (___ , ___).
Answers 

The letter can pair up with , , or , but NOT . All the two letter permutation that start with are: 
Next, count and list all two letter permutations that begin with the letter :
Answers 


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

Three 2permutations of {A,B,C,D} begin with C: 
 Finally, for D, count and list:
Answers 

As before there are three: 
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
Answer 

A permutation of S is an ordered arrangement of its elements, a list without repetitions. The number of permutations of S can be computed as follows. The number of distinct possibilities for the first item is . The number of possibilities for the second item is , namely all the integers in except the first element in the list. Similarly, the number of distinct possibilities for the th item is This pattern continues until all the elements in are listed. Summarizing, we find that the total number of permutations of is factorial, . 
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}
Answer 

With elements is S, the powerset of S will have elements. The power set of S is: 
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 airdriven 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 onsite 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
 ↑ In set theory, an element is also called a "member".
 ↑ In plain English: The choice is a member of the set (which of course has 3 members.)
 ↑ wikt:Special:permalink/62799858#Verb
 ↑ #1: Assume that n! = n·(n1)! 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 kperturbations gives the correct answer when n=k, since n!/(nk)!=n!/0!=1.
 ↑ 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.