Counting Principle

143. Counting Principle

Count the total number of possible outcomes in a multi-step process

then the total number of outcomes is:

𝑛_{1} \cdot 𝑛_{2} \cdot \dots \cdot 𝑛_{𝑘} = \prod_{𝑖 = 1}^{𝑘} 𝑛_{𝑖}

Permutations

Number of $𝑘$ -element subsets of a given $𝑛$ -element set

(\binom{𝑛}{𝑘}) = \frac{𝑛!}{𝑘! (𝑛 - 𝑘)!}

Because $0! = 1$ :

(\binom{𝑛}{𝑛}) = 1

(\binom{𝑛}{0}) = 1

\sum_{𝑘 = 0}^{𝑛} (\binom{𝑛}{𝑘}) = (\binom{𝑛}{0}) + (\binom{𝑛}{1}) + \dots + (\binom{𝑛}{𝑛}) = 2^{𝑛}

Ordering $𝑛$ elements	$𝑛!$
Ordering $𝑘$ out of $𝑛$	$𝑃 (𝑛, 𝑘) = \frac{𝑛!}{(𝑛 - 𝑘)!}$
Choosing and ordering $𝑘$ out of $𝑚$	$(\binom{𝑚}{𝑘}) 𝑘!$
Number of subsets of $𝑛$	$2^{𝑛}$
Sequences of length $𝑛$ from $𝑚$ choices	$𝑚^{𝑛}$

Example

Find the probability that 6 rolls of a fair 6-sided die all give different numbers

𝑃 (all different) = \frac{number of favorable outcomes}{total outcomes}

Total outcomes for 6 rolls: $6^{6}$
Favorable outcomes (all numbers different): $6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

Therefore:

\frac{6!}{6^{6}}

Combination

Definition: Number of $𝑘$ -element subsets of a given $𝑛$ -element set

(\binom{𝑛}{𝑘})

Two ways to construct an ordered sequence of $𝑘$ distinct items:

𝑛 (𝑛 - 1) (𝑛 - 2) \dots (𝑛 - 𝑘 + 1) = \frac{𝑛!}{(𝑛 - 𝑘)!}

(\binom{𝑛}{𝑘}) 𝑘!