3
$\begingroup$

I saw this question and thought that may be it is possible to prove that the $n^{\text{th}}$ Catalan number $C_n$ equals $\frac{1}{n+1}{2n\choose n}$ by taking a set $A$ of size $n+1$ and another set $B$ of size $C_n$ such that there exists a $1$-$1$ correspondence $A\times B\to T$, where $T$ is the set of subsets of $\{1,2,\ldots,2n\}$ of size $n$. I made my attempt but failed, but I am curious if there is a known bijection $A\times B\to T$ for some $A$, $B$.

I know that there are combinatorial proofs that show $C_n={2n\choose n}-{2n\choose{n-1}}$, but I want a specific proof that shows $(n+1)C_n={2n\choose n}$. Below is my attempt.

Write $[k]=\{1,2,\ldots,k\}$. Furthermore, $\binom{X}{k}$ is the set of all subsets of cardinality $k$ of a given set $X$.

Let there be $2n$ people, named, $1$, $2$, $\ldots$, $2n$. The $2n$ people are seated around a round table in the counterclockwise order. Let $\mathcal{P}$ denote the set of all pairings $$\big\{\{x_1,y_1\},\{x_2,y_2\},\ldots,\{x_n,y_n\}\big\}$$ of $[2n]$ in such a way that, when $x_i$ shakes hand with $y_i$ simultaneously for every $i\in[n]$, there are no crossing arms. Wlog, we assume that $x_i<y_i$ for each $i\in[n]$ and that $x_1<x_2<\ldots<x_n$.

Define $f:[n+1]\times\mathcal{P}\to\binom{[2n]}{n}$ as follows: $$f\Big(k,\big\{\{x_1,y_1\},\{x_2,y_2\},\ldots,\{x_n,y_n\}\big\}\Big)=\{y_1,y_2,\ldots,y_{k-1},x_k,x_{k+1},\ldots,x_n\}$$ for each $k\in[n+1]$ and $\big\{\{x_1,y_1\},\{x_2,y_2\},\ldots,\{x_n,y_n\}\big\}\in\mathcal{P}$. Well, this is where my idea fails. I was hoping that $f$ will be a bijection, but it isn't even injective.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy