Scribd
Upload
54 views28 pages

Catalan Number

The document discusses using generating functions to solve counting problems involving choosing doughnuts and fruits with certain constraints. It shows how to derive the generating function for choosing doughnuts with k varieties and explains Taylor's theorem. It also discusses using generating functions to solve recurrences like the rabbit population problem and the Tower of Hanoi problem to find closed forms for the sequences. Finally, it mentions deriving the closed form of the Catalan numbers from its recurrence relation.

Uploaded by

clb68296
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
54 views28 pages

Catalan Number

The document discusses using generating functions to solve counting problems involving choosing doughnuts and fruits with certain constraints. It shows how to derive the generating function for choosing doughnuts with k varieties and explains Taylor's theorem. It also discusses using generating functions to solve recurrences like the rabbit population problem and the Tower of Hanoi problem to find closed forms for the sequences. Finally, it mentions deriving the closed form of the Catalan numbers from its recurrence relation.

Uploaded by

clb68296
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 28

Choosing Doughnuts

How many ways can we select n doughnuts with k varieties?

Suppose there is only chocolate doughnuts.


How many ways can we select n doughnuts?

Well there is only one way to choose zero, one, two, three, ……, chocolate doughnuts.

So the generating function for choosing chocolate doughnuts is:

The generating function for choosing doughnuts with k varieties is:

By convolution rule:
Choosing Doughnuts

The generating function for choosing doughnuts with k varieties is:

By convolution rule:

Now what? How do we obtain the answer?

Taylor’s Theorem

where f(n)(x) is the n-th derivative of f(x).


Taylor’s Theorem
Choosing Doughnuts

The generating function for choosing doughnuts with k varieties is:

……
Choosing Doughnuts

The generating function for choosing doughnuts with k varieties is:

The number of ways to choose n doughnuts with k varieties is:

This is what we get before. Now there is a general method to derive it.
Choosing Fruits

How many ways can we fill a bag with n fruits with the following constraints?

• The number of apples must be even.


• The number of bananas must be a multiple of 5.
• There can be at most four oranges.
• There can be at most one pear.

For example, there are 7 ways to form a bag with 6 fruits


Choosing Fruits
• The number of apples must be even.
• The number of bananas must be a multiple of 5.
• There can be at most four oranges.
• There can be at most one pear.

GF for apples:

GF for bananas:

GF for oranges:

GF for pears: By convolution rule

GF for fruits:
Choosing Fruits

Generating function for fruits:

How many ways can we fill a bag with n fruits with the following constraints?

The answer is exactly n+1!

We solve an impossible counting problem in a routine way…


Solving Recurrences with Generating Functions

The Rabbit Population

• A mature boy/girl rabbit pair reproduces every month.


• Rabbits mature after one month.

wn::= # newborn pairs after n months

rn::= # reproducing pairs after n months

• Start with a newborn pair: w0 =1, r0 = 0


Rabbit Populations

wn::= # newborn pairs after n months


rn::= # reproducing pairs after n months

r1 = 1

rn = rn-1 + wn-1

wn = rn-1 so

rn = rn-1 + rn-2

How many rabbits after n months?

It was Fibonacci who was studying rabbit population growth.


Fibonacci Sequence

The Fibonacci sequence we want to analyze is:

Define a generating function for this sequence:

Remember

First we want to obtain a closed form for R(x)


Generating Function for Rabbits

R(x)::= r0+r1x+r2 +r3x +…


3 x 2

-xR(x) = - r0x-r1x -r2x -…


2 3

-x R(x) =
2 -r0x -r1x -…
2 3

0
Remember
Generating Function for Rabbits

R(x)::= r0+r1x+r2 +r3x +…


3 x 2

-xR(x) = - r0x-r1x -r2x -…


2 3

-x R(x) =
2 -r0x -r1x -…
2 3

0 0 …
Generating Function for Rabbits

R(x)::= r0+r1x
-xR(x) = - r0x
-x R(x) =
2

R(x)-xR(x)-x R(x)
2 =
r0+r1x-r0x = x
Closed Form for R(x)

What is the closed form of rn?

So rn = coefficient of xn in R(x)
Closed Form for Coefficients

So rn = coefficient of xn in R(x)
Tower of Hanoi

Post #1 Post #2 Post #3

Move1,2(n)::= Move1,3(n-1);
big disk 12;
Move3,2(n-1)
http://www.mazeworks.com/hanoi/
Generating Function

sn::=# steps by Move1,2(n)


sn = 2sn-1 + 1

s0 = 0

The sequence we want to analyze is:

Define a generating function for this sequence:

First we want to obtain a closed form for S(x)


Generating Function

S(x)::= s0+ s1x+ s2x2 + s3x3+…


-2xS(x)= -2s0x-2s1x -2s2x -…
2 3

-x/(1-x)= -1¢x - 1¢x2 - 1¢x3-…


0 0 0 …

sn = 2sn-1 + 1
Closed Form for S(x)

S(x) - 2xS(x) - x/(1-x) = s0 = 0

What is the closed form of sn?

so sn = 2n - 1
Catalan Number

Catalan number can be defined recursively by

We are going to show this is equal to

You might also like