## 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 ?

### 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

a_i > -1, a_1 + a_2 + . . . + a_k > 0, (1 < k < n - 1), and
a_1 + a_2 + . . . + a_n = 0 ?

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

a_i > -1, a_1 + a_2 + . . . + a_k > 0, (1 < k < n - 1), and
a_1 + a_2 + . . . + a_n = 0 ?

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

f(1) + f(2) + . . . + f(k) > 0 for all k < n; and
f(1) + f(2) + . . . + f(n) = 0 ?

### 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

f(1) + f(2) + . . . + f(k) > 0 for all k < n-1 ?

### 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