Results 1 to 2 of 2

Math Help - Catalan Numbers

  1. #1
    Junior Member
    Joined
    Feb 2008
    Posts
    48

    Catalan Numbers

    \prod_{i}^{n}(x_{1}+x_{2}+...+x_{i})

    I need to prove the number of distinct monomials appearing in the expansion is the nth catalan number.
    I tried to do induction, I don't believe it works. I need to do a bijection. I tried a lattic path which of course is a bijection because
    it's also counted by a Catalan number, but proving it is a little hard.

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by hockey777 View Post
    \prod_{i}^{n}(x_{1}+x_{2}+...+x_{i})

    I need to prove the number of distinct monomials appearing in the expansion is the nth catalan number.
    I tried to do induction, I don't believe it works. I need to do a bijection. I tried a lattic path which of course is a bijection because
    it's also counted by a Catalan number, but proving it is a little hard.
    [snip]
    The terms in the expansion of the product are of the form

    x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}

    where 0 \leq a_i \leq n-i+1 \text{ and } a_1 + a_2 + \cdots + a_n = n.

    Given an acceptable sequence a_1, a_2, \cdots , a_n, define b_i \text{ for } i = 1,2,...,n by
    b_i = \sum_{j=n-i+1}^n a_i.
    Then I think you can convince yourself that the mapping of sequences is a bijection, the b_i's are non-decreasing, b_i \leq i \text{ and } b_n = n, which is one of the characterizations of the the Catalan numbers.

    jw
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: August 29th 2011, 02:18 AM
  2. Approximation for large Catalan Numbers
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 14th 2010, 07:30 AM
  3. Catalan's Constant
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: August 11th 2010, 08:16 PM
  4. Catalan numbers and tiling
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 21st 2010, 10:50 PM
  5. Catalan Numbers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 1st 2008, 04:38 AM

Search Tags


/mathhelpforum @mathhelpforum