# Probability/Combinatorics

## What is 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 ${\displaystyle P}$  denote prime and ${\displaystyle E}$  denote even, the figure suggests that we define the two sets, ${\displaystyle P=\{2,3,5\}}$ , and ${\displaystyle E=\{2,4\}}$  If a set has a finite number of elements[1] that number is known as the set's cardinality. Hence the cardinality of ${\displaystyle E}$  and ${\displaystyle P}$  are 3 and 2, respectively. The intersection, ${\displaystyle P\cap E=\{2\},}$  and union, ${\displaystyle P\cup E=\{2,3,4,5\},}$  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,

${\displaystyle E=\{2,4\}=\{4,2\}.}$

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 ${\displaystyle P\cup E}$  suggests that the universe for this discussion should be ${\displaystyle U=\{1,2,3,4,5\}.}$  Another important set is the empty set, ${\displaystyle \{\},}$  which contains no elements whatsoever. The empty set can also be written as ${\displaystyle \varnothing }$ .

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 ${\displaystyle S}$ , including the empty set and the set itself. The powerset of the set t ${\displaystyle \{1,2,3\}}$  is illustrated in Figure 2. For reasons that will soon become clear, the convention is to denote the powerset of ${\displaystyle S}$  as ${\displaystyle S^{2}}$ . This notation permits us to write:

${\displaystyle {\text{If }}S=\{1,2,3\},}$  ${\displaystyle {\text{then }}2^{S}=\{\{\},\{1\},\{2\},\{3\},\{1,2\},\{3,1\},\{2,3\},\{1,2,3\}\}.}$

Note that ${\displaystyle S}$  contains ${\displaystyle 3}$  elements, while its powerset contains ${\displaystyle 2^{3}=8}$  elements. The generalization to the powerset of a set with ${\displaystyle n}$  elements containing ${\displaystyle 2^{n}}$  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 ${\displaystyle (\,)}$  instead of curly brackets ${\displaystyle \{\,\}}$ , so that in contrast with the situation for set of ${\displaystyle E}$  (even) in Figure 1, these two sequences are not equal:

${\displaystyle (1,2)\neq (2,1)}$  ... or in string/word notation: ${\displaystyle 12\neq 21}$

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 ${\displaystyle (b,e,e)}$  is more efficiently expressed as ${\displaystyle {\textit {bee}}}$ . Note that repetition plays an essential role in defining a sequence:
Example: While ${\displaystyle {\textit {be}}}$  and ${\displaystyle bee}$  are pronounced the same, ${\displaystyle {\textit {be}}\neq {\textit {bee}}.}$

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 ${\displaystyle [\,].}$  Example: While ${\displaystyle \{b,e,e\}=\{e,b,e\}}$  represents the equality of two multisets, we have, ${\displaystyle [b,e,e]\neq [b,e],}$  for sequences (or ${\displaystyle {\textit {bee}}\neq {\textit {ebe}}}$  in string notation.)

## Fundamental Counting Principle

Figure 3. In set theory this is called the Cartesian product of two sets, with cardinality, ${\displaystyle {\mathcal {N}}=3\times 2}$

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 ${\displaystyle HT\neq TH}$ .

The Fundamental Rule of Counting: If a set of choices or trials, ${\displaystyle T_{1},\dots ,T_{k}}$  , could result, respectively, in ${\displaystyle n_{1},\dots ,n_{k}}$  possible outcomes, the entire set of ${\displaystyle k}$  choices or trials has ${\displaystyle n_{1}\times \cdots \times n_{k}}$  possible outcomes. (The numbers ${\displaystyle n_{1},\dots ,n_{k}}$  cannot depend on which outcomes actually occur.)

The tree diagram of Figure 3 illustrates this for ${\displaystyle k=2}$ , ${\displaystyle n_{1}=3}$ , and ${\displaystyle n_{2}=2}$ . The number of possible outcomes is ${\displaystyle {\mathcal {N}}=n_{1}\times n_{2}=6.}$  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 ${\displaystyle T_{1}}$ , where ${\displaystyle T_{1}\in \{1,2,3\}.}$ [2] The number possible outcomes for this first choice is ${\displaystyle n_{1}=3.}$  For the second choice, ${\displaystyle T_{2}\in \{A,B\},}$  and ${\displaystyle n_{2}=2.}$

