CATALAN NUMBERS

We collect various problems on Catalan numbers. Then we provide with the solutions for small numbers of integers n and try to establish a connection with the first bracket problem or second bracket problem.

First Bracket Problems [Balanced Strings of Brackets]

A string of left and right brackets is said to be balanced if each left bracket has a matching right bracket.

Problem: How many balanced strings of n left and n right brackets are there?

For the answers, click:

Second Bracket Problem [Well-parenthesized Products]

Problem 1: Suppose you have n numbers x0, x1, x2, . . . , xn and you want to multiply them together. In how many ways can you insert brackets into the string x0x1x2 . . . xn so that the order of multiplication is completely specified? Each pair of brackets should contain just two terms.

Problem 2: Suppose you have n numbers x0, x1, x2, . . . , xn and you want to add them together. In how many ways can you insert brackets into the string x0x1x2 . . . xn so that the order of addition is completely specified? Each pair of brackets should contain just two terms.

For the answers, click:

Planar Diagrams [Smiling Faces]

Consider a row of 2n dots. For each pair of dots, we join them by a unique arc from below. We call such a diagram a planer diagram.

Problem: How many ways can we join the dots with nonintersecting arcs? That is, how many such planer diagrams with nonintersecting curves?

To see some of the diagrams, click:

Stacking of Manilla Folders

Problem; How many ways to stack n (identical) manilla folders upright, nested, into your carrying bag are there?

For the answers, click:

Arrangements of Circles

How many ways to draw n nonintersecting circles with centres (can be of different radii) on the same line are there? Any such diagram is refered to as a string of circles.

To see the diagrams, click:

[Circles arrangements]

Murasaki diagrams

Given n vertical lines. A diagram obtained by joining some of the n vertical lines with horizontal lines, is called a Murasaki diagram.

How many noncrossing Murasaki diagrams with n vertical lines are there?

To see some of the diagrams, click:

Mountain Ranges [Dyck Paths, Random Walks]

Problem 1: How many mountain ranges can you draw with n upstrokes and n downstrokes are there?

Problem 2: A Dyck path from (0, 0) to (2n, 0) is lattice path with steps (1, 1) and (1, -1), never falling below the x-axis. How many such Dyck paths?

Problem 3: Consider a random walk in the plane, where the steps are from (x, y) to (x + 1, y + 1) or (x + 1, y - 1), starting at a given point. In how many ways can the random walk go from (0, 0) to (2n, 0) through the upper halfplane without crossing the x-axis?

For the answers and the diagrams, click:

Balanced Paths [Ballot Problem, Soccer Match Problem]

Problem 1: Given the origin (0, 0) and the point (n, n) in the plane, we are going to join them by a path, allowing to move a unit to the right or a unit upwards. Such a path is called balanced if it does not go above the diagonal joining (0, 0) and (n, n).

For any positive integer n, how many balanced paths are there?

Problem 2: How many lattice paths from (0, 0) to (n, n) with steps (0, 1) or (1, 0), never rising above the line y = x?

Problem 3: [Soccer match problem] In a soccer match between Teams A and B, the final score is n-all. At no time during the match was Team B in the lead. In how many different ways can the A-B scores be built up, starting at 0-0 and ending at n-n?

Problem 4:[ Ballot Problem] Suppose an election is held in which there are two candidates A and B. The final number of votes is n each. Throughout the counting of votes, A stays ahead of B. How many ways of counting there are?

Problem 5: Find the number of increasing lattice paths from (0, 0) to (n, n) that never cross, but may touch the main diagonal.

Problem 6: [Coin tossing] Suppose that a coin is tossed 2n times, coming up heads exactly n times and tails exactly n times. What is the number of sequences of tosses in which the cumulative number of heads is always at least as large as the cumulative number of tails?

For the answers and the diagrams, click:

Rooted Plane Trees [Planted Planar Trees]

Consider ``trees'' planted in the ground and living in two dimensions. These are called rooted plane trees or planted planar trees. The `dots' in the drawing below are called vertices and the lines joining the vertices are called the edges. A tree of n + 1 vertices has n edges; there are no circuits. (Here `plane' means that we distinguish between left and right.)

How many rooted plane trees (or planted planar trees) are there with n + 1 vertices and n edges?

For the answers and diagrams, click

Increasing functions

Problem 1: Let f be a function from the set of n elements {1, 2, . . . , n} to itself such that f is increasing, i.e., if i < j, then f(i) < f(j); and f(i) < i, for all i.

For any integer n, how many such functions are there?

Problem 2: How many sequences of the form 1 = a_1 < a_2 < . . . < a_n of integers are there, with a_i < i ?

Problem 3: How many n-tuples (1, a_2, . . . , a_n) are there, with a_i < i , for all i , and a_i < a_j whenever i < j ?

For the answers, click:

Tied Children with Ropes [Microscopic Organisms Problem]

Problem 1: Line up n + 1 children in a row. How many ways are there to round them with n closed ropes in such a way that there are exactly 2 groups of children inside each ropes? (This is just the second bracket problem)

Problem 2: Put n + 1 dots in a row. How many ways are there to round them with n ellipses in such a way that there are exactly 2 groups of dots inside each ellipse?

