Pascal's triangle — combinatorial interpretation: Question bank

Figure 1 — the map for this whole page. Every trap below points back to one entry, one diagonal, or one symmetry of this picture. Read the two red labels first: they show how "row $n$ " runs down the triangle and "position $k$ " runs across a row. The green cell $(2 4) = 6$ is a worked reference — locate it now so the "spot the error" items feel concrete.

Figure — Pascal's triangle — combinatorial interpretation

True or false — justify

True or false: Row

n

of the triangle has exactly

n

entries.

False. Row

n

runs

k = 0, 1, \dots, n

, so it has

n + 1

entries. Off-by-one here is the root of the "sum is

2^{n}

because there are

n

entries" error.

True or false:

(0 n) = 0

because you are choosing nothing.

False. There is exactly one way to choose nothing — the empty selection — so

(0 n) = 1

. Choosing zero items is a valid, unique act, not an impossible one.

True or false:

(k n)

and

^{n} P_{k}

(the ordered-selection count,

\frac{n !}{( n - k )!}

) count the same thing whenever

k = 1

True. For a single pick there is nothing to reorder, so

^{n} P_{1} = n = (1 n)

; the

k! = 1! = 1

divisor changes nothing.

True or false: Because

(k n) = (n - k n)

, every row of Pascal's triangle is a palindrome.

True. Symmetry forces position

k

to equal position

n - k

, so reading the row left-to-right or right-to-left gives the same sequence.

True or false: The sum

\sum_{k = 0}^{n} (- 1)^{k} (k n)

equals

0

for every

n \geq 0

False. It is

0

only for

n \geq 1

. For

n = 0

the single term is

(- 1)^{0} (0 0) = 1

, not

0

— an empty set has one even-sized subset (itself) and no odd-sized ones. Figure 3 shows the cancellation for

n = 4

True or false:

(k n)

is always a whole number even though the formula divides by

k! (n - k)!

True. It counts actual subsets, which cannot be fractional; the factorials in the denominator always divide the numerator exactly.

True or false: Pascal's rule

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

still holds at the edge

k = 0

True but delicate. It reads

(0 n) = (- 1 n - 1) + (0 n - 1)

; we define

(- 1 n - 1) = 0

(no way to choose a negative amount), so it correctly gives

1

True or false: The number of even-sized subsets of a 5-element set is larger than the number of odd-sized subsets.

False. The alternating sum being

0

(for

n \geq 1

) means they are equal:

16

each, summing to

2^{5} = 32

Spot the error

(2 5) = \frac{5 !}{2 !} = 60

, so there are 60 ways to pick 2 from 5." — find the flaw.

The denominator must be

k! (n - k)! = 2! 3!

, not just

2!

. Think of listing the 5 items in a row:

5!

orders all of them, and

2!

cancels the reshuffles of the 2 you chose — but the remaining

3! = 6

reshuffles of the 3 you did not choose are still counted as different, even though "leave A, B, C behind" is one single act. Dividing by

3!

too gives the true

\frac{120}{2 \cdot 6} = 10

"To get

(2 5)

I add the two entries next to it in row 5." — what's wrong?

Pascal's rule adds the two entries in the row directly above (row 4, positions 1 and 2 →

4 + 6

), not the horizontal neighbours in the same row. Figure 2 shows one such up-arrow pair.

"Row sum is

2^{n}

, so row 3 sums to

2 \times 3 = 6

." — spot the mistake.

2^{n}

means

2

raised to

n

, i.e.

2^{3} = 8

, not

2

times

n

. Indeed

1 + 3 + 3 + 1 = 8

(2 4) = 6

counts ordered pairs like (A,B) and (B,A) separately." — correct?

No.

(2 4)

counts unordered sets, so

{A, B}

is counted once. Ordered pairs would be the permutation count

^{4} P_{2} = \frac{4 !}{2 !} = 12

, exactly

2!

times larger.

"Since choosing gets harder as

k

grows,

(k n)

increases with

k

all the way to

k = n

." — flaw?

The values rise then fall, peaking in the middle. By symmetry

(k n) = (n - k n)

, so

(n n) = 1

is as small as

(0 n) = 1

; the largest term sits at the centre.

"The Binomial Theorem is a separate fact; it has nothing to do with counting subsets." — correct?

No. Setting