### Counting the number of elements in a powerset

Let us now count the elements of a superset of set S, where S contains ${\displaystyle n}$  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 ${\displaystyle n}$  elements, iterate through each member of S and decide whether to include that element.

This procedure requires a sequence of ${\displaystyle n}$  "choices", each involving ${\displaystyle 2}$  options. This proves the statement made above that the powerset of a set with ${\displaystyle n}$  elements contains ${\displaystyle 2^{n}}$  elements.

### The counting principle misused

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 ${\displaystyle \{1,2,3\}}$ . Since these three integers are choices (decisions), it is convenient to label the choice indices with capital letters: ${\displaystyle T_{A},T_{B},T_{C}.}$

What does ${\displaystyle T_{B}=3}$  mean? It is the second choice and that choice is the integer 3. Also, if we know that ${\displaystyle T_{B}=3}$ , we also know that the first choice was ${\displaystyle T_{A}=1}$

We cannot apply the counting principle to figure 2 because ${\displaystyle n_{B}}$  depends on ${\displaystyle T_{A}.}$  In our case, ${\displaystyle T_{A}=1\Rightarrow n_{B}=3,}$  and ${\displaystyle T_{A}=2\Rightarrow n_{B}=2,}$  and ${\displaystyle T_{A}=3\Rightarrow n_{B}=1.}$  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, ${\displaystyle {\mathcal {N}}=2\times 2}$ ${\displaystyle =4,}$  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 ${\displaystyle {\mathcal {N}}=n_{A}\times n_{B}}$  cannot be used:

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

## Permutations: n!

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 ${\displaystyle AB}$ , namely: ${\displaystyle AB}$  and ${\displaystyle BA\ .}$  The 6 ways to permute the string 123 are shown in Figure 6. The formula for the number of ways to permute ${\displaystyle n}$  objects involves the factorial, which is defined as, ${\displaystyle n!=(n)(n-1)\ldots (3)(2)(1)\ .}$  There are at least three justifications for adopting the convention that, ${\displaystyle 0!=1!=1\ .}$  [4]

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

### k-permutations: P(n,k)

Figure 7: k-permutation
${\displaystyle P(4,2)}$  ${\displaystyle =4\times 3=12}$

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 ${\displaystyle 0\leq k\leq n}$ . The number of ways to do this is obviously less than or equal to ${\displaystyle n!}$ , and defines the k-permutation coefficient:

${\displaystyle P(n,k)=n(n-1)\cdots (n-k+1)={\frac {n!}{(n-k)!}}.}$

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 ${\displaystyle n_{1}=4}$ . Since they can't to repeat the song, their second (and final) choice is between three songs, with ${\displaystyle n_{1}=4.}$  Therefore there are, ${\displaystyle 4\times 3=12}$  possible outcomes, as shown in Figure 7. This result is consistent with our formula for the number of k-permutations, since ${\displaystyle P(4,2)=4!/2!=12.}$  Our goal is to prove that ${\displaystyle P(n,k)=n!/(n-k)!,}$  but first

The formula, ${\displaystyle P(n,k)=n!/(n-k)!}$  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 ${\displaystyle S=\{1,2,3\ldots ,n\}.}$  Our task is to select ${\displaystyle k}$  integers from this list, removing them one at a time without replacement. We know that ${\displaystyle k}$  decisions must be made, but how many choices were available at each decision. To that end we construct a table:

 Decision ${\displaystyle 1}$ ${\displaystyle 2}$ ${\displaystyle 3}$ ${\displaystyle \ldots }$ ${\displaystyle i}$ ${\displaystyle \ldots }$ ${\displaystyle k}$ Choices ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-2}$ ${\displaystyle \ldots }$ ${\displaystyle n-i+1}$ ${\displaystyle \ldots }$ ${\displaystyle n-k+1}$

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 ${\displaystyle i}$  choice. Therefore:

