intermediate 25 minutes

Counting Principles and Combinatorics

Master the fundamental counting techniques: multiplication rule, permutations, and combinations. Essential for probability calculations.

counting permutations combinations factorial combinatorics
On This Page
Advertisement

Why Counting Matters in Statistics

Many probability problems boil down to counting:

  • How many possible outcomes exist?
  • How many of those outcomes are “favorable”?
Classical Probability

P(A)=Number of favorable outcomesTotal number of outcomesP(A) = \frac{\text{Number of favorable outcomes}}{\text{Total number of outcomes}}

This lesson teaches systematic ways to count outcomes when listing them all isn’t practical.

The Fundamental Counting Principle

Multiplication Rule

If task 1 can be done in n1n_1 ways, task 2 in n2n_2 ways, …, and task kk in nkn_k ways, then all tasks together can be done in:

n1×n2×⋯×nk waysn_1 \times n_2 \times \cdots \times n_k \text{ ways}

License Plates

A license plate has 3 letters followed by 4 digits.

  • Letters: 26 choices each
  • Digits: 10 choices each

Total plates = 26×26×26×10×10×10×1026 \times 26 \times 26 \times 10 \times 10 \times 10 \times 10 = 263×10426^3 \times 10^4 = 175,760,000 possible plates

Restaurant Menu

A combo meal offers:

  • 5 appetizers
  • 8 main courses
  • 4 desserts
  • 3 drinks

Total combinations = 5×8×4×35 \times 8 \times 4 \times 3 = 480 different combos

Factorials

The factorial of n (written n!) is the product of all positive integers from 1 to n.

Factorial Definition

n!=n×(n−1)×(n−2)×⋯×2×1n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1

nn!
01 (by definition)
11
22
36
424
5120
6720
75,040
840,320
9362,880
103,628,800
Arranging Books

How many ways can you arrange 6 different books on a shelf?

  • Position 1: 6 choices
  • Position 2: 5 choices (one book used)
  • Position 3: 4 choices
  • …
  • Position 6: 1 choice

Total = 6×5×4×3×2×1=6!=6 \times 5 \times 4 \times 3 \times 2 \times 1 = 6! = 720 arrangements

Permutations

A permutation is an ordered arrangement of objects. Order matters!

Permutations of n Different Objects

P(n,n)=n!P(n,n) = n!

Permutations of r Objects from n (Without Replacement)

Permutation Formula

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

Also written as: nPr_nP_r or PrnP_r^n

Race Results

10 runners compete. How many ways can gold, silver, and bronze be awarded?

We’re selecting 3 from 10, and order matters (1st, 2nd, 3rd are different).

P(10,3)=10!(10−3)!=10!7!=10×9×8=720P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = \textbf{720}

PIN Codes

How many 4-digit PINs can be formed if digits cannot repeat?

P(10,4)=10!6!=10×9×8×7=5,040P(10,4) = \frac{10!}{6!} = 10 \times 9 \times 8 \times 7 = \textbf{5,040}

Compare: With repetition allowed, there would be 104=10,00010^4 = 10,000 PINs.

Permutations with Repetition

When some objects are identical:

Permutations with Repetition

n!n1!×n2!×⋯×nk!\frac{n!}{n_1! \times n_2! \times \cdots \times n_k!}

Where n1,n2,…,nkn_1, n_2, \ldots, n_k are the counts of identical items.

Word Arrangements

How many distinct arrangements of the letters in “STATISTICS”?

Total letters: 10

  • S appears 3 times
  • T appears 3 times
  • A appears 1 time
  • I appears 2 times
  • C appears 1 time

10!3!×3!×1!×2!×1!=3,628,8006×6×1×2×1=3,628,80072=50,400\frac{10!}{3! \times 3! \times 1! \times 2! \times 1!} = \frac{3,628,800}{6 \times 6 \times 1 \times 2 \times 1} = \frac{3,628,800}{72} = \textbf{50,400}

Combinations

A combination is a selection where order doesn’t matter.

Combination Formula

C(n,r)=(nr)=n!r!(n−r)!C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}

Also written as: nCr_nC_r or “n choose r”

Committee Selection

How many ways can a 3-person committee be formed from 10 people?

Order doesn’t matter—the set containing Amy, Ben, and Chris is the same committee regardless of selection order.

C(10,3)=(103)=10!3!×7!=10×9×83×2×1=7206=120C(10,3) = \binom{10}{3} = \frac{10!}{3! \times 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = \textbf{120}

Comparison: When to Use Which

ScenarioOrder Matters?Formula
Arranging all itemsYesn!n!
Selecting r from n, order mattersYesP(n,r)=n!(n−r)!P(n,r) = \frac{n!}{(n-r)!}
Selecting r from n, order doesn’t matterNoC(n,r)=n!r!(n−r)!C(n,r) = \frac{n!}{r!(n-r)!}
Arrangements with repetitionYesn!n1!n2!⋯\frac{n!}{n_1! n_2! \cdots}
Permutation vs Combination

From 5 people (A, B, C, D, E), select 2.

If selecting president and VP (order matters): P(5,2) = 5 × 4 = 20 Pairs: AB, BA, AC, CA, AD, DA, AE, EA, BC, CB, BD, DB, BE, EB, CD, DC, CE, EC, DE, ED

If selecting a 2-person team (order doesn’t matter): C(5,2) = (5 × 4) / (2 × 1) = 10 Teams: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE

Properties of Combinations

Symmetry Property

(nr)=(nn−r)\binom{n}{r} = \binom{n}{n-r}

Symmetry

(103)=(107)=120\binom{10}{3} = \binom{10}{7} = 120

Choosing 3 people to include is the same as choosing 7 people to exclude!

Pascal’s Identity

(nr)=(n−1r−1)+(n−1r)\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}

