math.wiki
Probability › Counting › Pascal's triangle
Open on the map
Algebra 2

Pascal's triangle

Working out \binom{n}{r} from factorials one number at a time is slow. Is there a way to get every combination count at once, using nothing harder than addition?

You need
CombinationsAlgebra 2CountingGrades 7 to 11SetsGrades 9 to 12
Unlocks
The binomial theoremAlgebra 2Combinatorial proof: counting one set two waysDiscrete Mathematics and Proof
Where you are 10 in Counting
Probability4
Counting10
▴ 4 aboveProbability with counting formulasThe fundamental counting principle
Pascal's triangle
PermutationsCounting with restrictions▾ Show all 10 (1 more)

Why this exists

Combinations gave a formula for the number of ways to choose r objects from n different objects:

\binom{n}{r} = \frac{n!}{r!\,(n - r)!}

The formula answers one question at a time, and each answer costs a run of multiplications and a division. But combination counts are not isolated numbers. Laid out in rows, one row for each n, they fit together so tightly that each row can be written down from the row above it by adding neighbors. No factorial is needed at all.

The arrangement is called Pascal’s triangle, after Blaise Pascal, who wrote a treatise on it in the 1650s, though mathematicians in India, Persia and China had written down versions of the table long before him. The adding rule that builds it is not a coincidence of arithmetic. It is a fact about choosing, and seeing why it holds is the main idea of this lesson. The same view of choosing also answers a question the formula alone does not: how many subsets does a set have altogether, of every size at once?

Definition

Pascal’s triangle is the table whose row n, for n = 0, 1, 2, \dots, lists the combination counts

\binom{n}{0},\ \binom{n}{1},\ \binom{n}{2},\ \dots,\ \binom{n}{n}

from left to right, each row centered under the one before. Row n has n + 1 entries. Rows are numbered from 0, so the top row, a single 1, is row 0; and the places in a row are numbered from 0 as well, so the entry in place r of row n is \binom{n}{r}, the number of r-element subsets of an n-element set.

Pascal’s rule is the statement that, for whole numbers n and r with 1 \le r \le n - 1,

\binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r}

In the triangle, the two numbers on the right sit side by side in row n - 1, just above the entry on the left.

Intuition

Here are the first five rows written as symbols. The upper number of every symbol in a row is the row number; the lower number climbs from 0 to the row number.

row 0
\binom{0}{0}
 row 1
\binom{1}{0}
\binom{1}{1}
 row 2
\binom{2}{0}
\binom{2}{1}
\binom{2}{2}
 row 3
\binom{3}{0}
\binom{3}{1}
\binom{3}{2}
\binom{3}{3}
 row 4
\binom{4}{0}
\binom{4}{1}
\binom{4}{2}
\binom{4}{3}
\binom{4}{4}
Figure 1Row n holds \binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}. Both the rows and the places in a row are counted from 0.

Now the same table as numbers, carried down to row 8:

row 0 1 row 1 1 1 row 2 1 2 1 row 3 1 3 3 1 row 4 1 4 6 4 1 row 5 1 5 10 10 5 1 row 6 1 6 15 20 15 6 1 row 7 1 7 21 35 35 21 7 1 row 8 1 8 28 56 70 56 28 8 1
Figure 2Each inner number is the sum of the two above it, here 21 + 35 = 56, which says \binom{7}{2} + \binom{7}{3} = \binom{8}{3}.

Two things leap out. Every row begins and ends with 1. And every number inside a row is the sum of the two numbers diagonally above it: in row 8, the 56 sits under the 21 and the 35 of row 7, and 21 + 35 = 56. With those two facts the triangle can be grown downward forever: put 1 at each end of the new row, and fill the inside by adding neighbors in the row above.

Why should choosing work like that? Picture a group of 8 people choosing 3 of themselves, and fix one person, say Ottilie. Each choice of 3 either includes Ottilie or does not. If it does, the other 2 come from the remaining 7 people, in \binom{7}{2} = 21 ways. If it does not, all 3 come from those 7, in \binom{7}{3} = 35 ways. No choice is in both piles and none is in neither, so the total is 21 + 35 = 56. One person, in or out, splits the count into two counts from the row above.