${\displaystyle P(n,k)=(n)(n-1)(n-2)\cdot \ldots \cdot (k+1)(k)\ .}$   ${\displaystyle \left({\text{or equivalently, }}P(n,k)=\prod _{\alpha =0}^{k-1}(n-\alpha )\right)}$

Simple algebra produces a more compact and easily remembered formula:

${\displaystyle P(n,k)={\frac {(n)(n-1)\ldots (n-k+1)}{1}}}$ ${\displaystyle ={\frac {(n)(n-1)\ldots (n-k+1)}{1}}\cdot {\frac {(n-k)!}{(n-k)!}}={\frac {n!}{(n-k)!}}}$

## Combinations: C(n,k)

Figure 8: ${\displaystyle C(n,k)}$  is shown for ${\displaystyle n=3,}$  and ${\displaystyle k=0,1,2,3.}$  The dotted ellipses remind us that these are sets, where order is not important.

Figure 9: combinations. ${\displaystyle {\textit {4-choose-2}}}$  ${\displaystyle =6}$

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 ${\displaystyle \{1,2,3\}.}$  The number of elements in this set is ${\displaystyle n=3.}$  From our earlier discussion of the powerset, we know that the total number of subsets is ${\displaystyle 2^{3}}$ . 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 ${\displaystyle k}$  denote the number of elements "chosen" to be in each of the 8 subsets of set ${\displaystyle S=\{1,2,3\}}$  (where the number of elements in ${\displaystyle S}$  is, ${\displaystyle n=3}$ .)

${\displaystyle {\tbinom {3}{0}}=1}$  set has ${\displaystyle k=0}$  elements. It is the empty set: ${\displaystyle \{\,\}}$ .

${\displaystyle {\tbinom {3}{1}}=3}$  sets have ${\displaystyle k=1}$  element. They are ${\displaystyle \{1\}}$ ,${\displaystyle \{2\}}$ ,and ${\displaystyle \{3\}}$ .

${\displaystyle {\tbinom {3}{2}}=3}$  sets have ${\displaystyle k=2}$  elements. They are ${\displaystyle \{2,3\}}$ ,${\displaystyle \{1,3\}}$ ,and ${\displaystyle \{1,2\}}$ .

${\displaystyle {\tbinom {3}{3}}=1}$  set has ${\displaystyle k=3}$  elements. It is the set itself: ${\displaystyle \{1,2,3\}}$ .

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:

${\displaystyle C(n,k)={\binom {n}{k}}={\frac {n!}{k!(n-k)!}}}$ ${\displaystyle ={\frac {n(n-1)\cdots (n-k+1)}{k!}}\ .}$

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

## Binomial and multinomial coefficients

The proof of our formula for ${\displaystyle {\tbinom {n}{k}}}$  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

