All Questions
Tagged with co.combinatorics combinatorial-identities
101 questions
5
votes
1
answer
231
views
Reference request: Gessel interview's generating function identities
In this interview, Ira Gessel mentions the following results:
Result 1: Let $B_n$ denote the $n^{\text{th}}$ Bernoulli number.
Define the series
$$B(x) = \sum_{n=2}^{\infty} \frac{B_nx^{n-1}}{n(n-1)}.$...
- 17k
0
votes
1
answer
403
views
Could you please confirm or deny two identities involving weighted Stirling numbers of the second kind?
In the paper [1] below, among other things, Carlitz introduced weighted Stirling numbers of the second kind $R(n,k,r)$. He also proved that the numbers $R(n,k,r)$ can be generated by
\begin{equation*}%...
- 1,091
23
votes
5
answers
2k
views
Identity involving Pochhammer symbol
I came across the following identity in my research:
$$
\sum_{m=0}^s \frac{(-1)^m (a+2m)}{m!(s-m)! (a+m)_{s+1}}=\delta_{s,0}
$$
where $(a)_n= a(a+1)\cdots (a+n-1)$ is the Pochhammer symbol. One can ...
- 109k
4
votes
1
answer
216
views
Any conjectures about Jack Littlewood-Richardson coefficients when Schur LR > 1?
Stanley famously conjectured ("Some combinatorial properties of Jack symmetric functions" Adv. in Math. (77) 1989, doi:10.1016/0001-8708(89)90015-7, MR1014073, Zbl 0743.05072) that the Jack ...
- 335
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 ...
- 17k
13
votes
1
answer
468
views
Four new series for $\pi$ and related identities involving harmonic numbers
Recently, I discovered the following four new (conjectural) series for $\pi$:
\begin{align}\sum_{k=1}^\infty\frac{(5k^2-4k+1)8^k\binom{3k}k}{k(3k-1)(3k-2)\binom{2k}k\binom{4k}{2k}}&=\frac{3\pi}2,\...
- 188k
6
votes
1
answer
484
views
Three conjectural series for $\pi^2$ and related identities
Recently, I found the following three (conjectural) identities for $\pi^2$:
$$\sum_{k=1}^\infty\frac{145k^2-104k+18}{k^3(2k-1)\binom{2k}k\binom{3k}k^2}=\frac{\pi^2}3,\tag{1}$$
$$\sum_{k=1}^\infty\frac{...
- 528
6
votes
0
answers
235
views
A curious series for $L(2,(\frac{-3}{\cdot}))$
Let
$$K:=L\left(2,\left(\frac{-3}{\cdot}\right)\right)=\sum_{k=1}^\infty\frac{(\frac k3)}{k^2}=\sum_{j=0}^\infty\left(\frac1{(3j+1)^2}-\frac1{(3j+2)^2}\right),$$ where $(\frac k3)$ is the Legendre ...
- 6,367
6
votes
0
answers
298
views
A new series for $\sqrt3/\pi$?
Recently, I conjectured the following identity:
$$\sum_{k=0}^\infty\frac{(66k^2+37k+4)\binom{2k}k\binom{3k}k\binom{4k}{2k}}{(2k+1)729^k}=\frac{27\sqrt3}{2\pi}.\tag{1}$$
This can be easily checked ...
- 15.6k
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 $\...
- 109k
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
10
votes
2
answers
2k
views
Proving an identity about Catalan numbers
$$C_{n} = \sum_{i=1}^n (-1)^{i-1} \binom{n-i+1}{i} C_{n-i}$$
Are there any good combinatorial proofs or algebraic proofs of this?
- 10.5k
0
votes
0
answers
244
views
Looking for a combinatorial proof of an identity
I've come up with an interesting combinatorial identity (thanks to P. Belmans who precomputed the numbers and pointed out to me that they correspond to OEIS A002697):
$$
\sum_{i=0}^{n-1}\binom{n+1-i}{...
- 12.9k
0
votes
0
answers
302
views
An alternating sum involving a product of binomial coefficients
I encountered the sum below, where $c_{1}$, $c_{2}$, $c_{3}$, $c_{4}$ and $d$ are some given positive constants. Does anyone have an idea how to simplify it?
$$
\sum\limits_{k=1}^{d} \frac{(-1)^{k-1}k}...
- 109
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 ...
- 128k
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
12
votes
0
answers
629
views
$q$-analogue of the multinomial theorem?
The $q$-binomial theorem states that
$$
\prod_{k=0}^{n-1}(1+q^kt) = \sum_{k=0}^n q^{\binom k2}{n\brack k}_q t^k.
$$
This identity is a $q$-analogue of the binomial theorem
$$
(1+t)^n = \sum_{k=0}^n \...
- 5,654
3
votes
2
answers
427
views
Combinatorial identity concerning integral matrices with prescribed row sums and column sums
How to prove the following identity?
Let $r = (r_1, r_2, \ldots, r_d)$ and $c = (c_1, c_2, \ldots, c_d)$ be sequences of natural numbers such that $s = r_1 + r_2 + \cdots + r_d = c_1 + c_2 + \ldots + ...
- 1,755
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
3
votes
1
answer
388
views
Is this combinatorial identity known? (of interest for random matrix theory)
While playing around with random matrices and I arrived at a different formula for the mean of the limiting normal distribution for a spectral CLT for sample covariance matrices. More precisely I have ...
- 7,226
3
votes
2
answers
463
views
Ask for a reference or a proof of a combinatorial identity $\sum_{k=0}^n\binom{2n+1}{2k}\binom {k}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m}$
Could you please recommend a reference to or supply a proof of the following identity \eqref{combin-ID-Maclaurin}, or \eqref{first-equiv-form}, or \eqref{combin-ID-Mac-Equiv}, or \eqref{combin-ID-Mac-...
- 1,091
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 ...
- 1,906
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 ...
- 2,306
4
votes
1
answer
147
views
$0,1$-matrices with $1$ in every row/column vs. all $0,1$-matrices
Chapter 2, Exercise 25 of R. Stanley's "Enumerative Combinatorics" Vol. 1 asserts that
$$ \sum_{m,n \geq 0} \left(\sum_{t \geq 0} f_i(m,n)t^i\right)\frac{x^m}{m!}\frac{y^n}{n!} = e^{-x-y}\...
- 17k
12
votes
3
answers
892
views
Set partitions and permanents
Let $a(n)=$ Number of ordered set partitions of $[n]$ such that the smallest element of each block is odd.
...
- 884
9
votes
1
answer
676
views
Permanent identities
The permanent $\mathrm{per}(A)$ of a matrix $A$ of size $n\times n$ is defined to be:
$$\mathrm{per}(A)=\sum_{\tau\in S_n}\prod_{j=1}^na_{j,\tau(j)}.$$
Let
$$A=\left[\tan\pi\frac{j+k}n\right]_{1\le j,...
- 15.6k
1
vote
1
answer
124
views
A $1$-step convolution identity involving the Motzkin triangle
The Motzkin triangle $T(n,k)$ is built according to the rules:
(1) $T(n,0)=1$;
(2) $T(n,k)=0$ if $k<0$ or $k>n$;
(3) $T(n,k)=T(n-1,k-2)+T(n-1,k-1)+T(n-1,k)$.
After some numerical evidence I ...
- 7,226
46
votes
0
answers
3k
views
A = B (but not quite); 3-d arrays with multiple recurrences
Many years ago, I discovered the remarkable array (apparently originally discovered by Ramanujan)
1
1 3
2 10 15
6 40 105 105
24 196 700 1260 945
...
- 33.8k
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, ...
- 7,875
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:
$$\...
- 17k
10
votes
2
answers
2k
views
Expressions involving Eulerian numbers of the second kind: trying to show $\sum_{m=0}^{n} (-1)^m(m)m!(2n-m-2)!\left\langle\left\langle n\atop m\right\rangle\right\rangle\neq0$ for even $n$.
Considering the success of a previous question involving Eulerian numbers, I thought I might throw this question into the mix. It comes from some localization computations in GW theory, but in this ...
- 1
3
votes
2
answers
244
views
Is there a combinatorial reason for variable-independence of this binomial-coefficient identity?
Consider the following identity
$$\sum_{n=0}^{R-t}\binom{n+\ell}n\binom{R-\ell-n}{R-t-n}=\binom{R+1}{t+1}.\tag1$$
It is relatively easy to give an algebraic or mechanical proof of (1). But, I like to ...
- 4,713
3
votes
1
answer
466
views
How to prove this combinatorial identity?
If $n \in \mathbb N \setminus \{0\}$ and $x,y,z \in \mathbb R$ such that $x+y+z=n-1$, show that
$$\dfrac{(-4)^n}{\binom{2x}{n}}\sum_{r+s=n,r,s\in Z}\dfrac{\binom{y}{r}\binom{y-a}{r}\binom{z}{s}\binom{...
- 2,720
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_{...
- 109k
3
votes
1
answer
439
views
An identity for polynomials over partitions
Given an integer partition $\lambda=(\lambda_1,\dots,\lambda_{\ell(\lambda)})$ of $n$ where $\ell(\lambda)$ is the length of $\lambda$, associate its conjugate partition $\lambda'$. Denote by $\lambda'...
- 33.8k
2
votes
0
answers
196
views
For human proofs of two novel combinatorial identities
For $n=0,1,2,\ldots$, let us define the polynomial
$$S_n(x):=\sum_{k=0}^n\binom{x/2}k\binom{(x-1)/2}k\binom{-(x+1)/2}{n-k}\binom{-(x+2)/2}{n-k}.$$
Such polynomials occur in some series for $1/\pi$ ...
- 15.6k
6
votes
1
answer
310
views
On the sum $\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k}$
Let $n$ be a non-negative integer.
Does there always exist a polynomial $P_n(a,b)$ such that for all integers $a > b \geq n/2$ we have
$$
\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k} = \...
- 3,927
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 ...
- 17k
5
votes
1
answer
351
views
"Non-associative" standard polynomials
I saw somewhere (I appreciate if anyone has any references to proof of this fact) that if $A$ is a finite dimensional associative algebra such that $\textrm{dim}(A)<n$, then $A$ satisfies the ...
- 353
4
votes
2
answers
495
views
Showing this formula counts these things
I'm writing an article, and I got stuck trying to prove that some numbers are positive. I have a relatively good intuition for guessing what an expression is counting, but in this case I'm not being ...
- 3,255
5
votes
0
answers
350
views
Sum over permutations involving sign
The problem is to evaluate the following sum over all permutations $\sigma\in S_{d}$ of $\{1,2,...,d\}$:
$\displaystyle\sum_{\sigma\in S_{d}}\text{sgn}(\sigma)\displaystyle\frac{1}{\prod_{i=1}^{d}(\...
- 1,538
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 ...
CommunityBot
- 1
9
votes
5
answers
888
views
Sums of binomial coefficients weighted by incomplete gamma
I am interested in proving that
$$\sum_{k=0}^n\frac{k}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}=1
$$
and
$$\sum_{k=0}^n\frac{k^2}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}=2.
$$
I verified it numerically ...
32
votes
3
answers
3k
views
A conjectural trigonometric identity
Recently, I formulated the following conjecture which seems novel.
Conjecture. For any positive odd integer $n$, we have the identity
$$\sum_{j,k=0}^{n-1}\frac1{\cos 2\pi j/n+\cos 2\pi k/n}=\frac{n^2}...
- 109k
-1
votes
1
answer
271
views
How do I calculate this sum $\sum_k(k!)^{-n}$? [closed]
How do I evaluate the following finite sum over $k$
$1+\frac{1}{2^n}+\frac{1}{2^n3^n}+\frac{1}{2^n3^n4^n}+\cdots+\frac{1}{2^n3^n\cdots k^n}$
or if there is an expression of this sum in terms of ...
- 63.9k
7
votes
3
answers
478
views
A hypergeometric identity related to Bessel functions
The identity in my recent answer can be stated in a particularly neat form:
$${}_2F_0\left({-n, n+1\atop{}};\frac{x}{2}\right) ~\cdot~ {}_2F_0\left({-n, n+1\atop{}};-\frac{x}{2}\right) ~=~ {}_3F_0\...