The same “in or out” view counts all subsets at once. For each of the n objects there are two possibilities, in the subset or out of it, so there are 2^n subsets. Sorting those same subsets by size gives the entries of row n. So every row adds up to a power of 2: 1 + 3 + 3 + 1 = 8, 1 + 4 + 6 + 4 + 1 = 16.

Results

Entries. The entry in place r of row n is \binom{n}{r}, for 0 \le r \le n.

The edges. Every row starts and ends with 1:

\binom{n}{0} = \binom{n}{n} = 1

Pascal’s rule. Each inside entry is the sum of the two entries above it: for 1 \le r \le n - 1,

\binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r}

Symmetry. Each row reads the same from either end:

\binom{n}{r} = \binom{n}{n - r}

Row sums, and all the subsets of a set. A set with n elements has 2^n subsets, counting the empty set and the whole set. Sorted by size, they give row n:

\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n

Diagonal sums. Adding down a diagonal, from the 1 at its top to any point, gives the entry just below and to the side of where the sum stopped: for whole numbers r \le n,

\begin{aligned} &\binom{r}{r} + \binom{r + 1}{r} + \cdots + \binom{n}{r} \\ &\quad = \binom{n + 1}{r + 1} \end{aligned}

Drawn on the triangle, the entries added and the answer make the shape of a hockey stick, which is the name this result often goes by.

Why it is true

Pascal’s rule, by counting. Let S be a set of n objects with n \ge 2, and pick out one object, x. Every r-element subset of S falls in exactly one of two piles.

  • The subsets that contain x. Each is x together with r - 1 other objects, chosen from the n - 1 objects other than x. So this pile holds \binom{n - 1}{r - 1} subsets.
  • The subsets that leave x out. Each is a choice of all r of its objects from the n - 1 objects other than x. So this pile holds \binom{n - 1}{r} subsets.

The piles share nothing and together hold every r-element subset, so their sizes add to \binom{n}{r}. The condition 1 \le r \le n - 1 makes both piles make sense: r - 1 is at least 0, and r is at most n - 1, the number of objects left to choose from.

Pascal’s rule, from the formula. Put the two fractions over the common denominator r!\,(n - r)!. The first has (r - 1)! below, which needs a factor of r; the second has (n - 1 - r)! below, which needs a factor of n - r:

\begin{aligned} &\binom{n - 1}{r - 1} + \binom{n - 1}{r} \\ &\quad = \frac{(n - 1)!\; r}{r!\,(n - r)!} + \frac{(n - 1)!\,(n - r)}{r!\,(n - r)!} \\ &\quad = \frac{(n - 1)!\,\big(r + (n - r)\big)}{r!\,(n - r)!} \\ &\quad = \frac{n!}{r!\,(n - r)!} \end{aligned}

The last step uses r + (n - r) = n and (n - 1)! \times n = n!.

The edges and the symmetry were shown in combinations: there is one way to choose nothing and one way to choose everything, and choosing r objects to take is the same as choosing n - r to leave. In the triangle, symmetry says each row is a palindrome.

Row sums. Building a subset of an n-element set means deciding, for each element in turn, whether it is in or out. That is n decisions with 2 options each, so by the fundamental counting principle there are 2 \times 2 \times \cdots \times 2 = 2^n subsets. Every subset has some size from 0 to n, and exactly \binom{n}{r} of them have size r, so adding the counts for each size gives the same total. The rule shows the doubling as well: when row n is built from row n - 1, every entry of row n - 1 is added into exactly two entries below it (the one down to the left and the one down to the right), so row n adds up to twice row n - 1.

Diagonal sums. Count the (r + 1)-element subsets of \{1, 2, \dots, n + 1\} by their largest element. If the largest element is m, the other r elements are chosen from 1, 2, \dots, m - 1, in \binom{m - 1}{r} ways. The largest element can be anything from m = r + 1 (the subset is \{1, \dots, r + 1\}) up to m = n + 1, so the counts for each m are \binom{r}{r}, \binom{r + 1}{r}, \dots, \binom{n}{r}. Every subset has exactly one largest element, so these add to \binom{n + 1}{r + 1}.

Worked examples

Example 1

Growing the triangle one row

Row 7 of Pascal’s triangle is 1, 7, 21, 35, 35, 21, 7, 1. Write row 8, and use it to find \binom{8}{2} and \binom{8}{6}. Check \binom{8}{2} with the formula.

Solution

