Transcript Some Parenthetical Remarks About Counting

Some
Parenthetical
Remarks
About
Counting
Dr. Henry Ricardo
Hunter College High School
October 12, 2012
Two Similar Problems
In how many ways can we
multiply n + 1 numbers
two at a time?
In how many ways can we
arrange n left
parentheses ( and n
right parentheses ) as
legitimate grouping
devices?
“Legitimate” Parenthesization
1. At any point in the process of
counting from left to right, the
number of (’s must be greater
than or equal to the number of
)’s.
2. The total number of (’s must
equal the total number of )’s.
A Partial Table of Values
n
0
1
2
3
4
5
6
7
Cn
1
1
2
5
14
42
132
429
Eugène Charles Catalan
(1814-1894)
Each arrangement of n left
parentheses ( and n right
parentheses ) is equivalent
to a “mountain path”−−a
sequence of n diagonal
upward strokes / and n
diagonal downward strokes
\.
A valid arrangement of 2n
parentheses corresponds to a
mountain path that lies on or
above the x-axis.
An invalid arrangement of
parentheses corresponds to a
mountain path that crosses the
x-axis.
A Mountain Path
Correspondence
UDUUDDUD
( ) ( ( ) ) ( )
A Mountain Path
Correspondence
UDDUUDDU
( ) ) ( ( ) ) (
A(n) = the number of all possible
mountain paths from (0, 0) to
(2n, 0)
G(n) = the number of mountain
paths from (0, 0) to
(2n, 0) which lie on or above
the x-axis
B(n) = the number of “bad”
mountain paths from
(0, 0) to (2n, 0)—those which
cross the x-axis
Then
or
A(n) = G(n) + B(n),
Cn = G(n) = A(n) − B(n)
An Equivalent Problem
Cn is the number of different
ways a convex polygon with
n + 2 sides can be cut into
triangles by connecting
vertices with straight lines.
The following hexagons
illustrate the case n = 4
Some Other Equivalent Problems
The number of ways 2n people, seated
around a round table, can shake hands
without their hands crossing
The number of mountain ranges with
n – 1 peaks such that they do not
contain three consecutive upsteps or
three consecutive downsteps
If a student wants to take n math
courses m1, m2, . . ., mn and n
computer courses c1, c2, . . ., cn , where
mi is a prerequisite for mi +1 , ci is a
prerequisite for ci + 1 , and mi is a
prerequisite for ci , then there are Cn
ordered ways the student can take
these 2n courses.
References
Fibonacci and Catalan Numbers: An Introduction by
Ralph Grimaldi (Wiley, 2012)
Catalan Numbers with Applications by Thomas Koshy
(Oxford University Press, 2009)
Enumerative Combinatorics, Volume 2 by Richard P.
Stanley (Cambridge University Press, 2001)
[Stanley has a set of exercises describing 66 problems
equivalent to the parentheses problem.]
“Catalan Addendum” by R. P. Stanley:
www.math.mit.edu/~rstan/ec/catadd.pdf
[This is a continuation of the equivalences in the last
reference.]
“Catalan Numbers” by Tom Davis:
www.geometer.org/mathcircles/catalan.pdf
*
*
*
and many, many references on the Internet