${\displaystyle {\begin{array}{lc}(a+b)^{0}=&{\color {Red}{\boldsymbol {1}}}\\(a+b)^{1}=&{\color {Red}{\boldsymbol {1}}}a+{\color {Red}{\boldsymbol {1}}}b\\(a+b)^{2}=&{\color {Red}{\boldsymbol {1}}}a^{2}+{\color {Red}{\boldsymbol {2}}}ab+{\color {Red}{\boldsymbol {1}}}b^{2}\\(a+b)^{3}=&{\color {Red}{\boldsymbol {1}}}a^{3}+{\color {Red}{\boldsymbol {3}}}a^{2}b+{\color {Red}{\boldsymbol {3}}}ab^{2}+{\color {Red}{\boldsymbol {1}}}b^{3}\\(a+b)^{4}=&{\color {Red}{\boldsymbol {1}}}a^{4}+{\color {Red}{\boldsymbol {4}}}a^{3}b+{\color {Red}{\boldsymbol {6}}}a^{2}b^{2}+{\color {Red}{\boldsymbol {4}}}ab^{3}+{\color {Red}{\boldsymbol {1}}}b^{4}\\\end{array}}}$  ←binomial | combination→ ${\displaystyle {\begin{array}{c}{\color {Red}{\boldsymbol {1}}}={\binom {0}{0}}\\{\color {Red}{\boldsymbol {1}}}={\binom {1}{0}}\quad \quad {\color {Red}{\boldsymbol {1}}}={\binom {1}{1}}\\{\color {Red}{\boldsymbol {1}}}={\binom {2}{0}}\quad \quad {\color {Red}{\boldsymbol {2}}}={\binom {2}{1}}\quad \quad {\color {Red}{\boldsymbol {1}}}={\binom {2}{2}}\\{\color {Red}{\boldsymbol {1}}}={\binom {3}{0}}\quad \quad {\color {Red}{\boldsymbol {3}}}={\binom {3}{1}}\quad \quad {\color {Red}{\boldsymbol {3}}}={\binom {3}{2}}\quad \quad \quad \quad {\color {Red}{\boldsymbol {1}}}={\binom {3}{3}}\\{\color {Red}{\boldsymbol {1}}}={\binom {4}{0}}\quad \quad {\color {Red}{\boldsymbol {4}}}={\binom {4}{1}}\quad \quad {\color {Red}{\boldsymbol {6}}}={\binom {4}{2}}\quad \quad {\color {Red}{\boldsymbol {4}}}={\binom {4}{3}}\quad \quad {\color {Red}{\boldsymbol {1}}}={\binom {4}{4}}\\\end{array}}}$

### Special cases worth remembering

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

${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1}$  (There is only one way to pick no thing and only one way to pick all ${\displaystyle n}$  things.)
${\displaystyle {\binom {n}{1}}={\binom {n}{n-1}}=n}$  (there are n ways to pick one thing or to leave one thing out)
${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}$  (There are the same number of ways of picking ${\displaystyle k}$  of ${\displaystyle n}$  things as there are of leaving out ${\displaystyle k}$  of ${\displaystyle n}$  things)

## Partitions

### Multinomial partitioning

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 ${\displaystyle n_{1},n_{2},\ldots ,n_{r}}$  be nonnegative integers such that

${\displaystyle \sum _{p=1}^{r}n_{p}=n.}$

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

We wish to count the number of such partitions. We know that there are ${\displaystyle {\frac {n!}{n_{1}!(n-n_{1})!}}}$  ways to form the first subset. Examining our algorithm, we see that there are

${\displaystyle {\frac {(n-n_{1}-\cdots -n_{p-1})!}{n_{p}!(n-n_{1}-\cdots -n_{p})!}}}$

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

${\displaystyle {\frac {n!}{n_{1}!n_{2}!\cdots n_{r}!}}.}$

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

${\displaystyle {\frac {9!}{3!3!3!}}=1680.}$

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

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

${\displaystyle \sum _{p=1}^{r}n_{p}=n}$ .

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

${\displaystyle (n_{1},n_{2},n_{3})=(0,2,3).}$

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,

${\displaystyle {\frac {(n+r-1)!}{n!(r-1)!}}.}$

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

${\displaystyle {\frac {(n+r-1)!}{n!(r-1)!}}.}$

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 ${\displaystyle k\leq n}$ . 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

${\displaystyle {\frac {n!}{k!(n-k)!}}.}$

Again, let S = {1, 2, ... , n}. Since a combination is also a subset and the number of k-element combinations of S is ${\displaystyle {\frac {n!}{k!(n-k)!}}}$ , 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

${\displaystyle \sum _{k=0}^{n}{\frac {n!}{k!(n-k)!}}=2^{n}.}$

## Stirling's approximation for large n!

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

${\displaystyle n!\sim \left({\frac {n}{e}}\right)^{n}{\sqrt {2\pi n}}}$  as ${\displaystyle n\to \infty }$ .

