Questions tagged [combinatorial-identities]
The combinatorial-identities tag has no usage guidance.
161
questions
45
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
votes
7
answers
3k
views
On the polynomial $\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}$
Let $n = 2m$ be an even integer and let $F_n(X)$ be the polynomial $$F_n(X):=\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}.$$ I observed (but cannot prove) that the polynomial $F_n$ is always divisible by $...
32
votes
2
answers
2k
views
Generalization of Tamarkin's ARO 1993, final round, problem 10/8: still a conjecture?
This is from the category "problems I cannot believe that are still open". But then again, I don't know whether it is still open; it seems to have escaped the attention of most number theorists and ...
31
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}...
31
votes
3
answers
2k
views
Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$
In my research, I found this identity and as I experienced, it's surely right. But I can't give a proof for it.
Could someone help me?
This is the identity:
let $a$ and $b$ be two positive integers; ...
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 ...
28
votes
3
answers
3k
views
Sum over permutations is 1
This might be easy, but let's see.
Question 1. If $\mathfrak{S}_n$ is the group of permutations on $[n]$, then is the following true?
$$\sum_{\pi\in\mathfrak{S}_n}\prod_{j=1}^n\frac{j}{\pi(1)+\pi(...
27
votes
2
answers
1k
views
Some binomial coefficient determinants
It is well known that for $n>0$
$$d(n)=\det\left(\binom{2i+2j+1}{i+j}\right)_{i,j=0}^{n-1}=1.$$
Computer experiments suggest that more generally
$$d(n,k)=\det\left(\binom{2i+2j+2k+1}{i+j}\right)_{i,...
26
votes
3
answers
4k
views
Is the sum $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0?$
I am trying to prove $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$. This inequality has been verified by computer for $k\le40$.
Some clues that might work (kindly provided by ...
26
votes
2
answers
2k
views
Is there a combinatorial interpretation of the identity $\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m} =4^{-m} \binom{4m+1}{2m}$?
I came across the following combinatorial identity in a paper by Victor H. Moll and Dante V. Manna 'a remarkable sequence of integers'.
$$\sum_{k=0}^m 2^{-2k} \binom{2k}{k} \binom{2m-k}{m}
=4^{-m} \...
24
votes
2
answers
2k
views
Reference for exponential Vandermonde determinant identity
I recently stumbled upon the following identity, valid for any real numbers $\alpha_1,\dots,\alpha_n$ and $\lambda_{n1} \leq \dots \leq \lambda_{nn}$:
$$ \mathrm{det}( e^{\alpha_i \lambda_{nj}} )_{1 \...
24
votes
1
answer
585
views
Has the $E_8$-based generating function for squares numbers been proven?
In his 2004 paper Conformal Field Theory and Torsion Elements of the Bloch Group, Nahm explains a physical argument due to Kadem, Klassen, McCoy, and Melzer for the following remarkable identity. Let $...
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 ...
20
votes
1
answer
1k
views
A proof required for this identity [duplicate]
Experiments support the below identity.
Question. Is this true? Combinatorial proof preferred if possible.
$$\sum_{m=0}^n\binom{n-\frac13}m\binom{n+\frac13}{n-m}(1+6m-3n)^{2n+1}
=\left(\frac43\...
19
votes
2
answers
2k
views
What role does Cauchy's determinant identity play in combinatorics?
When studying representation theory, special functions or various other topics one is very likely to encounter the following identity at some point:
$$\det \left(\frac{1}{x _i+y _j}\right) _{1\le i,j \...
18
votes
3
answers
2k
views
A binomial sum is divisible by p^2
This is a question I have since longer time, but I have absolutely no idea how to proceed on it.
Let $p>3$ be a prime. Prove that $\displaystyle\sum\limits_{k=1}^{p-1}\frac{1}{k}\binom{2k}{k}\...
18
votes
3
answers
858
views
$\prod_k(x\pm k)$ in binomial basis?
Let $x$ be an indeterminate and $n$ a non-negative integer.
Question. The following seems to be true. Is it?
$$x\prod_{k=1}^n(k^2-x^2)=\frac1{4^n}\sum_{m=0}^n\binom{n-x}m\binom{n+x}{n-m}(x+2m-n)^...
18
votes
0
answers
745
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)$ ...
16
votes
2
answers
743
views
Sum of multinomals = sum of binomials: why?
I stumbled on the following identity, which has been checked numerically.
Question. Is this true? If so, any proof?
$$\sum_{j=0}^{\lfloor\frac{k}2\rfloor}\binom{n-2k+j}{j,k-2j,n-3k+2j}
=\sum_{j=0}...
15
votes
2
answers
965
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 ...
14
votes
2
answers
570
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$...
13
votes
1
answer
420
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,\...
13
votes
1
answer
375
views
Some more binomial coefficient determinants
The setup is similar to this question, but generalizes the size of the Hankel matrix. We'll define
$$d(n,k,r):=\det\left(\binom{2i+2j+k+r}{i+j}\right)_{i,j=0}^{kn-1}.$$
Edit: Thanks to Johann ...
12
votes
6
answers
2k
views
A sum involving derivatives of Vandermonde
Consider the standard Vandermonde $V(x_1, \ldots, x_n) = \prod_{i < j} (x_i - x_j)$.
I am intersted in the calculation of the following expression for fixed $k$:
$$\sum_i (x_i)^k (d/dx_i)^k V(x_1 , ...
12
votes
3
answers
1k
views
A "quantum" identity: in search of a proof -Part II
As usual, denote $[n]_q=1+q+\cdots+q^{n-1}=\frac{\,\,1-q^n}{1-q}$ and $[n]_q!=[1]_q[2]_q\cdots[n]_q$. Furthermore, we write
$$\binom{n}k_q=\frac{[n]_q!}{[k]_q!\cdot[n-k]_q!}.$$
As a follow up on this ...
12
votes
3
answers
981
views
Identity with binomial coefficients and k^k
In process of doing some computations on Hilbert schemes, I stumbled across the following identity, for $k \ge 2$:
$$
k^{k-3} = \frac{1}{2} \sum_{i=1}^{k-1} \binom{k-2}{i-1} i^{i-2} (k-i)^{k-i-2}
$$
...
12
votes
2
answers
1k
views
An interesting identity: in search of a proof -Part I
I like the following binomial identity in that the RHS extracts the indeterminate $w$ from the LHS.
Question. Can you show that
$$\sum_{k=0}^n\binom{x+kw}k\binom{y-kw}{n-k}=\sum_{k=0}^n\binom{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.
...
12
votes
0
answers
497
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 \...
11
votes
3
answers
3k
views
Gauss sum (with sign) through algebra
Let $p$ be an odd prime, and $\zeta$ a primitive $p$-th root of unity over a field of characteristic $0$.
Let $G = \sum\limits_{j=0}^{p-1} \zeta^{j\left(j-1\right)/2}$ be the standard Gauss sum for $...
11
votes
1
answer
569
views
Catalan determinants in search of a proof: Part II
This problem involves the Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$.
I can prove the below equality by computing each of the two sides, directly. That means, there is an algebraic proof.
...
11
votes
1
answer
973
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 ...
11
votes
2
answers
1k
views
Proofs of some combinatorial identities
Just wondering if anyone knows any references in the literature to bijections corresponding to the following simple generating function identities. Let $B(z)=\dfrac{1}{\sqrt{1-4z}}$ and $C(z)=\dfrac{1-...
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
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 ...
10
votes
2
answers
1k
views
A cancellation property for permutations?
Let $S_n$ be the group of $n$-permutations. Denote the number of inversions of $\sigma\in S_n$ by $\ell(\sigma)$.
QUESTION. Assume $n>2$. Does this cancellation property hold true?
$$\sum_{\...
10
votes
2
answers
454
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 ...
10
votes
1
answer
530
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 ...
10
votes
0
answers
490
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
0
answers
342
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^...
9
votes
3
answers
1k
views
Combinatorial identities
I have computational evidence that
$$\sum_{k=0}^n \binom{4n+1}{k} \cdot \binom{3n-k}{2n}= 2^{2n+1}\cdot \binom{2n-1}{n}$$
but I cannot prove it. I tried by induction, but it seems hard. Does anyone ...
9
votes
5
answers
840
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 ...
9
votes
2
answers
818
views
An identity involving an infinite integral with a sinh in the denominator
I recently encountered the rather appealing looking integral, which appears in the theory of random matrices :
$$\int_{-\infty}^{\infty}\prod_{j=1}^{p-1}(j^{2}+z^{2})\frac{zdz}{\mathrm{sinh}(2\pi z)} ...
9
votes
1
answer
655
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,...
9
votes
1
answer
387
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}^\...
9
votes
1
answer
961
views
A conjecture on primitive tenth roots of unity
QUESTION. How to solve my following conjecture involving primitive tenth roots of unity?
Conjecture. Let $\zeta$ be any primitive tenth root of unity. Then
$$\prod_{k=1}^{(p-1)/2}(\zeta-e^{2\pi ik^2/...
9
votes
0
answers
191
views
For $q$-analogues of a known curious identity
In 2002 I published the folllowing curious combinatorial identity:
$$(x+m+1)\sum_{i=0}^m(-1)^i\binom{x+y+i}{m-i}\binom{y+2i}i-\sum_{i=0}^m\binom{x+i}{m-i}(-4)^i=(x-m)\binom xm.$$
My original proof is ...
8
votes
1
answer
907
views
A special binomial identity in need of a proof
I've encountered a curious identity as a codicil in some work. Is there a proof or reference?
$$\sum_{k=-n}^n\frac{2k+1}{n+k+1}\binom{2n}{n-k}\frac{x^k}{1+x^{2k+1}}=\frac{x^n}{1+x^{2n+1}}.$$
8
votes
1
answer
464
views
In search of a combinatorial reasoning for a vanishing sum
Assume $s, j \in\mathbb{N}$. Define the set
$$\mathcal{A}_{j,s}:=\{(n_1,n_2,\dots,n_j)\in\mathbb{Z}_{\geq0}^j\vert \,
n_1+2n_2+\cdots+jn_j=j, \, n_1+n_2+\cdots+n_j=s\}.$$
Question. Is there a ...
8
votes
3
answers
1k
views
Binomial Identity
I recently noted that
$$\sum_{k=0}^{n/2} \left(-\frac{1}{3}\right)^k\binom{n+k}{k}\binom{2n+1-k}{n+1+k}=3^n$$
Is this a known binomial identity? Any proof or reference?