Math Detours · Grade 9 · Around the corner · 6

Counting balanced brackets

(()) and ()() are the two ways to balance two pairs. For three pairs there are 5, then 14, then 42. The same numbers count mountain ranges and handshakes across a table.

Name ____________________Date ____________

Tonight's idea

Brackets are balanced when every ( is closed by a later ), and every ) closes an earlier (. To test a string, read from the left, adding 1 for ( and subtracting 1 for ). The count must never drop below zero, and must end at zero. Draw the count as a path and you get a mountain range that never goes underground.

((())) (()()) (())() ()(()) ()()()
All five balanced strings with three pairs.

Let \(C_n\) be the number of balanced strings with \(n\) pairs. Then \(C_0 = 1\) (the empty string), \(C_1 = 1\), \(C_2 = 2\) and \(C_3 = 5\).

To go further without listing, look at the first bracket. Some ) closes it. So every balanced string looks like

( A ) B

where A and B are balanced strings, possibly empty. In ()(()), A is empty and B is (()). If the string has \(n\) pairs, A and B share the other \(n - 1\). When A has \(k\) pairs there are \(C_k\) choices for A and \(C_{n-1-k}\) for B. Any A goes with any B, so multiply. Then add over every split:

\(C_n = C_0C_{n-1} + C_1C_{n-2} + \cdots + C_{n-1}C_0\)

Watch one: four pairs

A and B share three pairs: 0 and 3, 1 and 2, 2 and 1, or 3 and 0.

\[C_4 = C_0C_3 + C_1C_2 + C_2C_1 + C_3C_0 = 1 \times 5 + 1 \times 2 + 2 \times 1 + 5 \times 1 = 14.\]

Check the second term. A has one pair, so A is (). B has two pairs, so B is (()) or ()(). That gives (())(()) and (())()(): two strings, as \(C_1C_2 = 2\) says.

The numbers 1, 1, 2, 5, 14, … are the Catalan numbers, named after the mathematician Eugène Catalan.

Your turn

  1. Which of these are balanced? For each one that is not, say where the test fails. (a) (()())   (b) ())(()   (c) ((())   (d) ()(())()
  2. Use the rule to find \(C_5\), then \(C_6\).
  3. 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
    Left: allowed. Right: two handshakes cross.
    Eight people sit round a table. All shake hands at once, in four pairs, and no two handshakes may cross. (a) Why can person 1 not shake hands with person 3? (b) Person 1 can shake with 2, 4, 6 or 8. Count the ways to finish in each case, and add.
  4. There are 42 balanced strings with five pairs. How many of them (a) begin with ()? (b) have their first bracket closed by the very last bracket? (c) have their first bracket closed by the sixth symbol?

Stretch: one in how many?

There are 20 ways to write three ( and three ) in a row, balanced or not. For four pairs there are 70, and for five there are 252. What fraction is balanced each time? Guess the pattern. For six pairs there are 924 arrangements. Predict \(C_6\) and compare with question 2.

Answers

  1. (a) Balanced: the count runs 1, 2, 1, 2, 1, 0. (b) Not balanced: the count runs 1, 0, −1, below zero at the third symbol. (c) Not balanced: the count ends at 1, so one ( is never closed. (d) Balanced: 1, 0, 1, 2, 1, 0, 1, 0.
  2. \(C_5 = 1 \times 14 + 1 \times 5 + 2 \times 2 + 5 \times 1 + 14 \times 1 = 42\). \(C_6 = 1 \times 42 + 1 \times 14 + 2 \times 5 + 5 \times 2 + 14 \times 1 + 42 \times 1 = 132\).
  3. (a) Person 2 would be cut off alone on one side of that handshake, with nobody to reach without crossing it. Each side needs an even number of people. (b) With 2: the other six are on one side, \(C_3 = 5\) ways. With 4: two people on one side (1 way) and four on the other (2 ways), so 2. With 6: 2 again. With 8: 5. Total \(5 + 2 + 2 + 5 = 14 = C_4\). It is the same rule: person 1's handshake splits the table the way the first bracket splits the string.
  4. (a) A is empty and B has four pairs: \(C_0C_4 = 14\). (b) B is empty and A has four pairs: \(C_4C_0 = 14\). (c) Six symbols are ( A ), so A has two pairs and B has the other two: \(C_2C_2 = 4\).

Stretch. \(\tfrac{5}{20} = \tfrac14\), \(\tfrac{14}{70} = \tfrac15\), \(\tfrac{42}{252} = \tfrac16\). With \(n\) pairs, one arrangement in \(n + 1\) is balanced. (It works for two pairs as well: 2 out of 6.) So \(C_6 = 924 \div 7 = 132\), matching the rule. The pattern holds for every \(n\), though proving it takes a cleverer argument than the one on this sheet.

← PreviousNext: Stars and bars →