# Catalan Numbers

• Apr 10th 2008, 02:32 AM
hockey777
Catalan Numbers
$\displaystyle \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.

http://i220.photobucket.com/albums/d...sc0054cf40.jpg
• Apr 11th 2008, 07:51 AM
awkward
Quote:

Originally Posted by hockey777
$\displaystyle \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

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

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

Given an acceptable sequence $\displaystyle a_1, a_2, \cdots , a_n$, define $\displaystyle b_i \text{ for } i = 1,2,...,n$ by
$\displaystyle 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 $\displaystyle b_i's$ are non-decreasing, $\displaystyle b_i \leq i \text{ and } b_n = n$, which is one of the characterizations of the the Catalan numbers.

jw
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}