All Questions
Tagged with co.combinatorics combinatorial-identities
101 questions
46
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
...
- 6,342
32
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}...
- 15.6k
32
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; ...
- 321
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(...
- 43.2k
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,...
- 5,622
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} \...
- 1,858
24
votes
1
answer
593
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 $...
- 54.6k
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 ...
- 341
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\...
- 43.2k
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 \...
- 85.6k
18
votes
3
answers
860
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)^...
- 43.2k
16
votes
2
answers
750
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}...
- 43.2k
15
votes
2
answers
1k
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 ...
- 43.2k
13
votes
6
answers
3k
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 , ...
- 24.9k
13
votes
3
answers
1k
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}
$$
...
- 1,509
13
votes
1
answer
468
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,\...
- 15.6k
13
votes
1
answer
385
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 ...
- 13.4k
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 ...
- 43.2k
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-...
- 43.2k
12
votes
3
answers
892
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.
...
- 884
12
votes
0
answers
629
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,654
11
votes
1
answer
579
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.
...
- 43.2k
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-...
- 1,190
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?
- 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 ...
- 103
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_{\...
- 43.2k
10
votes
2
answers
484
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,772
10
votes
0
answers
349
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,190
9
votes
3
answers
2k
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 ...
- 91
9
votes
5
answers
888
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 ...
- 555
9
votes
1
answer
676
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,...
- 884
9
votes
0
answers
192
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 ...
- 15.6k
8
votes
1
answer
914
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}}.$$
- 43.2k
8
votes
1
answer
472
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 ...
- 43.2k
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?
- 81
8
votes
2
answers
325
views
A link between hooks and contents: Part II
This is a question in the spirit of an earlier problem.
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$.
Recall also the notation for the content of a cell $...
- 43.2k
8
votes
1
answer
811
views
(0,1)-matrix congruence: is it known?
[[UPDATE: This work has now been published at SIAM J Discrete Math.: Formulae for the Alon–Tarsi Conjecture.]]
By equating two formulae (one congruence by Glynn (1) (which has just appeared) and one ...
- 4,229
7
votes
3
answers
478
views
A hypergeometric identity related to Bessel functions
The identity in my recent answer can be stated in a particularly neat form:
$${}_2F_0\left({-n, n+1\atop{}};\frac{x}{2}\right) ~\cdot~ {}_2F_0\left({-n, n+1\atop{}};-\frac{x}{2}\right) ~=~ {}_3F_0\...
- 34.3k
7
votes
1
answer
286
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 ...
- 135
7
votes
1
answer
325
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 \...
- 43.2k
6
votes
2
answers
1k
views
Products and sum of cubes in Fibonacci
Consider the familiar sequence of Fibonacci numbers: $F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$.
Although it is rather easy to furnish an algebraic verification of the below identity, I wish to see a ...
- 43.2k
6
votes
2
answers
719
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 ...
- 43.2k
6
votes
5
answers
944
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
6
votes
2
answers
217
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:
$$\...
- 43.2k
6
votes
1
answer
484
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{...
- 15.6k
6
votes
2
answers
519
views
Seeking for a meaning: a curious symmetry
Suppose $\Phi(m,n)=(2m)!^n\prod_{k=1}^n\binom{2m+2k+x}{2k+x}$.
Then, algebraically, it is trivial to see that
$$(2m)!^n\prod_{k=1}^n\binom{2m+2k+x}{2k+x}=(2n)!^m\prod_{k=1}^m\binom{2n+2k+x}{2k+x}.$$
...
- 43.2k
6
votes
1
answer
2k
views
Double sum involving binomial coefficients
I came across a sum of binomial coefficients while trying to solve a problem involving $SU(2)$ group integrals. I am not able to solve it, nor I found a similar identity in the literature. I would ...
- 377
6
votes
1
answer
310
views
On the sum $\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k}$
Let $n$ be a non-negative integer.
Does there always exist a polynomial $P_n(a,b)$ such that for all integers $a > b \geq n/2$ we have
$$
\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k} = \...
- 3,927
6
votes
0
answers
235
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 ...
- 15.6k