Catalan Numbers

**hockey777** · April 10th 2008, 02:32 AM

$\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.

**awkward** · April 11th 2008, 07:51 AM

Originally Posted by hockey777

$\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

Thread: Catalan Numbers

LinkBack

Thread Tools

Display

Catalan Numbers

Similar Math Help Forum Discussions

Random choice of numbers from series, probability the numbers are equal?

Approximation for large Catalan Numbers

Catalan's Constant

Catalan numbers and tiling

Catalan Numbers

Search Tags