Questions tagged [combinatorial-identities]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
3 answers
647 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 $\...
T. Amdeberhan's user avatar
6 votes
1 answer
310 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 $ ...
Arda Aydin's user avatar
7 votes
2 answers
501 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}...
Zhi-Wei Sun's user avatar
  • 13.9k
4 votes
0 answers
89 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 ...
T. Amdeberhan's user avatar
4 votes
0 answers
196 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+\...
T. Amdeberhan's user avatar
0 votes
0 answers
186 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}{...
Anton Fonarev's user avatar
3 votes
1 answer
194 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\...
T. Amdeberhan's user avatar
10 votes
2 answers
1k 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?
banana's user avatar
  • 111
0 votes
0 answers
211 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}...
sdd's user avatar
  • 109
7 votes
1 answer
235 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 ...
Sela Fried's user avatar
2 votes
1 answer
183 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[\...
Athena's user avatar
  • 275
10 votes
0 answers
428 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{(...
Zhi-Wei Sun's user avatar
  • 13.9k
9 votes
1 answer
312 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}^\...
Zhi-Wei Sun's user avatar
  • 13.9k
4 votes
0 answers
195 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 ...
Jim Bryan's user avatar
  • 5,880
1 vote
1 answer
146 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{...
sdd's user avatar
  • 109
8 votes
1 answer
519 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/...
Henri Cohen's user avatar
  • 10.7k
12 votes
0 answers
375 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 \...
Amritanshu Prasad's user avatar
1 vote
1 answer
206 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&...
T. Amdeberhan's user avatar
3 votes
2 answers
412 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 + ...
MMM's user avatar
  • 245
2 votes
1 answer
189 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=...
T. Amdeberhan's user avatar
5 votes
1 answer
285 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}...
Zhi-Wei Sun's user avatar
  • 13.9k
3 votes
1 answer
347 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 ...
Tardis's user avatar
  • 797
2 votes
1 answer
468 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)...
KLiu's user avatar
  • 41
1 vote
1 answer
206 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-...
Zhi-Wei Sun's user avatar
  • 13.9k
-1 votes
1 answer
321 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*}%...
qifeng618's user avatar
  • 726
2 votes
2 answers
245 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}^...
qifeng618's user avatar
  • 726
15 votes
2 answers
935 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 ...
T. Amdeberhan's user avatar
9 votes
2 answers
407 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 ...
Anton Mellit's user avatar
  • 3,562
3 votes
2 answers
402 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-...
qifeng618's user avatar
  • 726
4 votes
1 answer
134 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}\...
Sam Hopkins's user avatar
  • 21.3k
12 votes
3 answers
833 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. ...
Deyi Chen's user avatar
  • 729
6 votes
1 answer
485 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, ...
Zhi-Wei Sun's user avatar
  • 13.9k
10 votes
1 answer
511 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 ...
Zhi-Wei Sun's user avatar
  • 13.9k
9 votes
1 answer
634 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,...
Deyi Chen's user avatar
  • 729
5 votes
3 answers
568 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 ...
qifeng618's user avatar
  • 726
3 votes
1 answer
167 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, ...
T. Amdeberhan's user avatar
7 votes
1 answer
292 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 \...
T. Amdeberhan's user avatar
10 votes
0 answers
333 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^...
Alexander Burstein's user avatar
6 votes
2 answers
208 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: $$\...
T. Amdeberhan's user avatar
3 votes
2 answers
68 views

Optimal scaling of Lipschitz estimates in generalized geometric series

If we did not know it before, then wikipedia teaches us the generalized geometric series $$\sum_{n \ge 0} \binom{n+k}{n} (1-\mu)^{n} \mu^k = \frac{1}{\mu}.$$ We can then study for $0 <\varepsilon &...
Landauer's user avatar
  • 173
6 votes
1 answer
153 views

An identity for rational functions leading to equations for multiple polylogarithms

The following identity is not hard to prove: $$ \sum_{1\leq i_1<i_2<\ldots <i_{2n}\leq N} (-1)^{i_1+\ldots+i_{2n}}\frac{(1-x_{i_1})(1-x_{i_3})\ldots(1-x_{i_{2n-1}})}{(1-x_{i_2})(1-x_{i_4}) \...
Daniil Rudenko's user avatar
2 votes
1 answer
250 views

Evaluations of three series involving binomial coefficients

Question. How to prove the following three identities? \begin{align}\sum_{k=1}^\infty\frac1{k(-2)^k\binom{2k}k}\left(\frac1{k+1}+\ldots+\frac1{2k}\right)=\frac{\log^22}3-\frac{\pi^2}{36},\tag{1} \end{...
Zhi-Wei Sun's user avatar
  • 13.9k
3 votes
2 answers
240 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 ...
T. Amdeberhan's user avatar
7 votes
1 answer
190 views

Reference for permanent integral identity

$\DeclareMathOperator\perm{perm}\DeclareMathOperator\diag{diag}$Using MacMahon's master theorem, the properties of complex gaussian integrals, and Cauchy's integral theorem one can show that the ...
motherboard's user avatar
18 votes
0 answers
732 views

Two curious series for $1/\pi$

On Jan. 18, 2012 I conjectured that for any prime $p>3$ we have $$R_p^2\equiv\frac1{10}\left(512\left(\frac{10}p\right)-27\left(\frac{-15}p\right)-475\right)\pmod p,$$ where $(\frac{\cdot}p)$ ...
Zhi-Wei Sun's user avatar
  • 13.9k
3 votes
1 answer
416 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{...
math110's user avatar
  • 3,718
6 votes
5 answers
838 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_{...
user avatar
3 votes
1 answer
423 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'...
T. Amdeberhan's user avatar
14 votes
2 answers
482 views

Curious identity between the two kinds of Chebyshev polynomials

I have found, by accident, an identity that relates a sum of Chebyshev polynomials of the first kind to a Chebyshev polynomial of the second kind. It goes as follows: Given an integer partition of $n$...
MannyC's user avatar
  • 243
2 votes
0 answers
194 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$ ...
Zhi-Wei Sun's user avatar
  • 13.9k