Questions tagged [combinatorial-identities]
The combinatorial-identities tag has no usage guidance.
161
questions
11
votes
1
answer
979
views
Is it true that $\sum_{k=1}^\infty\frac{\binom{2k}k^2}{k16^k}(H_{2k}-H_k)=\frac23\sum_{k=1}^\infty\frac{\binom{2k}k^2H_{2k}}{(2k+1)16^k}$?
On Jan. 27, 2012, I conjectured the identity
$$\sum_{k=1}^\infty\frac{\binom{2k}k^2}{k16^k}(H_{2k}-H_k)=\frac23\sum_{k=1}^\infty\frac{\binom{2k}k^2H_{2k}}{(2k+1)16^k},\tag{$*$}$$
where $H_n$ denotes ...
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 ...
4
votes
1
answer
203
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 ...
2
votes
1
answer
668
views
Transfinite sums related to a sequence
Given a sequence $S$ indexed by the finite ordinals, a limit ordinal $\alpha$, and $k \in \mathbb{N}$, define $S_{\alpha+k}$(the extension of $S$ to $\alpha+k$) to be the sum over the products of all $...
6
votes
2
answers
706
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 ...
13
votes
1
answer
421
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,\...
8
votes
3
answers
582
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}...
3
votes
1
answer
416
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
177
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{...
1
vote
1
answer
226
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
316
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 ...
6
votes
1
answer
421
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
221
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
0
answers
284
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 ...
3
votes
3
answers
718
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
406
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 $ ...
4
votes
0
answers
92
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
200
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+\...
3
votes
1
answer
212
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
228
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}{...
0
votes
0
answers
261
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
272
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
199
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
493
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{(...
9
votes
1
answer
389
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}^\...
2
votes
2
answers
271
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}^...
4
votes
0
answers
215
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 ...
8
votes
1
answer
530
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/...
5
votes
1
answer
301
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}...
1
vote
1
answer
211
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&...
12
votes
0
answers
504
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 \...
3
votes
2
answers
416
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
197
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=...
6
votes
1
answer
161
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}) \...
3
votes
1
answer
361
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 ...
10
votes
1
answer
531
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 ...
2
votes
1
answer
487
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)...
6
votes
1
answer
506
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, ...
1
vote
1
answer
211
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-...
-1
votes
1
answer
336
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*}%...
3
votes
2
answers
430
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-...
29
votes
4
answers
3k
views
A mysterious Heisenberg algebra identity from Sylvester, 1867
I am trying to understand two papers by James Joseph Sylvester:
P92: "Note on the properties of the test operators which occur in the calculus of invariants, their derivatives, analogues, and laws of ...
15
votes
2
answers
968
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
455
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 ...
5
votes
3
answers
668
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 ...
7
votes
1
answer
233
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 ...
4
votes
1
answer
142
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
864
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.
...
5
votes
3
answers
751
views
Identity with Pochhammer and harmonic numbers
This came out of some work on the digamma function.
Let $(x)_k=x(x+1)\cdots(x+k-1)$ denote the Pochhammer symbol. Then,
Question. Can you prove/disprove this identity?
$$\pmb{\frac{(\frac12)_j^...