Course contentsShow
← Mathematics
Lesson 2606 of 3,12152. CombinatoricsFree lesson

Binomial Coefficients Modulo 2 and Sierpiński's Triangle

Color Pascal's Triangle by parity of entries and discover the fractal pattern resembling Sierpiński's Triangle.

Binomial Coefficients Modulo 2 and Sierpiński's Triangle

What You'll Learn

You'll discover how Pascal's Triangle reveals a stunning fractal pattern when you color entries based on whether they're odd or even.

The Core Idea

Take Pascal's Triangle—that familiar triangular array of binomial coefficients—and apply a simple rule: color each entry black if it's odd, white if it's even (or equivalently, examine each binomial coefficient modulo 2).

What emerges is breathtaking: the pattern resembles Sierpiński's Triangle, one of mathematics' most famous fractals.

Why This Happens

The key lies in Lucas's Theorem for prime p = 2. When you compute C(n,r) mod 2, the coefficient is odd (≡ 1 mod 2) if and only if, in binary representation, every bit of r is less than or equal to the corresponding bit of n. In other words, r is a "binary submask" of n.

This binary relationship creates the self-similar, fractal structure. Each triangular "block" of Pascal's Triangle mirrors the overall pattern at smaller scales.

The Visual Pattern

Start coloring:

  • Row 0: 1 (odd) → black
  • Row 1: 1, 1 (both odd) → black, black
  • Row 2: 1, 2, 1 (odd, even, odd) → black, white, black
  • Row 3: 1, 3, 3, 1 (all odd) → all black

As you continue, triangular "holes" (white regions) appear within larger black triangles, repeating infinitely—the hallmark of Sierpiński's Triangle.

The Connection

Powers of 2 are especially important: Row 2^k consists entirely of odd numbers (all 1s in the simplified mod-2 view), creating the boundaries of the self-similar structure.

Key Takeaway: Coloring Pascal's Triangle by parity reveals Sierpiński's Triangle, demonstrating how number theory, combinatorics, and fractal geometry beautifully intersect through the binary structure of binomial coefficients.