x = y = 1

in $(x+y)^n$ turns the theorem into the subset-count

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

; the coefficients are the counts.

Why questions

Why do we divide by

k!

rather than

(n - k)!

when converting ordered picks to combinations?

We over-counted each chosen set once per rearrangement of its

k

members, and

k

items rearrange in

k!

ways — so

k!

is the exact over-count factor for the selection, not

(n - k)!

Why is Pascal's rule a proof about a single element rather than about factorials?

Fixing element

n

splits all subsets into two clean groups — those that include

n

and those that don't — which are disjoint and exhaustive, so the Addition Principle hands us the sum for free.

Why does "each element is in or out" give

2^{n}

and not

n^{2}

2 n

Each of the

n

elements makes an independent 2-way choice, so by the Multiplication Principle we multiply

2

by itself

n

times:

2 \times 2 \times \dots \times 2 = 2^{n}

Why does the symmetry

(k n) = (n - k n)

need no algebra?

Every act of taking a

k

-subset simultaneously leaves behind a unique

(n - k)

-subset; this is a perfect pairing of the two collections, so their counts must match.

Why does

\sum_{k = 0}^{n} (- 1)^{k} (k n) = 0

for

n \geq 1

— where does the cancellation come from?

Algebraically it is just

(1 - 1)^{n} = 0

in the Binomial Theorem (put

x = 1, y = - 1

). Combinatorially, adding an element flips every subset between "even-sized" and "odd-sized", pairing each even subset with exactly one odd subset; equal-size teams with opposite signs wipe each other out. Figure 3 draws these opposite-sign bars stacking to

0

Why are the shallow diagonals of the triangle connected to Fibonacci numbers?

Summing entries along a shallow diagonal counts subsets with "no two adjacent" constraints, and those counts satisfy the same add-the-previous-two rule that defines Fibonacci numbers. Figure 4 highlights the exact entries on each diagonal and shows their sums forming

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

Why isn't

(k n)

defined when

k > n

You cannot choose more distinct items than exist, so the count is

0

(or "undefined by the formula", since

(n - k)!

would need a factorial of a negative number).

Edge cases

What is

(0 0)

and what does it count?

It is

1

: there is exactly one way to choose nothing from nothing — the empty selection. This is why the triangle's apex (row 0) is a single

1

What is

(n n)

for any

n

, and why?

Always

1

— there is only one way to take everything, leaving nothing behind, mirroring

(0 n) = 1

by symmetry.

If you extend Pascal's rule to compute row 0, what "parents" does the lone

1

have?

It has no two entries above it; row 0 is a seed (

(0 0) = 1

) that the rule cannot generate — every other entry is built from it downward.

What does the alternating sum tell you about the empty set (the

n = 0

row)?

It equals

1

, correctly reporting that the empty set has one even-sized subset (itself, size

0

) and zero odd-sized subsets — the single case where even and odd counts differ.

For very large

n

with

k

fixed and small, does

(k n)

grow like a polynomial or exponentially in

n

Polynomially —

(k n) = \frac{n ( n - 1 ) \dots ( n - k + 1 )}{k !}

is a degree-

k

polynomial in

n

, so with

k

fixed it grows only as fast as

n^{k}

The four figures, in one glance

Figure 1 — the triangle with row/position labels and the reference cell $(2 4) = 6$ . Use it for: every "reading the triangle" and "spot the error" item.
Figure 2 — Pascal's rule as two up-arrows feeding one cell. Use it for: the "add the two above, not beside" trap.
Figure 3 — the $n = 4$ alternating sum $+ 1 - 4 + 6 - 4 + 1 = 0$ as signed bars that cancel. Use it for: the even-vs-odd subset traps.
Figure 4 — shallow diagonals highlighted, their sums giving Fibonacci $1, 1, 2, 3, 5, 8$ . Use it for: the Fibonacci connection.

Connections

Combinations and Permutations — the $^{n} P_{k}$ vs $(k n)$ traps live here.
Factorials — the source of the "which factorial do I divide by" confusion.
Addition and Multiplication Principles — every "why" answer above leans on these.
Binomial Theorem — the $x = y = 1$ trick that de-mystifies the row sum.
Hockey Stick Identity — another diagonal-pattern to stress-test your intuition.
Fibonacci numbers — the shallow-diagonal edge case.