Catalan Numbers and their Properties(Part - 1)

image image

Almost all of you people are familiar or even madly in love with Fibonacci numbers.But in this post I will introduce you to another sequence of numbers known as Catalan numbers which like the Fibonacci numbers crop up in many unexpected areas!!By reading this post you'll surely be answer questions like what to do if you don't have spare change at hand and the number of possible restricted random walks :D

Definition:\textbf{Definition:}The Catalan sequence is a sequence of numbers C0,C1,......Cn,...C_0,C_1,......C_n,... where Cn=1n+1(2nn)C_n = \frac{1}{n+1}\dbinom{2n}{n} where n=0,1,2,3,...n = 0,1,2,3,... is the nn-th Catalan number, The first few Catalan numbers are :-

C0=1C_0 = 1 C1=1C_1 = 1 C2=2C_2 = 2 C3=5C_3 = 5 C4=14C_4 = 14 C5=42C_5 = 42

Theorem:\textbf{Theorem:}The number of sequences a1,a2,....,ana_1,a_2,....,a_n of 2n2n terms that can be formed by using nn number of +1+1s and nnnumber of 1-1s whose partial sums satisfy a1+a2+....+ak0a_1+a_2+....+a_k \ge 0 for k=1,2,3,4....2nk=1,2,3,4....2n equals the n-th Catalan number.

Proof:-\textbf{Proof:-}Let us call a sequence of nn number of +1+1 s and nn number of 1-1 s to be acceptable if it satisfies the above condition and unacceptable otherwise.We denote the number of acceptable sequences by AnA_n and the number of unacceptable sequences by UnU_n.

The total number of sequences of +1+1s and 1-1s can be regarded as a permutations of objects with two different types with nn different objects of one type and nn of the other.So the total number of such sequences is (2nn)=2n!n!n!\dbinom{2n}{n} = \frac {2n!}{n!n!}

Now we will calculate AnA_n by first calculating UnU_n.We will try to find a bijection. Let us consider an unacceptable sequence of nn +1+1s and nn 1-1s.So in case there must exist a smallest kk for which the partial sum a1+a2+....+aka_1+a_2+....+a_k is negative.Now as we have considered kk to the smallest of such numbers,there must be an equal number of +1+1 s and 1-1s preceding aka_k!So we must have a1+a2+...+ak1=0a_1+a_2+...+a_{k-1} = 0 and ak=1a_k = -1. So k is an odd integer!!and among the terms a1,a2,...ak)a_1,a_2,...a_k) there are k12\frac{k-1}{2} number of +1+1s and k12+1=k+12\frac{k-1}{2}+1=\frac{k+1}{2} number of 1-1s.Among the remaining terms,that is, (a{k+1},....,a{2n}) we have nk12n - \frac{k-1}{2} number of +1+1s and nk+12n - \frac{k+1}{2} number of 1-1s.

Now we have the most important part of the argument.Let us reverse the signs of each of the first kk terms.,that is we replace aia_i by ai-a_i for each i=1,2,...ki= 1,2,...k but we leave unchanged the remaining terms ak+1,....,a2na_{k+1},....,a_{2n}.Now this new sequence obtained say b1,b2,b3,...b2nb_1,b_2,b_3,...b_2n will have k+12\frac{k+1}{2} +1+1s and k12\frac{k-1}{2} 1-1s in the first kk terms and but the rest of the terms will have the same number of +1+1s and 1-1s as that of the previous sequence. So total number of +1+1s in this sequence is k+12+nk12=n+1\frac{k+1}{2}+ n- \frac{k-1}{2} = n+1. The total number of 1-1s is k12+nk+12=n1\frac{k-1}{2}+ n- \frac{k+1}{2} = n-1. So bib_i for i=1,2,...2ni = 1,2,...2n is simply a sequence of n+1n+1 +1+1s and n1n-1 1-1s!!Also we can notice further that for any sequence of n+1n+1 +1+1s and n1n-1 1-1s there must be a point where the number of +1+1s exceed the number of 1-1s .There has to be such a point as the number of +1+1s are more!!Reversing the signs upto that point results in an unacceptable sequence.So we have found a bijection between the number of unacceptable sequences and the number of sequences of (n+1)(n+1) +1+1s and (n1)(n-1) 1-1s.Clearly the number of sequences of n+1n+1 +1+1s and n1n-1 1-1s is 2n!(n+1)!(n1)!\frac{2n!}{(n+1)!(n-1)!}.By bijection, this is also equal to the number of unacceptable sequences!!!So the total number of unacceptable sequences Un=2n!(n+1)!(n1)!U_n = \frac{2n!}{(n+1)!(n-1)!}.

