Theorems

Sub-Experiment Outcomes

If an experiment consists of two sub experiments where one experiment has $n$ outcomes and the other has $k$ outcomes. The total number of outcomes for the experiment are $n k$ .

Sampling Without Replacement

The number of $k$ -permutations of $n$ distinguishable objects is

(n)_{k} = n (n - 1) (n - 2) . . . (n - k + 1) = \frac{n!}{(n - k)!}

Abstract

Using k-permutations is useful when sampling without replacement. This is because a k-permutation has specific rules for sampling from a collection. This is, once an object is chosen we cannot reuse it. This affects subsequent sub experiments as the collection we are sampling from is changed every time we sample.

The number of ways to choose $k$ objects out of $n$ distinguishable objects is

(\binom{n}{k}) = \frac{(n)_{k}}{k!} = \frac{n!}{k! (n - k)!}

Abstract

The intuition for this comes from the k-combination. Since we are trying to find a subset of all all possibilities we pick one outcome $(\binom{n}{k})$ and multiply by the rest of the possibilities, $(k)_{k} = k!$ . This yields an equation which we can rearrange the terms of to find $(\binom{n}{k})$ .

(n)_{k} = (\binom{n}{k}) \cdot k!

Note

We only define $(\binom{n}{k})$ for $0 \leq k \leq n$ and 0 otherwise.

Given $m$ distinguishable objects, there are $m^{n}$ ways to choose (with replacement) an ordered sample of $n$ objects.

Examples

There are $2^{1} 0 = 1024$ possible binary sequences of length 10 (0 - 1024)

The letters A-Z can produce $26^{4}$ words of length 4

For $n$ repetitions of a sub-experiment with sample space $S = S_{1}, S_{2}, . . ., S_{m}$ the number of length $n = n_{1} + n_{2} + . . . + n_{m}$ observation sequences with $s_{i}$ appearing $n_{i}$ times is

(\binom{n}{n_{1}, . . ., n_{m}}) = \frac{n!}{n_{1}! n_{2}! . . . n_{m}!}

Abstract

This is useful when we want to track sub occurrences of the total $n$

For example, if we had binary sequences of length 8 and we wanted to find the number of sequences where "1" appears 5 times and "0" appears 3 times in each word we could use this theorem to calculate. $n_{1} = 5 n_{2} = 3 n = n_{1} + n_{2} = 8$

(\binom{8}{5, 3}) = \frac{8!}{5 \cdot 3} = 7!

Definitions

K-permutations

K-permutations refers to an ordered sequence of k distinguishable objects.

K-combination

K-combination refers to a subset of outcomes from a k-permutation. It is denoted by $(\binom{n}{k})$ and pronounced "n choose k".