Combinatorics • Topic 11

Pascal's Triangle

Pascal's Triangle is a geometric arrangement of binomial coefficients that reveals deep number-theoretic properties.

Construction

The triangle is built starting with a 1 at the top. Each subsequent number is the sum of the two numbers directly above it.

(k n) = (k - 1 n - 1) + (k n - 1)

Rows are indexed by $n$ (starting at 0) and positions by $k$ (starting at 0).

The sum of entries in row

n

2^{n}

k = 0 \sum n (k n) = 2^{n}

The sum of a diagonal starting from the edge equals the term "below" the last term.

i = r \sum n (r i) = (r + 1 n + 1)

Example:

1 + 2 + 3 + 4 = 10 ⟹ (1 1) + (1 2) + (1 3) + (1 4) = (2 5)

Summing the "shallow diagonals" of Pascal's Triangle yields the Fibonacci sequence (

1, 1, 2, 3, 5, 8, \dots

For a prime

p

(k n) (mod p)

depends on the base-

p

digits of

n

and

k

. If

n = n_{d} \dots n_{1} n_{0}

and

k = k_{d} \dots k_{1} k_{0}

in base

p

(k n) \equiv i = 0 \prod d (k _{i} n _{i}) (mod p)

Exercise (Problem 1)

Find the sum of the squares of the entries in row

n

\sum_{k = 0}^{n} (k n)^{2}

. (Hint: Compare coefficients of $x^{n}$ in $(1 + x)^{2 n}$ ).

Exercise (Problem 2)

Prove that

(n p ^{k})

is divisible by

p

for

0 < n < p^{k}

p

is prime.

Exercise (Problem 3)

Determine how many odd numbers are in the

n

-th row of Pascal's triangle.