Pascal's triangle — combinatorial interpretation: Foundations

This page is the toolbox. Before you read the parent note with confidence, you need to own every symbol it throws at you. We build each one from absolute zero: plain words first, a picture second, and a reason it exists third.

0. What is "counting a set"?

Everything below rests on one plain question: "how many things are in this collection?" So let us fix the word set first.

Figure — Pascal's triangle — combinatorial interpretation

Why the topic needs it. Pascal's triangle counts subsets — smaller bags you can pull out of a bigger bag. If you do not know that a set ignores order, you will never understand why we divide by $k!$ later.

1. The symbol $n$ and $k$ — sizes, not objects

Picture: $n$ is the number of marbles on the table; $k$ is the number in your closed fist.

Why the topic needs it. Every entry of the triangle is labelled by two numbers — which row ( $n$ ) and which position ( $k$ ). Without separating "size of pile" from "size of handful" the whole array is meaningless.

2. The factorial symbol $n!$

Before combinations can exist, we need a way to count orderings. That is what factorial does.

Picture — factorial counts arrangements in a line. Suppose 3 friends A, B, C line up for a photo. First spot: 3 choices. Once filled, second spot: 2 choices left. Last spot: 1 choice. Multiply: $3 \times 2 \times 1 = 6$ orderings.

Why the topic needs it. The combination formula is built entirely from factorials — see Factorials. And the reason we divide by $k!$ is "a handful of $k$ things can be lined up in $k!$ orders."

3. The multiplication and addition principles

These two plain rules are the engine behind both proofs in the parent note.

Picture: Multiplication is a grid — $a$ rows times $b$ columns fills $a \times b$ cells. Addition is two separate boxes you pour together, valid only when nothing is double-counted.

4. Permutation notation $^{n} P_{k}$ (ordered picks)

Picture: it is a shortened line-up — you only fill $k$ slots of the photo, not all $n$ . The falling staircase $n, n - 1, \dots$ stops after $k$ steps.

Why the topic needs it. The parent's derivation goes "count ordered first ( $^{n} P_{k}$ ), then remove the ordering." So $^{n} P_{k}$ is the intermediate step on the way to the binomial coefficient. More in Combinations and Permutations.

5. The star symbol: the binomial coefficient $(k n)$

Now we can define the hero of the whole topic.

Picture — from ordered to unordered. Take 4 items, grab 2. Ordered count $=^{4} P_{2} = 4 \times 3 = 12$ line-ups. But each set like ${A, B}$ appeared as two line-ups ( $A B$ and $B A$ ) — that is $2! = 2$ copies. Divide $12/2 = 6$ . So $(2 4) = 6$ .

Why the topic needs it. This is the number in every cell of the triangle. Everything else — the row sums, Pascal's rule, symmetry — is a statement about these numbers, so if you can read $(k n)$ you can read the whole triangle.

6. The summation symbol $\sum$

Picture: put your finger on the bottom label $k = 0$ , read off the entries left to right along a row of the triangle, and keep a running total until you reach the top label $n$ .

Why the topic needs it. The "row sum $= 2^{n}$ " and "alternating sum $= 0$ " facts are both written with $\sum$ . It is pure shorthand — but if the symbol scares you, those beautiful results become unreadable.

7. The exponent $2^{n}$

Why the topic needs it. It is the answer to "how many subsets does an $n$ -set have?" — the right-hand side of the row-sum identity.

Prerequisite map

Read it top-down: sets feed sizes and factorials; factorials plus the multiplication principle build permutations; permutations divided by orderings give the binomial coefficient; and the two counting principles plus the coefficient assemble the full triangle.

Equipment checklist

Cover the right side and test yourself — you are ready when every reveal feels obvious.

What does

{A, B}

{B, A}

tell you about sets?

They are the same set — order does not matter in a set.

What are

n

and

k

in this topic?

n

= size of the whole pile;

k

= size of the handful you grab, with

0 \leq k \leq n

Compute

4!

and state what it counts.

4! = 24

; the number of ways to line up 4 distinct objects.

What is

0!

and why?

0! = 1

— there is exactly one way to arrange nothing.

When may you use the Addition Principle?

Only when the two groups are mutually exclusive (no shared outcome), then totals add.

State

^{n} P_{k}

in factorial form.

^{n} P_{k} = \frac{n !}{( n - k )!}

, the number of ordered picks of

k

from

n

How is

(k n)

built from

^{n} P_{k}

(k n) = \frac{^{n} P _{k}}{k !}

— divide out the

k!

orderings of each handful.

Read

k = 0 \sum 3 (k 3)

aloud and give its value.

"Sum over

k

from 0 to 3 of 3-choose-

k

= 1 + 3 + 3 + 1 = 8 = 2^{3}

What real-world question does

2^{n}

answer here?

How many subsets an

n

-element set has — each element is independently in or out.

Connections

Factorials — the building block $n!$ defined in §2.
Combinations and Permutations — the $^{n} P_{k}$ vs $(k n)$ distinction (§4–5).
Addition and Multiplication Principles — the two counting laws in §3.
Binomial Theorem — where $(k n)$ reappears as coefficients.
Hockey Stick Identity — a later diagonal pattern built on these same symbols.
Fibonacci numbers — hidden in the triangle's shallow diagonals.