# Questions tagged [combinatorial-identities]

The combinatorial-identities tag has no usage guidance.

163
questions

0
votes

1
answer

82
views

### Closed form of a Hypergeometric Function ${}_2F_1$ at $z=-8$

How this can be proved?
$$
E = {}_2F_1(-\frac{1}{2}, \frac{1}{3}, \frac{4}{3},-8) = \frac{6}{5} - \frac{\chi}{2}
$$
where
$$
\chi = \frac{6\sqrt{\pi}}{5}\frac{\Gamma(\frac{1}{3})}{\Gamma(-\frac{1}{6})}...

5
votes

1
answer

224
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)}.$...

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 ...

6
votes

2
answers

717
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 ...

3
votes

1
answer

429
views

### Identities for Bernoulli numbers

I arrived at this formula by inductive reasoning, but I don’t know how to prove it.
For any natural numbers $m$ and $k=0,1,2,\ldots, m-1$, $B_i$ - Bernoulli numbers we have:
$$\sum_{i=0}^k (-1)^{k-i}\...

1
vote

1
answer

244
views

### A vanishing sum and related $p$-adic congruences

Recently I had a curious discovery. Namely, I have made the following conjectures.
Conjecture 1. We have the identity
$$\sum_{k=0}^\infty\frac{(10k-1)\binom{3k}k\binom{6k}{3k}}{(2k+1)512^k}=0.\label{1}...

8
votes

0
answers

330
views

### A hypergeometric series for $\sqrt3\pi$ with converging rate $1/9$

Recently, I found a (conjectural) new series for $\sqrt3\pi$:
$$\sum_{k=1}^\infty\frac{(8k-3)\binom{4k}{2k}}{k(4k-1)9^k\binom{2k}k^2}=\frac{\sqrt3\pi}{18}.\label{1}\tag{1}$$
The series converges fast ...

13
votes

1
answer

452
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,\...

6
votes

0
answers

228
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
votes

1
answer

461
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{...

6
votes

0
answers

294
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 ...

4
votes

1
answer

210
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 ...

3
votes

3
answers

750
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 $\...

6
votes

1
answer

432
views

### A summation involving fraction of binomial coefficients

I need to prove the following statement.
Let $ n, g, m, a ,t$ be integers. Prove that the following statement is true for all $ n \geq g(1+2m)+1 $, $ g\geq 2t $, $ m\geq t $, $ 0\leq a <t $, and $ ...

8
votes

3
answers

606
views

### An identity involving polylogarithms

Recall that
$$\mathrm{Li}_2(x):=\sum_{n=1}^\infty\frac{x^n}{n^2}.$$
I have found the following identity:
\begin{equation}\begin{aligned}&\mathrm{Li}_2\left(\frac{-1-\sqrt{-7}}4\right)+\mathrm{Li}...

4
votes

0
answers

96
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 ...

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+\...

0
votes

0
answers

239
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}{...

3
votes

1
answer

214
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\...

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?

0
votes

0
answers

282
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}...

7
votes

1
answer

281
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 ...

2
votes

1
answer