Row 8 has 9 entries. The first and last are 1, because \binom{8}{0} = \binom{8}{8} = 1. Each entry in between is the sum of the two entries of row 7 above it, by Pascal’s rule:

\begin{aligned} 1 + 7 &= 8, & 7 + 21 &= 28, \\ 21 + 35 &= 56, & 35 + 35 &= 70, \\ 35 + 21 &= 56, & 21 + 7 &= 28, \\ 7 + 1 &= 8 \end{aligned}

So row 8 is 1, 8, 28, 56, 70, 56, 28, 8, 1. Places are counted from 0, so \binom{8}{2} is the third entry, 28, and \binom{8}{6} is the seventh, also 28. The two agree, as symmetry says they must: 6 = 8 - 2.

Check. \binom{8}{2} = \dfrac{8 \times 7}{2 \times 1} = 28.

Example 2

One member in or out

A chess club has 13 members, Benedikt among them, and 4 members are to be sent to a tournament. How many of the possible teams include Benedikt, and how many leave him out? Use your answers to find the number of possible teams.

Solution

A team is a set of 4 members; order does not matter.

A team that includes Benedikt still needs 3 more members, chosen from the other 12:

\binom{12}{3} = \frac{12 \times 11 \times 10}{3 \times 2 \times 1} = 220

A team that leaves him out takes all 4 members from the other 12:

\begin{aligned} \binom{12}{4} &= \frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} \\ &= \frac{11{,}880}{24} = 495 \end{aligned}

Every team either includes Benedikt or does not, never both, so the total is the sum:

\binom{13}{4} = 220 + 495 = 715

This is Pascal’s rule with n = 13 and r = 4. Check with the formula: \dfrac{13 \times 12 \times 11 \times 10}{24} = \dfrac{17{,}160}{24} = 715.

Example 3

Every possible selection

A stir-fry can be made with any selection of 6 different vegetables, from none at all to all six. How many different selections are there? How many use at least 2 vegetables?

Solution

A selection is a subset of the set of 6 vegetables. Each vegetable is either in or out, 2 options for each of 6 vegetables, so there are 2^6 = 64 selections.

Row 6 of the triangle, 1, 6, 15, 20, 15, 6, 1, sorts the same 64 selections by how many vegetables they use: 1 selection with none, 6 with one, 15 with two, and so on. The row adds up to the same total:

1 + 6 + 15 + 20 + 15 + 6 + 1 = 64

The selections with fewer than 2 vegetables are the 1 empty selection and the 6 with a single vegetable. Taking those away,

64 - 1 - 6 = 57

selections use at least 2 vegetables. Check by adding the rest of the row: 15 + 20 + 15 + 6 + 1 = 57.

Example 4

A far row without factorials

You are told that \binom{15}{6} = 5{,}005 and \binom{15}{7} = 6{,}435. Find \binom{16}{7}, \binom{16}{9} and \binom{16}{8} without any multiplication.

Solution

Pascal’s rule with n = 16 and r = 7 adds the two given entries of row 15:

\begin{aligned} \binom{16}{7} &= \binom{15}{6} + \binom{15}{7} \\ &= 5{,}005 + 6{,}435 = 11{,}440 \end{aligned}

Row 16 reads the same from either end, and 9 = 16 - 7, so \binom{16}{9} = \binom{16}{7} = 11{,}440.

For \binom{16}{8} the rule needs \binom{15}{7} and \binom{15}{8}. The second is not given, but symmetry in row 15 supplies it: \binom{15}{8} = \binom{15}{15 - 8} = \binom{15}{7} = 6{,}435. So

\binom{16}{8} = 6{,}435 + 6{,}435 = 12{,}870

Row 16 has an odd number of entries, 17, and \binom{16}{8} is the one in the middle. It sits under two equal numbers, so it is twice either of them.

Example 5

Down a diagonal

Find the sum below by adding, and then by the diagonal sum result. Explain what each term counts when 5 numbers are chosen from 1, 2, \dots, 10.

\binom{4}{4} + \binom{5}{4} + \binom{6}{4} + \binom{7}{4} + \binom{8}{4} + \binom{9}{4}
Solution

The terms are the entries in place 4 of rows 4 to 9. Reading them off the triangle and adding:

