Counting Principles

Overview

Counting principles provide methods to determine the number of ways events can occur, which is essential for calculating probabilities.

Fundamental Counting Principle

If there are $n_1$ ways to do task 1 AND $n_2$ ways to do task 2, then:

$$\text{Total ways} = n_1 \times n_2 \times \cdots \times n_k$$

Example

Choosing an outfit: 4 shirts and 3 pants

$$\text{Total outfits} = 4 \times 3 = 12$$

Factorial

The factorial of $n$ ($n!$) is the product of all positive integers up to $n$:

$$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$$

Special cases:

$$0! = 1, \quad 1! = 1$$

$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
10	3,628,800

Permutations

Arrangements where order matters.

All Objects

Arranging $n$ distinct objects:

$$P(n) = n!$$

Subset of Objects

Arranging $r$ objects from $n$ distinct objects:

$$P(n,r) = \frac{n!}{(n-r)!}$$

With Repetition

Arranging $n$ objects where some are identical:

$$\frac{n!}{n_1! \times n_2! \times \cdots \times n_k!}$$

Where $n_1, n_2, \ldots, n_k$ are counts of each identical type.

Combinations

Selections where order doesn't matter.

Formula

Choosing $r$ objects from $n$ distinct objects:

$$C(n,r) = \frac{n!}{r!(n-r)!} = \frac{P(n,r)}{r!}$$

Also written as:

$$\binom{n}{r} = \frac{n!}{r!(n-r)!}$$

Properties

$$C(n,0) = 1$$ $$C(n,n) = 1$$ $$C(n,r) = C(n, n-r)$$ $$C(n,r) = C(n-1,r-1) + C(n-1,r) \quad \text{(Pascal's Triangle)}$$

Comparison

Aspect	Permutation	Combination
Order	Matters	Doesn't matter
Formula	$n!/(n-r)!$	$n!/[r!(n-r)!]$
Notation	$P(n,r)$ or $_nP_r$	$C(n,r)$ or $\binom{n}{r}$
Example	Arranging books	Selecting committee

When to Use Which

Scenario	Use
Passwords, arrangements	Permutation
Committees, teams	Combination
Rankings, placements	Permutation
Lottery numbers	Combination
Seat assignments	Permutation
Card hands	Combination

Examples

Example 1: Permutation (All Objects)

Arrange 5 books on a shelf:

$$P(5) = 5! = 120 \text{ ways}$$

Example 2: Permutation (Subset)

Select president, VP, secretary from 10 candidates:

$$P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720 \text{ ways}$$

Example 3: Permutation (Repetition)

Arrange letters in "MISSISSIPPI":

11 letters: 1M, 4I, 4S, 2P

$$\text{Ways} = \frac{11!}{1! \times 4! \times 4! \times 2!} = 34{,}650$$

Example 4: Combination

Choose 3 students from 10 for a committee:

$$C(10,3) = \frac{10!}{3! \times 7!} = 120 \text{ ways}$$

Example 5: Lottery

Pick 6 numbers from 49 (order doesn't matter):

$$C(49,6) = \frac{49!}{6! \times 43!} = 13{,}983{,}816 \text{ combinations}$$ $$P(\text{winning}) = \frac{1}{13{,}983{,}816} \approx 0.0000000715$$

Example 6: Poker Hands

5 cards from 52:

$$\text{Total hands: } C(52,5) = 2{,}598{,}960$$

Flush (5 same suit):

$$4 \times C(13,5) = 5{,}148$$ $$P(\text{flush}) = \frac{5{,}148}{2{,}598{,}960} \approx 0.00198$$

Combined Problems

Cards Example

$P(\text{exactly 2 aces in 5-card hand})$:

$$\frac{C(4,2) \times C(48,3)}{C(52,5)} = \frac{6 \times 17{,}296}{2{,}598{,}960} = \frac{103{,}776}{2{,}598{,}960} \approx 0.040$$