Course contentsShow
← Computer Science
Lesson 104 of 2,8722. Discrete Mathematics for CSFree lesson

Binomial Coefficients and Pascal's Triangle

Explore properties of binomial coefficients including symmetry, recurrence relations, and Pascal's identity.

Binomial Coefficients and Pascal's Triangle

What you'll learn: You'll discover the beautiful patterns hidden in binomial coefficients and how Pascal's Triangle organizes them into a simple, powerful structure.

What Are Binomial Coefficients?

Binomial coefficients, written as C(n, k) or "n choose k", tell you how many ways you can select k items from n items (combinations). For example, C(5, 2) = 10 means there are 10 ways to choose 2 items from 5.

Pascal's Triangle: A Visual Tool

Pascal's Triangle arranges binomial coefficients in rows:

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
   1 5 10 10 5 1

Each number is the sum of the two numbers directly above it. Row n contains the values C(n, 0), C(n, 1), ..., C(n, n).

Key Properties

1. Symmetry: C(n, k) = C(n, n-k)
Choosing k items is the same as choosing which n-k items to leave out. In the triangle, each row is symmetric.

2. Pascal's Identity (Recurrence Relation): C(n, k) = C(n-1, k-1) + C(n-1, k)
This explains how to build the triangle: each entry equals the sum of the two entries above it. This recurrence relation lets you compute binomial coefficients efficiently without calculating large factorials.

3. Boundary Conditions: C(n, 0) = 1 and C(n, n) = 1
There's exactly one way to choose nothing or everything (the edges of the triangle).

Key Takeaway: Pascal's Triangle elegantly displays binomial coefficients, where symmetry and simple addition rules (Pascal's identity) reveal deep combinatorial patterns that power efficient computation and proof by induction.