So the number of acceptable sequences is : An=2n!(n)!(n)!UnA_n = \frac{2n!}{(n)!(n)!} - U_n An=2n!(n)!(n)!2n!(n+1)!(n1)!A_n = \frac{2n!}{(n)!(n)!} - \frac{2n!}{(n+1)!(n-1)!} An=1(n+1)2n!(n)!(n)!A_n = \frac{1}{(n+1)} \frac{2n!}{(n)!(n)!}

So AnA_n is the nn -th Catalan number!!!

Now that you have understood this lets have some fun and play with this idea!!

APPLICATIONS:-\textbf{APPLICATIONS:-}

1.The empty cash register:-\textbf{1.The empty cash register:-}There are 2n2n people in a line to buy candy.Of the 2n2n people, nn have 50 cents and nn have 1$1\$ bills.But the shopkeeper stupidly begins with an empty cash register.In how many ways can the people line up so that whenever a person with $1\$1 buys a candy the cash register has a 50 cent piece to make change.

img img

Solution:-\textbf{Solution:-}In this case we consider that people are indistinguishable.So we simply have a sequence of nn 5050 cent pieces and n 1$1\$ bills.We can easily consider the 50$ pieces as +1+1s and the 1$ pieces as 1-1s,then this problem falls directly under the result of the above theorem.So by the given theorem the number of possible arrangements is the n-th Catalan number.1(n+1)2n!(n)!(n)!\frac{1}{(n+1)} \frac{2n!}{(n)!(n)!}.

2.Restricted Random Walks:-\textbf{2.Restricted Random Walks:-}A person works nn blocks north and nn blocks south of her residence.Every day he has 2n2n blocks to walk.How many routes are possible if he never crosses the diagonal line from home to office.

imgrandomwalk imgrandomwalk

Solution:\textbf{Solution:}Clearly each acceptable route is either above the diagonal or below the diagonal and both of these paths are symmetric.So we calculate the number of paths above the diagonal and multiply it by 2.Each route is a sequence of n northerly blocks and n easterly blocks.We identify north with +1+1 and east with 1-1.Each route corresponds to a sequence a1,a2,....,a2na_1,a_2,....,a_{2n} of n+1+1s and n 1-1s .But in order that the route not dip below the diagonal,we must have a1+a2+......+ak0a_1+a_2+......+a_k \ge 0 for k=1,2,...........2nk=1,2,...........2n.So the theorem the number of acceptable routes above the diagonal equals the n-th Catalan number and the total number of acceptable routes is 2Cn=2(n+1)2n!(n)!(n)!2C_n = \frac{2}{(n+1)} * \frac{2n!}{(n)!(n)!}.The diagram shows all the possibilities for n=5n=5.Notice that it is equal to C5=42C_5 = 42.

If you have any questions or suggestions feel free to post in the comment box.Have a nice day and stay tuned for my next post!! :)

Note by Eddie The Head
5 years, 7 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Thanks! Your notes are as awesome as ever!

Kou$htav Chakrabarty - 5 years, 7 months ago

Log in to reply

Thanks a lot!!!

Eddie The Head - 5 years, 7 months ago

Log in to reply

This really helped me

Chaidir D'dalz - 5 years, 7 months ago

Log in to reply

example 1 is best one for its marvelous application. . ..nice contribution from u.....

Koushik Chowdhury - 5 years, 4 months ago

Log in to reply

Thanks!

Eddie The Head - 5 years, 3 months ago

Log in to reply

This was really great. Well done dude :)

Ivan Sekovanić - 5 years, 4 months ago

Log in to reply

Thanks :)

Eddie The Head - 5 years, 4 months ago

Log in to reply

Hey mate, I love Your notes. They are really awesome! But sometimes I have a difficulty in digesting some things..its not your fault!..here can you tell me what is this funda of +1s and -1s?

Akhilesh Chobey - 5 years, 4 months ago

Log in to reply

It means we are trying to arrange a collection of n number of +1s and n number of -1's in such a way that the sum of any k consecutive terms starting from the first term will always be 0\ge 0 for all integer knk \le n.This happens to be the nth Catalan number.If you still have doubt feel free to ask.

Eddie The Head - 5 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...