Questions tagged [combinatorial-identities]
The combinatorial-identities tag has no usage guidance.
164 questions
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 $...
- 85.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 ...
- 1,593
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,...
- 1,593
4
votes
0
answers
225
views
For a combinatorial proof of a symmetric identity
In my paper Supercongruences involving dual sequences [Finite Fields Appl. 46(2017), 179-216], I gave a new symmetric identity which states that if $x+y=-1$ then
$$\sum_{k=0}^n(-1)^k\binom xk^2\binom{...
- 15.6k
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
6
votes
3
answers
1k
views
Is there a generalization (surely there is) of this simple combinatorial identity?
I was just doing some algebra on a paper and obtained: $$\sum_{l=0}^{n-1} {{n+l} \choose l}={2n \choose {n+1}}$$
Are there some generalizations of this identity?
One possible generalization would be ...
- 128k
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 ...
- 60.5k
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; ...
- 2,896
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-...
- 2,175
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} \...
- 13.4k
4
votes
3
answers
2k
views
Identities involving sums of Catalan numbers
The $n$-th Catalan number is defined as $C_n:=\frac{1}{n+1}\binom{2n}{n}=\frac{1}{n}\binom{2n}{n+1}$.
I have found the following two identities involving Catalan numbers, and my question is if ...
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}
$$
...
- 33.8k
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 \...
- 114k
8
votes
1
answer
172
views
An identity involving hook-lengths
I am reading Macdonlad's book on "symmetric functions and Hall polynomials" and I have difficulty figuring out an identity which involves hook-lengths. I would like to ask for a hint.
Let $\lambda=(\...
- 7,875
3
votes
1
answer
172
views
Proving a particular "Abel type" identiy
I have reduced solving this question to proving the following identity, for $n, \ell \ge 0$:
$$
(n-2\ell+1)^{n-1} \binom{n}{\ell-1} =
\\ \frac{1}{2} \sum_{n_1+n_2=n-1}\left[ (n_1+1)^{n_1-1} (n_2-2\...
- 516
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}.$$
...
- 3,432
1
vote
1
answer
179
views
One trig "survives" a binomial summation: why?
I've seen many trigonometric identities but here is one that I encountered for which I did not find a reference.
In case you wonder where this came from, I was investigating certain $q$-series in ...
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}...
- 6,237
1
vote
0
answers
116
views
In search of multiple expressions for a sequence
The sequence $a_n=\sum_{k=0}^n\binom{n}k^24^k$ is listed on OEIS along with a couple of combinatorial interpretations. What interested me at the moment is the plethora of binomial single-sums for the ...
- 43.2k
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 ...
- 109k
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-...
- 1,384
4
votes
3
answers
322
views
An identity for product of central binomials
This "innocent-looking" identity came out of some calculation with determinants, and I like to inquire if one can provide a proof. Actually, different methods of proofs would be of valuable merit and ...
- 43.2k
2
votes
0
answers
376
views
Reflection formula for the Hurwitz zeta function and odd zeta values
A reflection formula for the Hurwitz zeta function, which does not seem to be well known, uses half of the polynomials generated by $\frac{1}{-1+\sqrt{t-1}\cot(\sqrt{t-1}u)}$. (Look at the sections "...
CommunityBot
- 1
2
votes
1
answer
253
views
In search of a binomial identity proof
The following has strong experimental evidence.
Question. For $n\geq3k$, is this identity true? Proof?
$$\sum_{j=0}^{\lfloor\frac{k}2\rfloor}\binom{n-2k+j}{j,k-2j,n-3k+2j}=\sum_{j=0}^{\lfloor\...
- 109k
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
3
votes
2
answers
656
views
p-adic poly-Bernoulli numbers
We can define p-adic Bernoulli polynomials by using q-integral on $\mathbb{Z}_p$ and Taekyun Kim's method.
But how can we define p-adic poly-Bernoulli numbers and polynomials by using integral on $\...
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?
- 43.2k
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
2
votes
2
answers
399
views
Rational Binomial Identity
Can anyone give a reference, a proof, or a reference that explains why Maple can evaluate this identity mathematically correctly:
$$n-i-1=(d-1)\sum_{l=1}^{n-i-1}\frac{\binom{n-i-1}{l}}{\binom{n-i+d-3}...
- 43.2k
4
votes
1
answer
649
views
On Ramanujan's beautiful cubic identity
Let $a_i, b_i, c_i$ be defined by the following$\colon$
$\frac{1 + 53X + 9X^2}{1 - 82X - 82X^2 + X^3} = a_0 + a_1X + \ldots$.
$\frac{2 - 26X - 12X^2}{1 - 82X - 82X^2 + X^3} = b_0 + b_1X + \ldots$.
...
- 192
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}}.$$
- 211
5
votes
1
answer
285
views
speeding up Gosper and WZ algorithms
In our ongoing work to speed up symbolic summation and other similar algorithms in Sagemath, we notice that naive implementations of Gosper and Wilf-Zeilberger (a.k.a. WZ) algorithms are usually quite ...
- 43.2k
6
votes
2
answers
1k
views
A relation between a binomial sum and a trigonometric integral
May not be a research-level problem for an expert, but non-trivial for a non-expert: why do we have
$$ \sum_{k=0}^n \frac{(-1)^k}{2k+1} \binom{n}{k} = \frac12 \int_0^\pi (\sin x)^{2n+1} dx $$
and ...
CommunityBot
- 1
1
vote
1
answer
286
views
Evaluation of sum of factorials
Is there an evaluation of this sum (possibly involving gamma functions)? $k$ and $n$ are natural numbers and $x$ is real with $0<x<1$.
$$ \sum_{\substack{k=0\\n-k\text{ even}}}^n \frac{(-1)^{(n-...
- 15.5k
2
votes
0
answers
153
views
system of complex number equations
Let $a_1,a_2,a_3,a_4\in \mathbb{C}$ be distinct such that
$$a_1^3+a_2^3+a_3^3+a_4^3=0$$
$$(1+|a_1|^2)a_1^2+(1+|a_2|^2)a_2^2+(1+|a_3|^2)a_3^2+(1+|a_4|^2)a_4^2=0$$
$$(1+2|a_1|^2+2|a_1|^4)a_1+(1+2|a_2|^...
CommunityBot
- 1
3
votes
1
answer
242
views
system of complex equations
I am working on a system of complex equations The question is the following:
Let $a_1,a_2,\ldots,a_N\in \mathbb{C}$ such that
$$\sum_{j=1}^N \sum_{q=0}^{N-1-k} {N-1 \choose q} {N-1 \choose k+q} |a_j|...
2
votes
0
answers
138
views
A combinatorial sum involving ratios of binomials [closed]
Can anyone suggest how to prove the following (for $k \le n$):
$$\sum \limits_{s=0}^N \frac{\binom{n}{k} \binom{N-n}{s-k} }{\binom{N}{s}} = \frac{N+1}{n+1}$$
I am assuming it to be true, and ...
- 1,228
3
votes
2
answers
466
views
equality of expressions for sum
Assume I have a chain of real numbers, s.th.
$x_0 < y_0 < x_1<y_1<x_2<\dots <x_n<y_n$.
I'm trying to explicitely solve the expression
$$ \sum_{i=0}^n \frac{\prod_{j=0}^n(x_j-y_i)...
- 33.8k
2
votes
1
answer
476
views
Alternating sign binomial identity [closed]
I recently noticed that for a triple of integers $k \geq 2$, $k \geq m \geq t \geq 1$, the following identity seems to hold
$\sum_{j=0}^{m-t} (-1)^{m-t-j}{k \choose j}{m-1-j \choose t-1}={k-t \choose ...
- 13.4k
0
votes
1
answer
156
views
Is it possible to write identity for $ \{x(y^2-z^2)-y\}.\{u(v^2-w^2)-v)\}=a(b^2-c^2)-b$? [closed]
I asked this question in "math.stackexchange" but I did not get any response, so I put it here, maybe someone can help.
Is it possible to write identity similar to the identity
$$
(x^2+y^2)(u^2+v^2)=...
- 841
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 ...
- 1,044
2
votes
0
answers
187
views
Multiplying three factorials with three binomials in polynomial identity
I have checked the following identity (1) below for $n\leq 40$ with a computer.
Let $(n)_k$ denote the falling factorial $n(n-1)\ldots (n-k+1)$, let
$Z_n=\sum_{k=0}^n (n)_k x^{n-k}$, and finally let
$...
CommunityBot
- 1
7
votes
4
answers
644
views
Permanent identities for special classes of matrices
The permanent $P(M)$ of a matrix $M$ of size $n$ is defined to be:
$$
P(M) := \sum_{\sigma \in S_n}\prod_{i=1}^n M_{i\sigma(i)}
$$
If you have a matrix of the form
$$
M_{ij} := A_i + B_j
$$
where ...
- 341
6
votes
2
answers
912
views
Closed form or/and asymptotics of a hypergeometric sum
Dear mathematicians,
I am a computer scientist wandering in the deep sea of combinatorics and asymptotics to pursue a recent interest in average case analysis of algorithms. In doing so, I designed ...
- 690
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 ...
CommunityBot
- 1
2
votes
1
answer
1k
views
A formula combining Euler $\phi$ and $\gcd$
Let us fix a natural number $N>1$ and $a_1, \ldots, a_n$ natural numbers satisfying $0 \leq a_i < N$, with the property that $1+ \sum a_i$ is divisible by $N$. Let $\phi$ be the Euler totient ...
CommunityBot
- 1
0
votes
1
answer
106
views
positive expression
Let
$$a_{n,k}=\sum_{s_i \geq 1 \atop \sum_{i=1}^{n-k} s_i \leq n} \frac{2^{n}}{(2(n-\sum_{i=1}^{n-k} s_i)+1)!\prod_{i=1}^{n-k} (2s_i)! }$$
for $0 \leq k \leq n-1$. Prove for $1 \leq k \leq n-1$ that
$...
CommunityBot
- 1
2
votes
1
answer
998
views
Identity of binomial series with factorial.
I'm looking for a simple identity for the formula:
$$
\sum_{n = 0}^{p} \binom{p}{n} \cdot n! \cdot x^n
$$
In words, I have $p$ "players" who can choose to play or not (every player is represented by ...
- 41.1k
5
votes
1
answer
2k
views
Number of Permutations with k-inversions and with a single clamped value
This question is cross-posted from math.stackexchange because it might be too technical.
Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the ...
CommunityBot
- 1
1
vote
2
answers
1k
views
An identity involving a sum of binomial coefficients
I am moving through a classic paper (On Average Height of Planted Plane Trees by Knuth, de Bruijn and Rice, 1972), and I would like to trade a weaker result for simpler mathematical tools, because my ...