208
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[\...

10
votes

0
answers

499
views

### New series for $\zeta(5)$ involving second-order harmonic numbers

In 1997 T. Amdeberhan and D. Zeilberger proved that
$$\sum_{k=1}^\infty\frac{(-1)^k(205k^2-160k+32)}{k^5\binom{2k}k^5}=-2\zeta(3).\tag{1}$$
In 2008 J. Guillera obtained that
$$\sum_{k=1}^\infty\frac{(...

10
votes

1
answer

419
views

### Series for $\frac{\log m}{\pi}$ with summands involving harmonic numbers

The classical rational Ramanujan-type series for $1/\pi$ have the following four forms:
\begin{align}\sum_{k=0}^\infty(ak+b)\frac{\binom{2k}k^3}{m^k}&=\frac{c}{\pi},\label{1}\tag{1}
\\\sum_{k=0}^\...

4
votes

0
answers

226
views

### Curious double sum identity

The following identity seems to hold for $a>1$ :
$$\sum_{m=1}^\infty \sum_{n=1}^\infty \frac{1}{ \frac{a^m}{m}\left( \frac{a^m}{m}+ \frac{a^n}{n} \right) } = \frac{a^2}{2(a-1)^4}$$
I've tested ...

1
vote

1
answer

190
views

### Curious identity involving the number of perfect matchings of the complete graph

Can you prove (preferably combinatorially) the following identity for the total number of perfect matchings of the complete graph $K_{2n}$, where the edges in the matching are ordered, i.e., $\binom{...

8
votes

1
answer

542
views

### Trivial (?) product/series expansions for sine and cosine

In an old paper of Glaisher, I find the following formulas:
$$\dfrac{\sin(\pi x)}{\pi x}=1-\dfrac{x^2}{1^2}-\dfrac{x^2(1^2-x^2)}{(1.2)^2}-\dfrac{x^2(1^2-x^2)(2^2-x^2)}{(1.2.3)^2}-\cdots$$
$$\cos(\pi x/...

12
votes

0
answers

577
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 \...

1
vote

1
answer

217
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&...

3
votes

2
answers

421
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 + ...

2
votes

1
answer

215
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=...

5
votes

1
answer

311
views

### A conjectural permanent identity

Let $n>1$ be an integer, and let $\zeta$ be a primitive $n$th root of unity. By $(3.4)$ of arXiv:2206.02589, $1$ and those $n+1-2s\ (s=1,\ldots,n-1)$ are all the eigenvalues of the matrix $M=[m_{jk}...

3
votes

1
answer

380
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 ...

2
votes

1
answer

502
views

### Integer eigenvalues of a class of matrices inspired by Prof. Zhi-Wei Sun's conjecture

Theorem: Let $n>1$ be an odd number and $\zeta$ a primitive $n$-th root of unity. Then
\begin{eqnarray}
&&\sum_{\tau\in D(n-1)}\mathrm{sign}(\tau)\prod_{j=1}^{n-1}\frac{1}{1-\zeta^{j-\tau(j)...

1
vote

1
answer

216
views

### A conjectural identity involving infinite series

Recently I formulated the following curious conjecture based on my computation.
Conjecture. For all $|x|>1$, we have the identity
$$\sum_{k=0}^\infty\frac{\sum_{j=0}^{k}\binom{2k+1}{2j}(1-x)^jx^{k-...

0
votes

1
answer

394
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*}%...

2
votes

2
answers

273
views

### Ask for a proof of an identity involving the product of two Bernoulli numbers

It is well known that the Bernoulli numbers $B_{k}$ for $k\in\{0,1,2,\dotsc\}$ can be generated by
\begin{equation*}
\frac{z}{\textrm{e}^z-1}=\sum_{k=0}^\infty B_k\frac{z^k}{k!}=1-\frac{z}2+\sum_{k=1}^...

15
votes

2
answers

989
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 ...

10
votes

2
answers

475
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
votes

2
answers

446
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-...

4
votes

1
answer

144
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}\...

12
votes

3
answers

882
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.
...

6
votes

1
answer

516
views

### A novel identity connecting permanents to Bernoulli numbers

For a matrix $[a_{j,k}]_{1\le j,k\le n}$ over a field, its permanent is defined by
$$\mathrm{per}[a_{j,k}]_{1\le j,k\le n}:=\sum_{\pi\in S_n}\prod_{j=1}^n a_{j,\pi(j)}.$$
In a recent preprint of mine, ...

10
votes

1
answer

556
views

### Identities involving derangements and roots of unity

For a positive integer $n$, a derangement of $\{1,\ldots,n\}$ is a permutation $\tau$ of $\{1,\ldots,n\}$ with $\tau(j)\not=j$ for all $j=1,\ldots,n$. For convenience, we let $D(n)$ denote the set of ...

9
votes

1
answer

671
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,...

5
votes

3
answers

717
views

### How to prove the combinatorial identity $\sum_{k=\ell}^{n}\binom{2n-k-1}{n-1}k2^k=2^\ell n\binom{2n-\ell}{n}$ for $n\ge\ell\ge0$?

With the aid of the simple identity
\begin{equation*}
\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^{k}}=2^n
\end{equation*}
in Item (1.79) on page 35 of the monograph
R. Sprugnoli, Riordan Array Proofs of ...

3
votes

1
answer

181
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
votes

1
answer

318
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 \...

10
votes

0
answers

347
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^...