Questions tagged [combinatorial-identities]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Peter Shor's user avatar
  • 6,272
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 $...
WhatsUp's user avatar
  • 3,232
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 ...
darij grinberg's user avatar
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}...
Zhi-Wei Sun's user avatar
  • 14.4k
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; ...
ken's user avatar
  • 311
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 ...
darij grinberg's user avatar
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(...
T. Amdeberhan's user avatar
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,...
Johann Cigler's user avatar
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 ...
Alexandra Seceleanu's user avatar
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} \...
Sunni's user avatar
  • 1,858
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 \...
Terry Tao's user avatar
  • 108k
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 $...
Theo Johnson-Freyd's user avatar
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 ...
XYX's user avatar
  • 241
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\...
T. Amdeberhan's user avatar
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 \...
Gjergji Zaimi's user avatar
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}\...
darij grinberg's user avatar
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)^...
T. Amdeberhan's user avatar
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)$ ...
Zhi-Wei Sun's user avatar
  • 14.4k
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}...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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$...
MannyC's user avatar
  • 243
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,\...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Wolfgang's user avatar
  • 13.2k
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 , ...
Alexander Chervov's user avatar
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 ...
T. Amdeberhan's user avatar
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} $$ ...
Drew's user avatar
  • 1,469
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-...
T. Amdeberhan's user avatar
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. ...
Deyi Chen's user avatar
  • 844
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 \...
Amritanshu Prasad's user avatar
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 $...
darij grinberg's user avatar
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. ...
T. Amdeberhan's user avatar
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
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-...
Alexander Burstein's user avatar
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?
banana's user avatar
  • 111
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 ...
Steffen Marcus's user avatar
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_{\...
T. Amdeberhan's user avatar
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 ...
Anton Mellit's user avatar
  • 3,572
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
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{(...
Zhi-Wei Sun's user avatar
  • 14.4k
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^...
Alexander Burstein's user avatar
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 ...
Marbor's user avatar
  • 91
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 ...
Gilles Mordant's user avatar
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)} ...
Gary's user avatar
  • 91
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,...
Deyi Chen's user avatar
  • 844
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}^\...
Zhi-Wei Sun's user avatar
  • 14.4k
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/...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
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}}.$$
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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?
user45868's user avatar