Your formula for the Catalan Number can be expressed as a binomial coefficient
divided by an integer. Whenever we have a formula that calls for division by
an integer, an ideal combinatorial explanation of the formula is one that uses
the quotient principle. The purpose of this problem is to find such an
explanation using diagonal lattice paths. \({ }^{a}\) A diagonal lattice path
that never goes below the \(y\) -coordinate of its first point is called a Dyck
Path. We will call a Dyck Path from (0,0) to \((2 n, 0)\) a Catalan Path of
length \(2 n\). Thus the number of Catalan Paths of length \(2 n\) is the Catalan
Number \(C_{n}\)
(a) If a Dyck Path has \(n\) steps (each an upstep or downstep), why do the
first \(k\) steps form a Dyck Path for each nonnegative \(k \leq n ?\)
(b) Thought of as a curve in the plane, a diagonal lattice path can have many
local maxima and minima, and can have several absolute maxima and minima, that
is, several highest points and several lowest points. What is the \(y\)
-coordinate of an absolute minimum point of a Dyck Path starting at (0,0)\(?\)
Explain why a Dyck Path whose rightmost absolute minimum point is its last
point is a Catalan Path. (h)
(c) Let \(D\) be the set of all diagonal lattice paths from (0,0) to \((2 n, 0)\).
(Thus these paths can go below the \(x\) -axis.) Suppose we partition \(D\) by
letting \(B_{i}\) be the set of lattice paths in \(D\) that have \(i\) upsteps
(perhaps mixed with some downsteps) following the last absolute minimum. How
many blocks does this partition have? Give a succinct description of the block
\(B_{0} \cdot(\mathrm{h})\)
(d) How many upsteps are in a Catalan Path?
(e) We are going to give a bijection between the set of Catalan Paths and the
block \(B_{i}\) for each \(i\) between 1 and \(n\). For now, suppose the value of
\(i,\) while unknown, is fixed. We take a Catalan path and break it into three
pieces. The piece \(F\) (for "front") consists of all steps before the \(i\) th
upstep in the Catalan path. The piece \(U\) (for "up") consists of the \(i\) th
upstep. The piece \(B\) (for "back") is the portion of the path that follows the
\(i\) th upstep. Thus we can think of the path as \(F U B\). Show that the
function that takes \(F U B\) to \(B U F\) is a bijection from the set of Catalan
Paths onto the block \(B_{i}\) of the partition. (Notice that \(B\) UF can go
below the \(x\) axis.) \((\mathrm{h})\)
(f) Explain how you have just given another proof of the formula for the
Catalan Numbers.
Explanations 
Textbooks 
Flashcards 
91影视 AI 
Notes 
Study Plans 
Study Sets 
Find a degree 
Magazine 