These are just the second bracket problem

For the beautiful diagrams, click

Nonintersecting Chords Problem [Hand Shaking Problem]

Problem 1: For any positive integer n, evenly distribute 2n points on the circumference of a circle. In how many ways can these 2n points be paired off as n chords where no two chords intersect?

Problem 2: There are 2n people sitting on a round table. In how many ways can they shake their hands, in pairs, without crossing the hands?

For the answers and the diagrams, click

River Systems

Consider a river system with n sources which eventually merge to form a single stream. Assuming that no more than two streams merge at any point. In how many ways that the mergers can take place.

For the answers and the diagrams, click

Full binary trees

A full binary tree is a rooted tree in which each internal vertex has exactly two children. Thus, a full binary tree with n internal vertices has 2n edges. Since a tree has one more vertex than it has edges, a full binary tree with n internal vertices has 2n+1 vertices, 2n edges and n + 1 leaves.

How many full binary trees are there with n internal vertices?

This is just the river systems!

For the answers and the diagrams, click:

Triangulations of Convex Polygon [Polygon Dissections]

In how many ways can a convex polygon with n + 1 sides be divided into triangles by non-intersecting diagonals?

For the answers and the diagrams, click

Stacking of Dominos

For any positive integer n, we are forming a stack of dominos with the first domino at (0, 0), each domino must either sit directly on one below or else overlap by half its length and the stack must be contained in the first quadrant.

For any n, how many such stacks are there?

For the answers and the diagrams, click

231-avoiding Permutations [Railway Wagons Problem]

Problem 1: How many permutations {a_1, a_2, . . . , a_n} of {1, 2, . . . , n} are there such that there does not exist i < j < k with a_k < a_i < a_j ?

Such permutation is called 231-avoiding permutation.

Problem 2: How many one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , n} are there such that there does not exist i < j < k with a_k < a_i < a_j ?

Problem 3: A railway track consists of a left track, a right track and a central track. There are n railway wagons on the left track. The wagons are moved from the left track to the right track throught the central track. It is assumed that the central track can accomodate all n of them and that they travel only from left to right (i.e., they may not be moved from the central track back to the left track.)

How many ways to move the n wagons from the left track to the right track are there?

For the answers, click

Sequences with positive partial sums

Problem 1: How many sequences a_1, a_2, . . . , a_n of integers are there, such that

Problem 2: How many n-tuples (a_1, a_2, . . . , a_n) of integers are there, such that

Problem 3: How many functions f from {1, 2, . . . , n} to {- 1, 0, . . . , n - 1} are there, such that

For the answers, click

Sequences with Non-negative Partial Sums

Problem 1: How many sequences a_1, a_2, . . . , a_n are there, such that a_i < 1 and all partial sums are nonnegative?

Problem 2: How many functions f from {1, 2, . . . , n - 1} to {1, 0, -1, . . . , -(n - 2)} are there such that

For the answers, click

Standard Young Tableaux

Problem 1: There are two rows of boxes with n boxes in each row. In how many ways can you place the numbers 1, 2, . . ., 2n in the boxes so that the numbers increase from left to right and so that each number in the bottom row is larger than the number in the box above it?

Problem 2: There are 2n people of different heights. In how many ways can these 2n people be lined up in increasing heights, in two rows of length n each, so that everyone in the second row is taller than the corresponding person in the first row?

For the answers, click

Stacking of Coins

How many ways to stack coins in the plane, the bottom row of which consisting of n consecutive coins?

For the answers and diagrams, click

Noncrossing Partitions I [Convex Hulls]

How many partitions {B_1, B_2, . . . , B_n} of {1, 2, . . . , n} are there, such that if the numbers 1, 2, . . . , n are arranged in order around a circle, then the convex hulls of the blocks B_1, B_2, . . . , B_n are pairwise disjoint?

For the answers and diagrams, click

Noncrossing Partitions II

How many noncrossing partitions {B_1, B_2, . . . , B_n} of {1, 2, . . . , n} are there, such that if a < b < c < d and a, c in B_i and b, d in B_j, then i = j ?

For the answers, click

Pairs of Permutations

How many pairs (u, v) of permutations of {1, 2, . . . , n} are there such that u and v have a total of n + 1 cycles and uv = (1, 2, . . . , n).

For the answers, click

Sequences of Pairs of Integers

Problem 1: How many sequences a_1a_2 . . . a_{2n} can be formed from the integers 1, 1, 2, 2,. . . , n, n such that the first occurrences of 1, 2, . . . , n appear in increasing order, and there is no subsequence of the form jkjk .

Problem 2: How many permutations a_1a_2 . . . a_{2n} of the multiset {1, 1, 2, 2,. . . , n, n} are there such that the first occurrences of 1, 2, . . . , n appear in increasing order, and there is no subsequence of the form jkjk .

For the answers, click

Divisible sequences

Consider the n-tuples (a_1, a_2, . . . , a_n) of integers a_i > 2 such that in the sequence 1 a_1 a_2 . . . a_n 1, each a_i divides the sum of its two neighbours; i.e., a_i | (a_{i-1} + a_{i+1}), a_0=a_{n+1}=1 .

How many such n-tuples are there?

For the answers, click