Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
This site is currently in read-only mode; we'll return with full functionality soon. Follow @StackStatus or visit our status blog for more info.

Questions tagged [catalan-numbers]

For questions on Catalan numbers, a sequence of natural numbers that occur in various counting problems.

0
votes
0answers
41 views

Showing that $\lim_{n \to \infty}\frac{c_n}{4^n} = 0$

Here $c_n$ represents the Catalan numbers. This question is from an old exam paper with no solutions available. I have an approach to the problem but it feels very long-winded considering only a few ...
2
votes
2answers
83 views

What is the generating function of $z^3 + 2z^5 + 5z^7 + 14 z^9+\dots$?

What is the generating function of $z^3 + 2z^5 + 5z^7 + 14 z^9+\dots$ ? The generating function can be written as follows: $$A(z)=\sum_{i>2}^{\infty} a_i z^{2i+1},\text{where } a_i \text{ is the ...
1
vote
1answer
40 views

Proving an algebraic binomial identity related to Bertrand's ballot theorem

I am trying to answer the math.stackexchange question found here by developing all the theory from scratch and not using Bertrand's ballot theorem. My logic boils down to being able to prove the ...
2
votes
4answers
103 views

combinatorics - how many ways can I add/subtract 1 from 4 40 times and reach zero without dropping below

I start at 4 and can add 1 or subtract 1 forty times and I need to 0 without dropping below 0. tried to start with a Catalan number and add 4 subs but there are too many ways to get the same answers ...
1
vote
1answer
87 views

The generalised Catalan Numbers and Borel's Triangle

I am currently reading "Counting with Borel’s Triangle" (https://arxiv.org/abs/1804.01597), and am very confused on a stated formula. We know: $C_{n,k}=\frac{n-k+1}{n+1}{n+k \choose n}$ $C(x) = \...
1
vote
1answer
48 views

Borel Bivariate Generating Function

I want to prove the following statement: $$ \beta(t,x)=C(1+t,x)= \frac {C((1+t)x)} {1-xC((1+t)x)} $$ Where $C(x)$ is the generating function for the Catalan Numbers and $ \beta(x) $ is the Borel ...
0
votes
2answers
70 views

How to count with Catalan numbers

I am wondering, in general, how to show that the Catalan numbers can be used to count in a certain problem? For example, I would like to know how the Catalan number $C_n$ counts the number of ways to ...
2
votes
2answers
38 views

Generating Function For Catalan Numbers Type Sequence

I've been working my way through an old post, but I don't think the solution offered can be correct. The question is; Find the generating function (within a choice of sign) for: $$c_{n+1} = 2\sum_{k=...
1
vote
1answer
38 views

Half-catalan numbers

I've been interested in counting how many binary trees there are with n leaves. I consider 2 trees to be the same if I can swap the children of nodes to get the other one. I've started by figuring ...
1
vote
1answer
39 views

Dyck Path w/ Descents of Length 2

Prove the number of Dyck paths with $4n$ steps such that every descent is of length exactly two is equal to the Catalan number $C_n$. I have drawn out some examples to try and solve the problem and ...
19
votes
4answers
4k views

Putting socks and shoes on a spider

A spider needs a sock and a shoe for each of its eight legs. In how many ways can it put on the shoes and socks, if socks must be put on before the shoe? My attempt: If I consider its legs to be ...
1
vote
1answer
61 views

Catalan numbers and numbers of subsequence

Given a set of numbers {$1,2,...,n$}, I want to find the number of permutations without 3-term subsequence of '1-3-2' pattern Now this would be $A_n = n! - U_n$, where $A_n$ is the number of ...
1
vote
0answers
32 views

generalization of Dyck Path: size K upward steps

One of the many interpretations of Dyck Paths is the number of lattice paths from $(0,0)$ to $(n,n)$, staying at or below the diagonal $y=x$, using only 2 kinds of line segments (1 unit right, or 1 ...
0
votes
1answer
97 views

Catalan numbers: bijection between applications of a binary operator and Dyck words.

The Wikipedia article on Catalan numbers lists various combinatorial objects that are described by them. I posit that there might be bijections between these various combinatorial objects. For some of ...
2
votes
0answers
159 views

Proof clarification: Catalan numbers and lattice paths

I'm reading a proof of the fact that the number of monotonic lattice paths from (0,0) to (n,n) not crossing over the diagonal y=x is given by the Catalan numbers. The proof uses the reflection ...
1
vote
1answer
92 views

Catalan numbers: why is there a division by $(n+1)$

There are many interpretations of the Catalan numbers. The one I relate to most readily is the number of paths from the bottom-left to the top-right of an $n \times n$ grid which don't cross the main ...
1
vote
0answers
76 views

Time complexity of Catalan number

The below solution is taken from Stack Overflow which has a very large number of up votes and it was accepted also, but I have a very very small doubt in this. The solution is the exact copy I didn'...
0
votes
1answer
58 views

A Catalan number proof involving an $2$ by $n$ array

I am struggling with this proof. Can anyone help me? Prove that the number of distinct $2$-by-$n$ arrays $$ \begin{bmatrix}x_{11} x_{12} ... x_{1n} \\ x_{21} x_{22} ... x_{2n} \end{bmatrix}$$ ...
1
vote
0answers
25 views

Type B Catalan numbers as signed permutations

The Catalan numbers are in bijection with the 123, 132, etc. avoiding permutations in $S_n$. If we move to type B, the type B Catalan numbers is $\binom{2n}{n}$, and the permutation group is the ...
3
votes
0answers
54 views

Is there a combinatorial proof that the Catalan number $C_n$ satisfies $(n+1)C_n={2n \choose n}$?

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 $...
0
votes
0answers
66 views

A problem on Catalan numbers

Suppose two candidates A and B poll the same number of votes, $n$ each, in an election. The counting of votes is usually done in some arbitrary order and therefore, during the counting process A may ...
1
vote
0answers
37 views

Combination Problem Part 1 about Catalan Number

Refer to an election in which two candidates Wright and Upshaw ran for dogcatcher. After each vote was tabulated, Wright was never behind Upshaw. This problem is known as the ballot problem. Suppose ...
0
votes
0answers
27 views

Number of random walks starting from $0$

Find a number of paths in random walk from $S_0=0$ to $S_{8n}=0$ satisfying the following terms: (a) $S_k \le -2$ for $2 \le k \le 4n-2$ (b) $S_k > 0$ for $4n \le k \le 8n$ Theorem: Let $S_0=a$ ...
2
votes
1answer
352 views

Catalan numbers. Sequence of balanced parentheses.

A legal sequence of parentheses is one in which the parentheses can be properly matched,like ()(()). I should calculate the number of legal sequences of length $2n$, the answer is $C_n = {2n \choose n}...
1
vote
1answer
68 views

How to calculate $\sum_{n=1}^{\infty}A_n(1/2)^{2n+2}(n+2)/(2n+2)$

This is a follow-up to a previous problem, which was answered as follows: $$S=\sum_{n=0}^{\infty}C_n\left(\frac{1}{2}\right)^{\!2n+1}\!\!\left(\frac{n+1}{2n+1}\right)=\frac{\pi}{4},$$ where $C_n$ is ...
2
votes
1answer
62 views

How to calculate $\sum_{n=0}^{\infty}C_n\left(\frac{1}{2}\right)^{2n+1}\left(\frac{n+1}{2n+1}\right)$

Does the following sum equal 1 (or some amount less than 1)? $$S\equiv\sum_{n=0}^{\infty}C_n\left(\frac{1}{2}\right)^{\!2n+1}\!\!\left(\frac{n+1}{2n+1}\right)=\sum_{n=0}^{\infty}\left(\frac{(2n)!}{(n+...
1
vote
0answers
25 views

Combinatorial problem of noncrossing partitions for recursively defined functions

Let $N$ be an even integer. Assume a class of functions $g(b_1,...,b_N)$ with $b_i\neq b_j$ for all $i,j$. These functions are defined recursively by the symmetric function $g(b_i,b_j)=g(b_j,b_i)$ ...
4
votes
0answers
112 views

On the Catalan Numbers

I have been able to prove the following using the snake oil method: $$\sum_{k \ge 0} C_k {{n-2k} \choose {l-k}} = {{n+1} \choose {l}}$$ where $l,n$ are positive integers and $C_k$ is the $k$-th ...
2
votes
0answers
76 views

Reference request for some determinants of binomial coefficients

Let $C_{n}=\frac{1}{n+1}\binom{2n}{n}$ be a Catalan number and $n$ and $k$ be non-negative integers. Consider the following identities: $$ \det\left(\binom{i+j+k}{2j}\right)_{0 \leq i,j\leq {n-1}}=\...
2
votes
1answer
94 views

Combinatorial proof of Catalan number/central binomial convolution: $2n C_n=\sum_{k=1}^n\binom{2k}kC_{n-k}$

Let $C_n=\frac1{n+1}\binom{2n}n$ be the $n^\text{th}$ Catalan number. I discovered the below identity through some generating function magic, and was wondering if anyone could come up with a ...
2
votes
1answer
59 views

Recursion and Catalan Numbers

Consider the sequence defined by $$ \begin{cases} r_0=1\\ r_1=3\\ r_n=6r_{n-1}-9r_{n-2} & \text{if }n\ge 2 \end{cases} .$$ Find a closed form for $r_n$. Your response should be a formula ...
4
votes
2answers
250 views

What is $f(2s+1)$ when $f(s)=\sum_{n=0}^\infty {\frac{(-1)^n}{(2n+1)^s}}=1-\frac{1}{3^s}+\frac{1}{5^s}-\frac{1}{7^s}+\dots$? [duplicate]

Is there an exact form of $$f(s)=\sum_{n=0}^\infty {\frac{(-1)^n}{(2n+1)^s}}=1-\frac{1}{3^s}+\frac{1}{5^s}-\frac{1}{7^s}+\dots$$ when $s$ is odd? Discussion I have been exploring infinite series ...
-2
votes
1answer
49 views

How to calculate a pseudo random Catalan number? [closed]

In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the ...
9
votes
3answers
636 views

Catalan numbers and triangulations

The number of ways to parenthesize an $n$ fold product is a Catalan number in the list $1,1,2,5,14,\cdots$ where these are in order of the number of terms in the product. The $n$th such number is also ...
3
votes
3answers
116 views

What's the probability of completing the illustrated “binomial walk” without ever visiting a node above the baseline?

Consider the illustrated binomial (not binary) tree with $n$ steps (drawn for $n=5$, but consider $n$ variable). Start a random walk at the left-hand node, and at each step you have probability $p$ of ...
3
votes
1answer
76 views

Hypergeometric series identity from Catalan numbers

We know that $$\sum_{n=0}^\infty C_nx^n=\frac{1-\sqrt{1-4x}}{2x}$$. But because $C_n=\frac1{n+1}\binom{2n}n=\frac{(2n)!}{n!(n+1)!}$, that sum is also $$\sum_{n=0}^\infty\frac{(2n)!}{(n+1)!}\frac{x^n}{...
0
votes
1answer
55 views

Question regarding Catalan Number

I have a question regarding Catalan Number. The question is as follows, Find the number of binary strings $w$ of length $2n$ with an equal number of $1’$s and $0’$s and the property that every ...
3
votes
1answer
87 views

Counting non-nesting multi-permutations

Given a sequence $1,1,2,2,3,3, …,k,k$, I am interested in counting the number of non-nesting permutations of the above sequence. Two intervals (determined by symbols $K$ and $L$) are nesting if one is ...
2
votes
0answers
446 views

Total number of leaves binary tree with n internal nodes

Using the definition of a leaf as being an internal node with no children (both children are external nodes), how can I find the total number of leaves for all binary trees with n internal nodes, for ...
2
votes
1answer
108 views

Generating function for the Catalan numbers

I know that generating function $f(x)$ for the Catalan numbers is \begin{equation} f(x)=\cfrac{1\pm \sqrt{1-4x}}{2x}\ . \end{equation} It is often said that we should choose \begin{equation} f(x)=\...
0
votes
1answer
241 views

How to get to Catalan numbers recurrence relation from couting lattice paths

I'm currently taking a probability theory class and I've been stuck on a problem where I can find the solution using one method but I dont get how my TA got to the catalan numbers from counting, so ...
0
votes
0answers
57 views

Forbiden paths in Catalan numbers

I am trying to solve the next problem: Find all the possible combinations of roads that do not cross each other given a number of towns. First I started permuting all combinations with low numbers ...
0
votes
0answers
45 views

Combinations of Catalan numbers with restrictions

I have to pair numbers in a circle without crossing chords. This: Image example The way to solve this is Catalan Numbers where n = nodes/2 The problem comes with some restrictions. I have to ...
0
votes
1answer
81 views

Catalan Numbers and Geometric Series Combo

Is there a nice (non-summation) representation of the following sum? $$\sum_{n=1}^{N}C_{n}b^n$$ where $b <1$ and $C_{n}$ are the Catalan numbers. Obviously, this can be written as $$\sum_{n=1}^{N}...
0
votes
1answer
39 views

What is the expansion of $\sqrt{1+ux+vx^2}$ in powers of $x$?

What is the expansion of $\sqrt{1+ux+vx^2}$ in powers of $x$? This came up in my answer here: How to solve this recurrence$f(n)=A\cdot f(n-1)+B\sum{f(i)f(n-i)},\;1\leq i\leq n-1,$ and $f(1)=K$? I ...
0
votes
1answer
105 views

Suppose 2k people are seated around a table.

How many ways are there for the k pairs of people to shake hands simultaneously across the table in such a way that no arms cross?
1
vote
2answers
196 views

Question in proving a recurrence relation for Catalan numbers [closed]

How to prove the recurrence relation for Catalan numbers, stating $$C_{n}=\sum_{i=0}^{n-1}C_{i}C_{n-1-i}$$ where we define $C_{0}$ as $1$?
1
vote
0answers
62 views

Formula for Generalized Catalan Numbers

The Catalan numbers $C_n$ count the number of staircase walks from $(0,0)$ to $(n,n)$ that lie below the diagonal $y=x$. Let $C(n,k)$ denote the number of staircase walks from $(k,0)$ to $(n,n)$ that ...
0
votes
1answer
126 views

extracting Catalan numbers from its generating function (binomial theorem)

I am reading the Combinatorics by Cameron, and one sections buggs me: $C_n = \sum_{i=1}^{n-1} C_iC_{n-i}$ We take $F(t) = \sum_{n \geq1}C_nt^n$ From which we conclude $F(t) = t + F(t)^2$ then $F(t) ...
6
votes
1answer
75 views

A bijection between Motzkin paths and 3-colored signed Dyck path homomorphs

The generating function $m=m(z)$ for the Motzkin numbers satisfies the functional equation $$ m=1+zm+z^2m^2 $$ (a Motzkin path $P$ with unit steps $u,d,l$ (up, down, level) is either empty or $lP'$ or ...