CS 121 › Lesson 6 of 12

Combinatorics

Lesson 6 · OKSTEM College · AS Computer Science

The Counting Principles

RuleWhen to useFormula
Product ruleSequential independent choicesn⊂1; · n⊂2; · … · nk
Sum ruleMutually exclusive alternativesn⊂1; + n⊂2; + … + nk
Inclusion-exclusionOverlapping sets|A ∪ B| = |A| + |B| − |A ∩ B|

Example (Product): A password of 8 characters (26 letters + 10 digits, case-insensitive) has 36&sup8; ≈ 2.8 trillion possibilities.

Permutations vs Combinations

Permutation (order matters): P(n, r) = n! / (n−r)!
Combination (order doesn’t matter): C(n, r) = n! / (r! · (n−r)!)
Permutations — How many ways to arrange 3 books chosen from 7? P(7,3) = 7·6·5 = 210.
Combinations — How many 5-card hands from a 52-card deck? C(52,5) = 2,598,960.
Key question: does swapping two chosen items give a different result? If yes → permutation. If no → combination.

Binomial Theorem

The coefficients C(n, k) count the terms in an expanded binomial:

(a + b)n = ∑k=0n C(n,k) · an−k · bk

(x + 1)³ = C(3,0)x³ + C(3,1)x² + C(3,2)x + C(3,3)
           = x³ + 3x² + 3x + 1

Pascal’s triangle encodes C(n,k) values: each entry is the sum of the two above it. Row n gives the binomial coefficients for (a+b)n.

Practice Problems

1. A restaurant offers 4 starters, 6 mains, and 3 desserts. How many distinct meals (one from each)?

Product rule: 4 · 6 · 3 = 72 distinct meals.

2. A committee of 4 is chosen from 10 people. How many committees include a specific person A?

Fix A on the committee. Choose remaining 3 from the other 9: C(9,3) = 84 committees.

Knowledge Check

How many 3-character PINs exist using digits 0-9 (repetition allowed)?

That's P(10,3)/something; repetition is allowed.
Correct — each position has 10 independent choices; product rule gives 10³ = 1000.
720 = P(10,3) = 10·9·8 — that's without repetition.
120 = 5! — unrelated here.
Recap: repetition allowed + sequential choices = product rule. 10 × 10 × 10 = 10³ = 1000.

The key difference between P(n,r) and C(n,r) is

Both use factorials in their formulas.
Correct — same elements in different order count once in C, multiple times in P.
P(n,r) ≥ C(n,r) always holds (for r ≥ 2), but that's a consequence, not the definition.
Neither allows repetition in the standard formulas.
Recap: permutation = order matters (ABC ≠ BAC). Combination = order doesn't matter (ABC = BAC = CAB). C(n,r) = P(n,r) / r!

C(5, 2) equals

That's P(5,2) = 5·4 = 20.
Correct — C(5,2) = 5!/(2!·3!) = 120/12 = 10.
60 = P(5,3).
25 = 5² — unrelated.
Recap: C(5,2) = 5·4 / 2·1 = 20/2 = 10. Always divide by r! to remove ordering from P(n,r).

Inclusion-exclusion for |A ∪ B| corrects for

Elements outside both sets aren't in A ∪ B at all.
Correct — |A| + |B| double-counts |A ∩ B|; we subtract it once.
Inclusion-exclusion counts sizes, not orderings.
Empty set contributions are zero; that's not what's corrected.
Recap: |A ∪ B| = |A| + |B| − |A ∩ B|. Without subtracting the overlap, elements in both sets are counted twice.

The coefficient of x²y in (x+y)³ is

The coefficient of x³ is 1; x²y has a larger coefficient.
Correct — C(3,1) = 3. The term is C(3,1)x²y¹ = 3x²y.
6 would be C(4,2); here n=3 and k=1.
9 = 3² — unrelated.
Recap: (x+y)³ = x³ + 3x²y + 3xy² + y³. The coefficient of xn−kyk is C(n,k).

← PreviousNext →