Sum of All Combinations

∑r=0n(nr)=2n\sum_{r=0}^{n} \binom{n}{r} = 2^n

Subsets

How many subsets does a set of 4 elements have?

(40)+(41)+(42)+(43)+(44)=1+4+6+4+1=16=24\binom{4}{0} + \binom{4}{1} + \binom{4}{2} + \binom{4}{3} + \binom{4}{4} = 1 + 4 + 6 + 4 + 1 = 16 = 2^4

Applying Counting to Probability

Poker: Full House

What’s the probability of a full house in 5-card poker?

A full house = 3 of one rank + 2 of another

Favorable outcomes:

  • Choose the rank for three-of-a-kind: (131)=13\binom{13}{1} = 13
  • Choose 3 suits from that rank: (43)=4\binom{4}{3} = 4
  • Choose the rank for the pair: (121)=12\binom{12}{1} = 12
  • Choose 2 suits from that rank: (42)=6\binom{4}{2} = 6

Favorable = 13×4×12×6=3,74413 \times 4 \times 12 \times 6 = 3,744

Total 5-card hands: (525)=52!5!×47!=2,598,960\binom{52}{5} = \frac{52!}{5! \times 47!} = 2,598,960

Probability: P(full house)=3,7442,598,960≈0.00144≈0.14%P(\text{full house}) = \frac{3,744}{2,598,960} \approx 0.00144 \approx 0.14\%

Lottery

A lottery draws 6 numbers from 1-49. You pick 6 numbers. What’s the probability of winning?

Total outcomes: (496)=49!6!×43!=13,983,816\binom{49}{6} = \frac{49!}{6! \times 43!} = 13,983,816

Favorable (your exact 6): 1

P(win)=113,983,816≈0.0000000715P(\text{win}) = \frac{1}{13,983,816} \approx 0.0000000715

That’s about 1 in 14 million!

Common Counting Mistakes

Complement Counting

For “at least one” problems, it’s often easier to count the complement.

At Least One

Roll a die 4 times. P(at least one 6)?

Direct approach: Count all ways to get 1, 2, 3, or 4 sixes… messy!

Complement approach: P(at least one 6)=1−P(no 6s)P(\text{at least one 6}) = 1 - P(\text{no 6s}) =1−(56)4=1−6251296=6711296≈0.518= 1 - \left(\frac{5}{6}\right)^4 = 1 - \frac{625}{1296} = \frac{671}{1296} \approx 0.518

Summary

In this lesson, you learned:

  • Fundamental Counting Principle: Multiply choices at each stage
  • Factorial: n!=n×(n−1)×⋯×1n! = n \times (n-1) \times \cdots \times 1
  • Permutations: Ordered arrangements; P(n,r)=n!/(n−r)!P(n,r) = n!/(n-r)!
  • Combinations: Unordered selections; C(n,r)=n!/[r!(n−r)!]C(n,r) = n!/[r!(n-r)!]
  • Key question: Does order matter?
  • Complement counting: “At least one” problems

Practice Problems

1. How many 3-letter “words” can be made from ABCDE if: a) Letters can repeat b) Letters cannot repeat

2. A committee of 4 must be chosen from 7 men and 5 women. How many committees have: a) Exactly 2 women b) At least 1 woman

3. How many distinct arrangements are there of the letters in “MISSISSIPPI”?

4. From a deck of 52 cards, what’s the probability of being dealt: a) 5 cards all of the same suit (flush, not counting straight flush) b) Exactly 3 aces in a 5-card hand

Click to see answers

1. a) With repetition: 53=5^3 = 125 b) Without repetition: P(5,3)=5×4×3=P(5,3) = 5 \times 4 \times 3 = 60

2. a) Exactly 2 women: C(5,2)×C(7,2)=10×21=C(5,2) \times C(7,2) = 10 \times 21 = 210 b) At least 1 woman = Total - All men C(12,4)−C(7,4)=495−35=C(12,4) - C(7,4) = 495 - 35 = 460

3. MISSISSIPPI has 11 letters: M(1), I(4), S(4), P(2) 11!1!×4!×4!×2!=39,916,8001×24×24×2=39,916,8001,152=34,650\frac{11!}{1! \times 4! \times 4! \times 2!} = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = \frac{39,916,800}{1,152} = \textbf{34,650}

4. a) Flush: Choose suit C(4,1)C(4,1), then 5 from that suit C(13,5)C(13,5) =4×1287=5148= 4 \times 1287 = 5148 flushes (includes straight flushes) P=5148/2,598,960≈P = 5148/2,598,960 \approx 0.198%

b) Exactly 3 aces: C(4,3)×C(48,2)=4×1128=4512C(4,3) \times C(48,2) = 4 \times 1128 = 4512 P=4512/2,598,960≈P = 4512/2,598,960 \approx 0.174%

Next Steps

Continue building your probability foundation:

Advertisement

Was this lesson helpful?

Help us improve by sharing your feedback or spreading the word.

Share on X Send Feedback