3
$\begingroup$

In the classical problem of bracketing $n$ numbers, I know the response is $C_{n-1}$. I find this $$C_{n-1}=\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^{i+1}\binom{n-i}{i}C_{n-1-i}$$ but I can't prove that. Can someone help me? Regards.

$\endgroup$
3
  • 1
    $\begingroup$ $C_{n-1}$ counts the triangulations of a given $\left(n+1\right)$-gon $N$. We say that a vertex $v$ of $N$ is an ear-vertex of a triangulation $T$ if no diagonal of $T$ contains $v$. Then, every triangulation has at least one ear-vertex (why?), and the ear-vertices of a given triangulation form a lacunar subset of the set of all vertices (where "lacunar" means that it contains no two adjacent vertices). For every nonnegative integer $i$, there are precisely $\binom{n-i}{i}$ lacunar subsets of the set of all vertices of $N$, and if $L$ is any such subset, then there exist precisely ... $\endgroup$ Dec 26 '14 at 18:04
  • 1
    $\begingroup$ ... $C_{n-1-i}$ triangulations of $N$ for which all elements of $L$ are ear-vertices (but we allow other ear-vertices too) (because in effect we are triangulating an $\left(n+1-i\right)$-gon). Now the claim follows from inclusion-exclusion. I hope this proof is correct, as I have not checked my count of lacunar subsets... There is likely a clearer way to write up this proof using one of the less geometric interpretations of Catalan numbers (Dyck paths or trees). $\endgroup$ Dec 26 '14 at 18:05
  • $\begingroup$ For the record, this is known as Koshy's identity, see the references in mathoverflow.net/a/391985/11260 $\endgroup$ May 6 at 6:57
12
$\begingroup$

Let $$C(x) = \sum_{n=1}^\infty C_{n-1} x^n = \frac{1-\sqrt{1-4x}}{2}.$$ Then the identity in question follows easily from $C(x(1-x)) = x$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.