Combinations and the Binomial Coefficient

Master unordered selection using the binomial coefficient, Pascal's triangle, and combinatorial identities.

24 min read
Beginner

Introduction

So far, we've counted ordered arrangements (permutations). But what if order doesn't matter? When selecting a committee of 3 people from 10, {Alice, Bob, Carol} is the same as {Carol, Alice, Bob}. This is the realm of combinations.

Learning Objectives:

  • Understand the difference between permutations and combinations
  • Master the binomial coefficient formula
  • Apply Pascal's triangle and combinatorial identities
  • Verify calculations using Python

Permutations vs Combinations

The fundamental distinction:

  • Permutation: Order matters - ABC ≠ BAC (different arrangements)
  • Combination: Order doesn't matter - {A, B, C} = {C, A, B} (same selection)

Example 1: Card Selection

Draw 2 cards from a deck of 4 cards {A, B, C, D}:

Permutations (ordered): AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC → 12 permutations

Combinations (unordered): {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D} → 6 combinations

Notice: 12/6=212 / 6 = 2 (each combination corresponds to 2!=22! = 2 permutations)

Key Question: "Does the order matter?" If selecting a team, order doesn't matter. If assigning roles (president, VP), order matters.

The Binomial Coefficient

The number of ways to choose kk objects from nn distinct objects without regard to order is:

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

Read as "nn choose kk" or "C(n, k)".

Derivation:

  1. Permutations of kk from nn: P(n,k)=n!(n−k)!P(n,k) = \frac{n!}{(n-k)!}
  2. Each combination has k!k! orderings (overcounting by factor of k!k!)
  3. Divide by k!k! to get combinations: (nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k!(n-k)!}

Example 2: Committee Selection

Choose a committee of 3 people from 10 people. How many possible committees?

Solution:

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

Why divide by 3!3!? Each committee of {A, B, C} was counted 3!=63! = 6 times in the permutation count (ABC, ACB, BAC, BCA, CAB, CBA are all the same committee).

python
import math

def combination(n, k):
    """Calculate C(n, k) = n! / (k! * (n-k)!)"""
    return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))

# Committee of 3 from 10
n = 10
k = 3

result = combination(n, k)

print(f"C({n}, {k}) = {result}")
print(f"\nThere are {result} possible committees")

# Show calculation breakdown
numerator = math.factorial(n)
denominator = math.factorial(k) * math.factorial(n - k)

print(f"\nCalculation:")
print(f"  Numerator: {n}! = {numerator:,}")
print(f"  Denominator: {k}! × {n-k}! = {math.factorial(k)} × {math.factorial(n-k):,} = {denominator:,}")
print(f"  Result: {numerator:,} / {denominator:,} = {result}")

# Alternative: using scipy
from scipy.special import comb as scipy_comb
print(f"\nVerification with scipy: {int(scipy_comb(n, k, exact=True))}")

Symmetry Property

One of the most beautiful identities:

(nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k}

Intuition: Choosing kk objects to include is the same as choosing n−kn-k objects to exclude.

Example 3: Card Selection

From a deck of 52 cards, choose 50 cards:

(5250)=(522)=52×512=1,326\binom{52}{50} = \binom{52}{2} = \frac{52 \times 51}{2} = 1,326

Computing (5250)\binom{52}{50} directly involves huge factorials, but using symmetry, we compute (522)\binom{52}{2} instead - much easier!

python
from scipy.special import comb

# Demonstrate symmetry
n = 52

# Computing C(52, 50) directly
result1 = int(comb(n, 50, exact=True))

# Using symmetry: C(52, 50) = C(52, 2)
result2 = int(comb(n, 2, exact=True))

print(f"C({n}, 50) = {result1:,}")
print(f"C({n}, 2) = {result2:,}")
print(f"Equal: {result1 == result2}")

# Show computational advantage
print(f"\nDirect calculation of C(52, 2):")
print(f"  (52 × 51) / 2 = {52 * 51 // 2:,}")

Pascal's Triangle

