Questions tagged [combinatorial-identities]
The combinatorial-identities tag has no usage guidance.
151
questions
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 $\...
- 41k
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 $ ...
- 63
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}...
- 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 ...
- 41k
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+\...
- 41k
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}{...
- 1,678
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\...
- 41k
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?
- 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}...
- 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 ...
- 103
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[\...
- 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{(...
- 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}^\...
- 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 ...
- 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{...
- 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/...
- 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 \...
- 5,504
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&...
- 41k
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 + ...
- 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=...
- 41k
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}...
- 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 ...
- 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)...
- 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-...
- 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*}%...
- 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}^...
- 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 ...
- 41k
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 ...
- 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-...
- 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}\...
- 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.
...
- 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, ...
- 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 ...
- 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,...
- 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 ...
- 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, ...
- 41k
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 \...
- 41k
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^...
- 1,088
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:
$$\...
- 41k
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 &...
- 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}) \...
- 4,226
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{...
- 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 ...
- 41k
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 ...
- 241
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)$ ...
- 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{...
- 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_{...
user153001
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'...
- 41k
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$...
- 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$ ...
- 13.9k