\begin{aligned} &\binom{4}{4} + \binom{5}{4} + \binom{6}{4} + \binom{7}{4} + \binom{8}{4} + \binom{9}{4} \\ &\quad = 1 + 5 + 15 + 35 + 70 + 126 \\ &\quad = 252 \end{aligned}

The diagonal sum result with r = 4 and n = 9 says the total is \binom{10}{5}, the entry below and to the right of the last term:

\begin{aligned} \binom{10}{5} &= \frac{10 \times 9 \times 8 \times 7 \times 6}{5 \times 4 \times 3 \times 2 \times 1} \\ &= \frac{30{,}240}{120} = 252 \end{aligned}

What each term counts: sort the choices of 5 numbers from 1 to 10 by the largest number chosen. If the largest is m, the other 4 come from the m - 1 numbers below it, in \binom{m - 1}{4} ways. The largest can be 5 (only \{1, 2, 3, 4, 5\}, giving \binom{4}{4} = 1), or 6, giving \binom{5}{4} = 5, and so on up to 10, giving \binom{9}{4} = 126. For example, 70 choices have 9 as their largest number.

Example 6

Even and odd

List row 5 and compare the sum of its entries in even places with the sum of its entries in odd places. Then explain by counting why a set with 5 elements has exactly as many subsets with an even number of elements as with an odd number.

Solution

Row 5 is 1, 5, 10, 10, 5, 1. The entries in places 0, 2, 4 count the subsets of sizes 0, 2, 4, and the entries in places 1, 3, 5 count those of sizes 1, 3, 5:

\begin{aligned} \binom{5}{0} + \binom{5}{2} + \binom{5}{4} &= 1 + 10 + 5 = 16 \\ \binom{5}{1} + \binom{5}{3} + \binom{5}{5} &= 5 + 10 + 1 = 16 \end{aligned}

Each is half of the row sum 2^5 = 32.

The reason does not depend on the numbers. Fix one element of the set, e. Match every subset with the subset you get by switching e: add e if it is missing, remove it if it is there. Switching twice gets back where you started, so the subsets fall into pairs, and the two subsets in a pair differ in size by exactly 1. So in every pair one subset has even size and the other odd size. Pairs share no subset and cover all of them, so the even-sized and odd-sized subsets are equally many. The argument works for any set with at least one element, since all it needs is an e to switch.

Boundaries

Rows and places start at 0. The top 1 is row 0 and the first entry of every row is place 0. The entry in the fourth place of row 9, counting the first entry as the first, is \binom{9}{3}, not \binom{9}{4}.

Pascal’s rule is for inside entries. It holds for 1 \le r \le n - 1. The two 1’s at the ends of a row are not sums of two entries above; they are set by \binom{n}{0} = \binom{n}{n} = 1. Some books extend the rule to the ends by agreeing that \binom{n}{r} = 0 when r < 0 or r > n, which treats the blank space outside the triangle as zeros. That is a convention chosen so the rule keeps working, not a count of anything.

The objects must be different. Like every entry of the triangle, the subset count 2^n is for n distinct objects. A bowl of 4 identical apples offers 5 possible selections (take 0, 1, 2, 3 or 4 apples), not 2^4 = 16.

The count 2^n includes the empty set and the whole set. If a question excludes “none” or “all”, take them away: a set of n elements has 2^n - 1 non-empty subsets and 2^n - 2 that are neither empty nor the whole set.

Even equals odd needs at least one element. A set with no elements has one subset, the empty set, whose size 0 is even, and no odd-sized subsets. The switching argument has no element to switch.

The triangle is slow for a far entry. To reach \binom{40}{6} by adding, you would build forty rows. The triangle is the better tool when many neighboring counts are needed, or when a count is wanted from counts already known; for a single distant entry, the formula is faster.

Where this goes next

