Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with catalan-numbers
Search options answers only
not deleted
user 10744
The Catalan numbers form the sequence of numbers starting 1,1,2,5,14,42,... with explicit formula $\frac{1}{n+1}\binom{2n}{n}$. It counts many combinatorial objects like planar binary trees, triangulations, noncrossing partitions, Dyck paths, etc. See https://oeis.org/A000108
4
votes
Accepted
Why is this alternating sum involving Catalan numbers $\sum_{i=0}^{\lfloor t/2 \rfloor} (-1)...
The formula (which holds for $t>1$ but not for $t=1$), is equivalent to
$$\sum_{t=1}^\infty C_{t-1}\bigl(x(1-x)\bigr)^t = x,$$
which follows directly from the generating function
$$\sum_{t=1}^\infty C …
- 17k
12
votes
A recurrence relation on Catalan numbers
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$.
- 17k
9
votes
Accepted
A sequence of polynomials related to Catalan numbers
I find a slightly different initial condition for the recurrence:
$$0=\sum_{j=0}^nP_{n-j}(P_j-(-x)^j)$$
for $n\ne 1$; for $n=1$ the sum is $-1$. It's easy to derive a formula for the generating functi …
- 17k
22
votes
Proving an identity about Catalan numbers
Algebraically, this identity is
$$\sum_{n=0}^\infty C(n) x^n (1-x)^{n+1} = 1, $$
which is a consequence of the generating function
$$\sum_{n=0}^\infty C(n) x^n = \frac{1-\sqrt{1-4x}}{2x}.$$
- 17k
13
votes
Looking for a combinatorial proof for a Catalan identity
More generally,
$$\sum_{k\ge1} \frac{k}{m}\binom{2m}{m-k}\cdot\frac{k}{n} \binom{2n}{n-k} = C_{m+n-1}.$$
This can be proved by the same reasoning as in Timothy Budd's answer.
This formula gives the LD …
- 17k
8
votes
How does this relationship between the Catalan numbers and SU(2) generalize?
Re Question 1: For the connection between walks and continued fractions (which is closely related to orthogonal polynomials, but not, as far as I know, to root systems) see Philippe Flajolet, Combinat …
- 17k