The notation ${\displaystyle a(n)\sim b(n)}$  signifies that the ratio ${\displaystyle a(n)/b(n)}$  approaches 1 as ${\displaystyle n}$  tends to infinity. Taking the natural logarithm of both sides and dropping some terms yields (at the expense of accuracy), ${\displaystyle \ln(n!)\sim n\ln n-n+\ldots }$ . A change-of-base formula for logarithms permits us to write this as,

${\displaystyle \log _{b}(n!)\sim n\log _{b}n-n\log _{b}e+\ldots }$ ${\displaystyle \iff \log _{b}(n!)\sim n\log _{b}n-{\frac {n}{\ln b}}+\ldots }$

For more precision, the asymptotic expression with a precise range for ${\displaystyle n\geq 1:}$

${\displaystyle {\sqrt {2\pi n}}\ \left({\frac {n}{e}}\right)^{n}e^{\frac {1}{12n+1}}

## Exercises

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

### Combinations and k-permutations

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

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

Sampling with Replacement and Ordering

An urn contains ${\displaystyle n}$  balls numbered ${\displaystyle 1,\dots ,n}$  . 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 ${\displaystyle k}$  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 ${\displaystyle k\leq n}$ . What formula calculates the number of possible sequences that results from this experiment.

### 2-letter permutations of A,B,C,D

Begin with permutations of ${\displaystyle {A,B,C,D}}$  that start with the letter ${\displaystyle A}$ . Remember: Since the order is important, ${\displaystyle (A\,B)}$  and ${\displaystyle (B\,A)}$  are NOT the same thing! Fill in the blanks as we count and list all the 2-permutations of ${\displaystyle {A,B,C,D}}$

If the first element begins with ${\displaystyle A}$ , the second element can be ____, or ____, or _____, but not ____.

The two letter permutations that begin with ${\displaystyle A}$  are: (___ , ___), (___ , ___), and (___ , ___).

Next, count and list all two letter permutations that begin with the letter ${\displaystyle B}$ :

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

Consider the integer set ${\displaystyle S=\{1,\dots ,n\}.}$  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 ${\displaystyle n}$  possible choices. We shall use the index ${\displaystyle m}$  to count the decisions. For example, ${\displaystyle m=1}$  corresponds to the first decision (with ${\displaystyle n}$  distinct choices.) Express the number of distinct possibilities for the ${\displaystyle m}$ -th element. Hint: Your answer will be an expression involving the variables ${\displaystyle m}$  and ${\displaystyle n}$ . You may assume that ${\displaystyle m

### Set theory

The power set of S, denoted by ${\displaystyle 2^{S}}$  , is the set of all subsets of ${\displaystyle S}$  . In set theory, ${\displaystyle 2^{S}}$  represents the set of all functions ${\displaystyle S\to \{0,1\}}$  . By identifying a function in ${\displaystyle 2^{S}}$  with the corresponding preimage of one, we obtain a bijection between ${\displaystyle 2^{S}}$  and the subsets of ${\displaystyle S}$ . In particular, each function in ${\displaystyle 2^{S}}$  is the characteristic function of a subset of ${\displaystyle S}$  .

Suppose that ${\displaystyle S}$  is finite with ${\displaystyle n=|S|}$  elements. For every element of ${\displaystyle S}$  , a characteristic function in ${\displaystyle 2^{S}}$  is either 0 or 1. There are therefore ${\displaystyle 2^{n}}$  distinct characteristic functions ${\displaystyle S\to \{0,1\}}$  . Hence, the number of distinct subsets of ${\displaystyle S}$  is given by ${\displaystyle 2^{n}}$ .

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

### Lottery tickets

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

${\displaystyle {\frac {1}{10}}{\frac {1}{10}}{\frac {1}{10}}={\frac {1}{1000}}.}$

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

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

${\displaystyle {\frac {51!5!}{56!}}{\frac {1}{46}}={\frac {1}{175711536}}.}$

## References and footnotes

1. In set theory, an element is also called a "member".
2. In plain English: The choice ${\displaystyle T_{1}}$  is a member of the set ${\displaystyle \{1,2,3\}}$  (which of course has 3 members.)