All Questions
Tagged with combinatorial-identities reference-request
26 questions
6
votes
2
answers
719
views
Recreation with Catalan
Consider the well-known sequence $C_k=\frac1{k+1}\binom{2k}k$ of Catalan numbers. I came across the below identity while working with certain generating functions. I thought it might be of interest to ...
- 43.2k
3
votes
3
answers
756
views
Ordinary partitions vs partitions into odd parts
Let $\mathcal{P}(n)$ be the set of all unrestricted partitions of $n$ while $\mathcal{O}(n)$ stand for the set of all partitions of $n$ into odd parts. We adopt the power notation for partitions $\...
- 43.2k
4
votes
0
answers
97
views
"Convolving" a general Catalan with classical Catalan
Consider what is sometimes known as generalized Catalan sequence
$$\mathcal{{\color{red}C}}_{a,b}:=\frac{2b+1}{a+b+1}\binom{2a}{a+b}.$$
Observe that $\mathcal{{\color{red}C}}_{n,0}$ reduces to the ...
- 43.2k
4
votes
0
answers
208
views
Extract this constant term
Given a Laurent polynomial $F$ in the variables $\mathbf{t}=(t_1,\dots,t_n)$, let $CT_{\vec{\mathbf{t}}}\,F$ denote its constant term.
For example, $CT_{t_1,t_2}((8t_1-\frac1{3t_1t_2})(5t_1t_2+t_2^2+\...
- 43.2k
3
votes
1
answer
215
views
Seeking for a combinatorial argument for partition identities
Given an integer partition $\lambda$, introduce the following quantities:
\begin{align*}
c(\lambda)&=\sum_{i\geq1}\left\lceil\frac{\lambda_i}2\right\rceil, \qquad c_o(\lambda)=\sum_{i\geq1}\left\...
- 43.2k
7
votes
1
answer
286
views
A reference for a sum found in Gould's Combinatorial Identities book
On p. 49 in Gould's book Combinatorial Identities, the author states that the sum $$\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}\binom{2n}{2k}^{-1}$$ "... arises naturally in a statistical problem; it ...
- 135
2
votes
1
answer
214
views
A Vandermonde like determinant with exponentials
Let $n\geq m$ be non negative integers, and consider a list of $(n+m+1)$ distinct numbers (complex or real). I am interested in getting a closed form formula for the following determinant: $\det\left[\...
- 275
1
vote
1
answer
220
views
Gaussian at $q=\pm1$, log-concave polynomials, Catalan numbers
Let $[n]_q!=\prod_{j=1}^n\frac{1-q^j}{1-q}$ with $[0]_q!:=1$ and the Gaussian polynomials $\binom{n}k_q=\frac{[n]_q!}{[k]_q!\,\cdot\,[n-k]_q!}$. Adopt the convention that $\binom{n}k_q=0$ whenever $k&...
- 43.2k
2
votes
1
answer
218
views
$q$-binomial sum, slightly
Recall that $[n]_{q}!=\prod_{j=1}^n\frac{1-q^{j}}{1-q}$ and $\binom{n}k_{q}=\frac{[n]_{q}!}{[k]_{q}![n-k]_{q}!}$. Then the $q$-binomial theorem states
$$\sum_{k=0}^n\binom{n}k_qq^{\binom{k}2}=\prod_{k=...
- 43.2k
15
votes
2
answers
1k
views
A rather curious identity on sums over triple binomial terms
While exploring the Baxter sequences from my earlier MO post, I obtained a rather curious identity (not listed on OEIS either). I usually try to employ the Wilf-Zeilberger (WZ) algorithm to justify ...
- 43.2k
10
votes
2
answers
484
views
Identity involving a quadratic term inside the Pochhammer symbol
This identity came up in my research:
$$
\sum_{m=1}^n m^2 \frac{(\frac{xy}n + m-1)_{2m-1} (n+m-1)_{2m-1}}{(x+m)_{2m+1} (y+m)_{2m+1}} = \frac{n^2}{(x^2-n^2) (y^2 - n^2)}.
$$
Here $n$ is a fixed ...
- 3,772
3
votes
1
answer
186
views
Is there a $q$-analogue to Shapiro's convolution identity?
Let $C_n=\frac1{n+1}\binom{2n}n$ denote the Catalan numbers.
This question is motivated by the (unanswered) MO post by Alexander Burstein and my own (answered by Fedor Petrov) MO post.
Specifically, ...
- 43.2k
7
votes
1
answer
325
views
Looking for a $q$-analogue of a binomial identity
The following identity is well-known and there are a few proofs to it (see Bijective proof problems, by R P Stanley, for this and similar formulae):
$$\sum_{k=0}^n\binom{2k}k\binom{2n-2k}{n-k}=4^n \...
- 43.2k
10
votes
0
answers
349
views
A bijective proof for the odd companion to Shapiro's Catalan convolution
Shapiro's Catalan convolution is the following formula (where $C_n$ is the $n$th Catalan number):
$$
\sum_{k=0}^{n}{C_{2k}C_{2(n-k)}}=4^nC_n.
$$
In other words, letting $C(z)=\sum_{n=0}^{\infty}{C_nz^...
- 1,190
6
votes
2
answers
217
views
A convolution-type identity for the "major index"
For a permutation $\pi\in\frak{S}_n$, define the number of descents of $\pi$ as $$\text{des}(\pi)=\vert\{i: \pi(i)>\pi(i+1)\}\vert.$$
The following is a well-known (and interesting) identity:
$$\...
- 43.2k
6
votes
5
answers
944
views
Combinatorial proof of Catalan's identity
Consider the problem of tiling a board of length $n$ with squares of size $1×1$ and dominoes of size $1×2$, Let's denote $f_n$ to be the number of ways to tile this so-called ($n$)-board.Then $f_n=F_{...
user153001
1
vote
2
answers
211
views
Bilinear recurrence relation between even Bernoulli numbers
Throughout this question $n$ is a positive integer greater than 1.
Consider the following well-known identity by Euler,
$$\sum_{k=1}^{n-1} \binom{2n}{2k}B_{2k}B_{2n-2k}=-(2n+1)B_{2n}.$$
Rather ...
- 195
6
votes
2
answers
1k
views
Products and sum of cubes in Fibonacci
Consider the familiar sequence of Fibonacci numbers: $F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$.
Although it is rather easy to furnish an algebraic verification of the below identity, I wish to see a ...
- 43.2k
2
votes
2
answers
273
views
Alternating binomial-harmonic sum: evaluation request
Let $H_k=\sum_{j=1}^k\frac1j$ be the harmonic numbers.
QUESTION. Can you find an evaluation of the following sum?
$$\sum_{a=1}^b(-1)^a\binom{n}{b-a}\frac{H_{b-a}}a.$$
- 43.2k
1
vote
1
answer
154
views
$q$-plane partitions & specialization & interlinks
MacMahon's enumeration of all plane partions (PP) inside an $n$-cube generalizes to
$${\tt PP_n}(q)=\prod_{i,j,k=1}^n\frac{1-q^{i+j+k-1}}{1-q^{i+j+k-2}}.$$
A $q$-analogue of symmetric plane partitions ...
- 43.2k
8
votes
2
answers
325
views
A link between hooks and contents: Part II
This is a question in the spirit of an earlier problem.
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$.
Recall also the notation for the content of a cell $...
- 43.2k
11
votes
2
answers
1k
views
Proofs of some combinatorial identities
Just wondering if anyone knows any references in the literature to bijections corresponding to the following simple generating function identities. Let $B(z)=\dfrac{1}{\sqrt{1-4z}}$ and $C(z)=\dfrac{1-...
- 1,190
24
votes
2
answers
2k
views
Reference for exponential Vandermonde determinant identity
I recently stumbled upon the following identity, valid for any real numbers $\alpha_1,\dots,\alpha_n$ and $\lambda_{n1} \leq \dots \leq \lambda_{nn}$:
$$ \mathrm{det}( e^{\alpha_i \lambda_{nj}} )_{1 \...
- 114k
1
vote
1
answer
179
views
One trig "survives" a binomial summation: why?
I've seen many trigonometric identities but here is one that I encountered for which I did not find a reference.
In case you wonder where this came from, I was investigating certain $q$-series in ...
- 43.2k
8
votes
1
answer
914
views
A special binomial identity in need of a proof
I've encountered a curious identity as a codicil in some work. Is there a proof or reference?
$$\sum_{k=-n}^n\frac{2k+1}{n+k+1}\binom{2n}{n-k}\frac{x^k}{1+x^{2k+1}}=\frac{x^n}{1+x^{2n+1}}.$$
- 43.2k
3
votes
2
answers
696
views
Open problems and known identities involving sums
As many people here, I know of a few identities involving expressions of the type $\sum_{i}\ f(i)$, with "arbitrarily complicated $f(\cdot)$", as well as closed formulas in some cases.
I also know ...
- 1,164