Associated Topics || Dr. Math Home || Search Dr. Math

Catalan Numbers and Probability

```Date: 05/29/2003 at 07:18:43
From: Rangarajan
Subject: Dollar Change Problem

Twenty persons want to buy a \$10 ticket each. Ten of them have a \$10
note and others have a \$20 note. The person at the ticket counter has
no money to start with. What is the probability that the person at the
ticket counter will not have a change problem?

I started with finding the number of instances where it's unfavorable,
i.e. where the ticket issuer WILL have a problem. These are when we
have series like one of the following:

a. 20,....
b. 10,20,20....
c. 10,20,10,20,20....etc.

So, the number of ways in which 'a.' can be formed is 19!/[10!*9!] and
the number of ways in which 'b.' can be formed is 17!/[9!*8!] and so
on. Hence, I finally end up getting a series which on summation will
give me the number of unfavorable situations (call it A). Then the
total no. of arrangements that can be formed is 20!/[10!*10!] (call it
B). Thus, no of favorable cases will be B-A and hence the probability
of favorable situations will be (B-A)/B.

I just want to know if there is some other route by which the process
of summation and hence the time and effort required to solve the
problem can be minimized.
```

```
Date: 05/29/2003 at 08:31:24
From: Doctor Anthony
Subject: Re: Dollar Change Problem

This is an example where we use Catalan numbers. The problem is
identical  to that of considering the number of routes from one corner
of a grid to the diagonally opposite corner such that you always
remain above the diagonal. See the example below.

Example:

A city lawyer works n blocks north and n blocks east of his place of
residence. Every day he walks 2n blocks to work.  How many routes are
possible if he never crosses (but may touch) the diagonal line from
home to office?

Each acceptable route is above the diagonal.  Each route is a
sequence of n northerly blocks and n easterly blocks.  We identify
north with +1 and east with -1.  Thus each route corresponds to a
sequence

a(1), a(2) , a(3), ......, a(2n)

of n +1's and n -1's and in order that the route not dip below the
diagonal we must have  a(1) + a(2) + a(3) + ........ + a(k) >=0

for k=0, 1, 2, ......, 2n

The number of sequences a(1), a(2), a(3), ......, a(2n) of 2n terms
that can be formed by using n +1's and n -1's whose partial sums
satisfy

a(1) + a(2) + ... + a(k) >=0  .....(1)     (k=1, 2, 3, ....,2n)

equals the nth Catalan number (see proof below)

C(n) = 1/(n+1) C(2n,n)   n >= 0

We call a sequence of n +1's and n -1's acceptable if it satisfies
(1). and unacceptable otherwise. [This is equivalent to the number of
routes consisting of n northerly blocks (+1) and n easterly blocks
(-1) that never cross the diagonal.]

Let A(n) denote the number of acceptable sequences of n +1's and
n -1's and let U(n) denote the number of unacceptable ones. The TOTAL
number of sequences of n +1's and n -1's is  (2n)!/(n!n!) = C(2n,n)

So we must have  A(n) + U(n) = C(2n,n)

and we evaluate A(n) by first evaluating U(n) and subtracting
from C(2n,n).

Consider an unacceptable sequence of n +1's and n -1's.  Because the
sequence is unacceptable there is a smallest k such that the partial
sum:

a(1) + a(2) + ... + a(k) < 0

Because k is smallest there is an equal number of +1's and -1's
preceding a(k) and we have:

a(1) + a(2) + .... + a(k-1) = 0    and   a(k) = -1

In particular, k is an ODD integer.  We now reverse the signs of each
of the first k terms; that is we replace a(i) by -a(i) for each i =
1, 2, 3, ..., k and leave unchanged the remaining terms.  The
resulting sequence

a'(1), a'(2), .. , a'(2n) is a sequence of (n+1) +1's and (n-1) -1's.

This process is reversible:

Given a sequence of (n+1) +1's and (n-1) -1's there is a first
instance when the number of +1's exceeds the number of -1's (since
there are more +1's than -1's). Reversing the +1's and -1's up to
that point results in an unacceptable sequence of n +1's and n -1's.
Thus there are as many unacceptable sequences as there are sequences
of (n+1) +1's and (n-1) -1's.  The number of sequences of (n+1) +1's
and (n-1) -1's is the number  (2n)!/[(n+1)!(n-1)!] =  C(2n,n-1)

(2n)!
Therefore  U(n) =  -----------
(n+1)!(n-1)!

(2n)!        (2n)!
Therefore   A(n) = --------- - -----------
n! n!      (n+1)!(n-1)!

(2n)!      1       1
=  -------- [ ---- - ------]
n!(n-1)!    n      (n+1)

(2n)!       1
= --------- [ -------]
n!(n-1)!    n(n+1)

1        (2n)!
=   ------ [ ---------]
(n+1)     n! n!

=  1/(n+1) C(2n,n)

and so, returning to the problem of the journeys from home to work,
the total number of acceptable routes above the diagonal is

C(n) = 1/(n+1) C(2n,n)

where C(n) means the nth Catalan number.

There are many different interpretations of this theorem.  One such
is that of the theatre tickets.

Example
-------
There are 2n people in line to get into a theatre. Admission is \$1.
Of the 2n people, n have \$1 bills and n have \$2 bills. The box
office rather foolishly begins with an empty cash register. In how
many ways can the people line up so whenever a person with a \$2 bill
buys a ticket, the box office has \$1 in order to give change.

If we regard the people as indistinguishable and identify a \$1 with a
+1 and a \$2 bill with -1, then the answer is the number

C(n) = 1/(n+1) C(2n,n)

of acceptable sequences.

The probability that there is always change available is this number
divided by the the total number of possible sequences, C(2n,n).

Therefore the required probability = 1/(n+1)

Applying this to your problem of 20 people in the queue, 10 with \$20
bills and 10 with \$10 bills, we put n=10 into the above expression and
obtain the probability  1/11.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 05/30/2003 at 08:25:48
From: Rangarajan
Subject: Thank you (Dollar Change Problem)

Sir,

Thanks a lot for your reply. Thanks to you, I have been introduced to
the new concept of Catalan numbers. The solution also was written in
an easy-to-understand format.

Once again thanks a lot. I hope you continue this great service
forever.

Yours truly,
Rangarajan V.
```
Associated Topics:
College Number Theory
High School Number Theory
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search