Pascal's Triangle is a visual representation of binomial coefficients:

                1
              1   1
            1   2   1
          1   3   3   1
        1   4   6   4   1
      1   5  10  10   5   1
    1   6  15  20  15   6   1

Each number is (nk)\binom{n}{k} where nn is the row (starting from 0) and kk is the position (starting from 0).

Pascal's Identity:

(nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

Intuition: To choose kk from nn objects, consider object #1:

  • Include object #1: Choose k−1k-1 from remaining n−1n-1 → (n−1k−1)\binom{n-1}{k-1}
  • Exclude object #1: Choose kk from remaining n−1n-1 → (n−1k)\binom{n-1}{k}
python
from scipy.special import comb

def pascal_triangle(rows):
    """Generate Pascal's triangle"""
    for n in range(rows):
        row = [int(comb(n, k, exact=True)) for k in range(n + 1)]
        print(f"Row {n}: {row}")

print("Pascal's Triangle (first 8 rows):")
pascal_triangle(8)

# Verify Pascal's Identity: C(n,k) = C(n-1,k-1) + C(n-1,k)
n, k = 6, 3
left = int(comb(n, k, exact=True))
right = int(comb(n-1, k-1, exact=True)) + int(comb(n-1, k, exact=True))

print(f"\nVerifying Pascal's Identity for C({n}, {k}):")
print(f"  C({n}, {k}) = {left}")
print(f"  C({n-1}, {k-1}) + C({n-1}, {k}) = {int(comb(n-1, k-1, exact=True))} + {int(comb(n-1, k, exact=True))} = {right}")
print(f"  Equal: {left == right}")

The Binomial Theorem

Binomial coefficients appear in polynomial expansions:

(x+y)n=∑k=0n(nk)xn−kyk(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k

Example 4: (x+y)3(x + y)^3

(x+y)3=(30)x3+(31)x2y+(32)xy2+(33)y3(x + y)^3 = \binom{3}{0}x^3 + \binom{3}{1}x^2y + \binom{3}{2}xy^2 + \binom{3}{3}y^3

=1⋅x3+3⋅x2y+3⋅xy2+1⋅y3= 1 \cdot x^3 + 3 \cdot x^2y + 3 \cdot xy^2 + 1 \cdot y^3

The coefficients are row 3 of Pascal's Triangle: 1, 3, 3, 1

Special case: x=y=1x = y = 1

(1+1)n=∑k=0n(nk)=2n(1 + 1)^n = \sum_{k=0}^{n} \binom{n}{k} = 2^n

Interpretation: The sum of all binomial coefficients in row nn equals 2n2^n (total subsets of an nn-element set).

Key Takeaways

  1. Combination: Unordered selection, (nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k!(n-k)!}
  2. Symmetry: (nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k} (choosing vs excluding)
  3. Pascal's Identity: (nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
  4. Binomial Theorem: (x+y)n=∑(nk)xn−kyk(x+y)^n = \sum \binom{n}{k} x^{n-k} y^k
  5. Sum of row: ∑k=0n(nk)=2n\sum_{k=0}^{n} \binom{n}{k} = 2^n

Next Lesson: We'll tackle multisets and stars and bars for counting with repetition allowed!

Formula
Description
Example
$\binom{n}{k} = \frac{n!}{k!(n-k)!}$Combinations$\binom{10}{3} = 120$
$\binom{n}{k} = \binom{n}{n-k}$Symmetry$\binom{52}{50} = \binom{52}{2}$
$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$Pascal's Identity$\binom{6}{3} = \binom{5}{2} + \binom{5}{3}$
$\sum_{k=0}^{n} \binom{n}{k} = 2^n$Sum of row$1+3+3+1 = 8 = 2^3$
🎲

Combinatorics and Probability: From Counting to Inference

Master the mathematical foundations of counting, probability, and randomness. This comprehensive course bridges pure combinatorics with computational probability, covering everything from basic counting principles to advanced probabilistic methods, limit theorems, and real-world applications in algorithms, finance, and data science.