The rows of Pascal’s triangle are the coefficients of powers of a sum: row 3, 1, 3, 3, 1, is the pattern in (a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3. Why choosing produces those coefficients is the subject of the binomial theorem, and the row sums 2^n come back there as the case a = b = 1. Seen as a rule that produces each row from the one before, the triangle is a recurrence, and its second diagonal, 1, 3, 6, 10, \dots, is the sequence of triangular numbers. The set of all 2^n subsets of a set is called its power set. Ratios of entries of the triangle give the chances in probability with counting formulas, and counting a set by splitting it into piles that do not overlap, the idea behind Pascal’s rule, runs through all of counting.

Exercises

Reading and building the triangle

  1. Row 8 is 1, 8, 28, 56, 70, 56, 28, 8, 1. Write row 9.
  2. Use row 9 to find \binom{9}{3} and \binom{9}{6}.
  3. Write row 10 and find the sum of its entries.
  4. Which entry of row 11 is \binom{11}{2}? Find it from row 10, and say what it counts.

Using Pascal’s rule

  1. Write \binom{17}{5} as the sum of two entries of row 16, find those two entries, and so find \binom{17}{5}.
  2. You are told that \binom{20}{8} = 125{,}970 and \binom{20}{9} = 167{,}960. Find \binom{21}{9} and \binom{21}{12}.
  3. You are told that \binom{17}{7} = 19{,}448 and \binom{18}{7} = 31{,}824. Find \binom{17}{6}.
  4. Fill in the blank with a single combination symbol: \binom{n}{r} + \binom{n}{r + 1} = \underline{\quad}, for 0 \le r \le n - 1. Test your answer with n = 9 and r = 3.

All the subsets

  1. How many subsets does \{p, q, r, s, t, u, v\} have? How many of them have exactly 3 elements?
  2. A set has 512 subsets. How many elements does it have, and how many of its subsets have exactly 2 elements?
  3. A phone case can be decorated with any selection of 5 different charms, including none. How many selections are there? How many use at least 2 charms?
  4. A stage has a row of 10 lamps, each either on or off. In how many patterns are at most 3 lamps on?
  5. Find the sum of row 12. What does that sum, minus the two 1’s at the ends, count for a set of 12 elements?

Patterns in the triangle

  1. Find \binom{3}{3} + \binom{4}{3} + \binom{5}{3} + \cdots + \binom{10}{3} with one combination symbol, and check by adding.
  2. Use the diagonal sum result with r = 1 to find 1 + 2 + 3 + \cdots + 20.
  3. The diagonal 1, 3, 6, 10, 15, \dots starts at \binom{2}{2} and runs down the triangle. These are the triangular numbers, and the k-th one is \binom{k + 1}{2}. Find the 12th.
  4. Find the sum of row 11. How many subsets of an 11-element set have an even number of elements?

Reasoning

  1. Prove Pascal’s rule from the factorial formula, and say where the condition 1 \le r \le n - 1 is used.
  2. Explain why every row of Pascal’s triangle reads the same from left to right as from right to left.
  3. Use Pascal’s rule, without the formula 2^n, to explain why each row of the triangle adds up to twice the row above it.
  4. Explain why, in every row n \ge 1, the entries in even places add up to 2^{n - 1}.
  5. A group has n girls and n boys. Count the ways to choose 2 people from the group in two ways to explain why \binom{2n}{2} = 2\binom{n}{2} + n^2, and check it for n = 5.
Answers
  1. 1, 9, 36, 84, 126, 126, 84, 36, 9, 1. The ends are 1, and each inside entry adds two neighbors of row 8: 1 + 8 = 9, 8 + 28 = 36, 28 + 56 = 84, 56 + 70 = 126, then the same sums in reverse.
  2. Both are 84. \binom{9}{3} is in place 3 (the fourth entry) and \binom{9}{6} in place 6 (the seventh). Check: \dfrac{9 \times 8 \times 7}{6} = 84.
  3. 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, with sum 1{,}024 = 2^{10}. From row 9: 1 + 9 = 10, 9 + 36 = 45, 36 + 84 = 120, 84 + 126 = 210, 126 + 126 = 252.
  4. 55, the entry in place 2 (the third entry). By Pascal’s rule \binom{11}{2} = \binom{10}{1} + \binom{10}{2} = 10 + 45 = 55. It counts the 2-element subsets of an 11-element set, for example the handshakes when 11 people each shake hands once with each other.
  5. 6{,}188. \binom{17}{5} = \binom{16}{4} + \binom{16}{5}, with \binom{16}{4} = \dfrac{16 \times 15 \times 14 \times 13}{24} = 1{,}820 and \binom{16}{5} = \dfrac{524{,}160}{120} = 4{,}368. So 1{,}820 + 4{,}368 = 6{,}188.
  6. Both are 293{,}930. By Pascal’s rule \binom{21}{9} = \binom{20}{8} + \binom{20}{9}, and 125{,}970 + 167{,}960 = 293{,}930. Then \binom{21}{12} = \binom{21}{9} by symmetry, since 12 = 21 - 9.
  7. 12{,}376. Pascal’s rule says \binom{18}{7} = \binom{17}{6} + \binom{17}{7}, so \binom{17}{6} = 31{,}824 - 19{,}448 = 12{,}376.
  8. \binom{n + 1}{r + 1}. The two entries sit side by side in row n, and the entry below them is in row n + 1, place r + 1. With n = 9, r = 3: 84 + 126 = 210 = \binom{10}{4}.
  9. 128 subsets, 35 of them with 3 elements. There are 2^7 = 128 subsets, and \binom{7}{3} = \dfrac{7 \times 6 \times 5}{6} = 35.
  10. 9 elements, and 36 subsets with 2 elements. 2^9 = 512, and \binom{9}{2} = \dfrac{9 \times 8}{2} = 36.
  11. 32 selections, 26 with at least 2 charms. 2^5 = 32, and taking away the 1 empty selection and the 5 single charms leaves 32 - 1 - 5 = 26.
  12. 176. A pattern is fixed by which lamps are on. Using row 10: \binom{10}{0} + \binom{10}{1} + \binom{10}{2} + \binom{10}{3}, which is 1 + 10 + 45 + 120 = 176.
  13. The sum is 2^{12} = 4{,}096. Taking off the two 1’s, which count the empty set and the whole set, leaves 4{,}094: the number of subsets that are neither empty nor the whole set.
  14. \binom{11}{4} = 330. The diagonal sum with r = 3 and n = 10. Adding: 1 + 4 + 10 + 20 + 35 is 70, and 70 + 56 + 84 + 120 = 330.
  15. 210. Since \binom{k}{1} = k, the sum is \binom{1}{1} + \binom{2}{1} + \cdots + \binom{20}{1}, which by the diagonal sum is \binom{21}{2}, and \dfrac{21 \times 20}{2} = 210.
  16. 78. The 12th is \binom{13}{2} = \dfrac{13 \times 12}{2} = 78.
  17. The sum is 2^{11} = 2{,}048, and 1{,}024 subsets have an even number of elements: by Example 6, even and odd sizes are equally many, so each is half of 2{,}048.
  18. Over the common denominator r!\,(n - r)!, the sum \binom{n - 1}{r - 1} + \binom{n - 1}{r} becomes \dfrac{(n - 1)!\,r + (n - 1)!\,(n - r)}{r!\,(n - r)!}, which is \dfrac{(n - 1)!\,n}{r!\,(n - r)!} = \dfrac{n!}{r!\,(n - r)!}. The condition makes every factorial a factorial of a whole number: r \ge 1 makes (r - 1)! meaningful, and r \le n - 1 makes (n - 1 - r)! meaningful.
  19. Place r of row n holds \binom{n}{r}, and the place the same distance from the right end is place n - r, holding \binom{n}{n - r}. These are equal because choosing r objects to take from n is the same as choosing the n - r to leave: each choice is matched with exactly one leftover set.
  20. By Pascal’s rule each inside entry of row n is the sum of the two entries above it, and each end 1 equals the end 1 above it. Adding up row n therefore adds up entries of row n - 1, and each entry of row n - 1 appears exactly twice: once in the entry below it to the left and once in the entry below it to the right (an end 1 of row n - 1 is counted once in an end of row n and once in the entry next to it). So row n adds to twice row n - 1.
  21. Row n adds up to 2^n, the number of subsets of an n-element set. The entries in even places count the subsets of even size. For n \ge 1 there is an element to switch, and switching it pairs every even-sized subset with an odd-sized one, as in Example 6. So the even-sized subsets are half of all of them: \dfrac{2^n}{2} = 2^{n - 1}.
  22. Directly, 2 people from 2n can be chosen in \binom{2n}{2} ways. Sorted by who is chosen: two girls in \binom{n}{2} ways, two boys in \binom{n}{2} ways, or one girl and one boy in n \times n = n^2 ways. Every pair is of exactly one kind, so \binom{2n}{2} = 2\binom{n}{2} + n^2. For n = 5: \binom{10}{2} = 45 and 2 \times 10 + 25 = 45.
kg1128 · updated 2026-10-19 · CC-BY-SA-4.0