Questions tagged [combinatorial-identities]
The combinatorial-identities tag has no usage guidance.
9
votes
1answer
631 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_{\...
7
votes
0answers
238 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 ...
7
votes
2answers
343 views
A conjecture involving roots of unity
Motivated by Kevin Liu's recent question, here I pose the following conjecture based on my numerical computation.
Conjecture. Let $m>1$ and $n>1$ be integers. Let $\delta\in\{0,1\}$ and let $\...
5
votes
1answer
307 views
A surprising identity: $\det[\cos\pi\frac{jk}n]_{1\le j,k\le n}=(-1)^{\lfloor\frac{n+1}2\rfloor}(n/2)^{(n-1)/2}$
On the basis of my computation, here I pose my following conjecture involving the cosine function.
Conjecture. For any positive integer $n$, we have the identity
$$\frac1{2n}\det\left[\cos\pi\frac{jk}...
7
votes
2answers
182 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 $...
21
votes
1answer
968 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\...
24
votes
1answer
526 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 $...
4
votes
0answers
150 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{...
8
votes
0answers
148 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 ...
12
votes
1answer
279 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 ...
6
votes
3answers
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 ...
33
votes
7answers
1k 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 $...
26
votes
2answers
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,...
30
votes
3answers
1k 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; ...
10
votes
2answers
773 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-...
20
votes
2answers
1k 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 \...
6
votes
1answer
155 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=(\...
3
votes
1answer
137 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\...
12
votes
3answers
594 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
vote
1answer
165 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
2answers
688 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}...
7
votes
2answers
266 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^...
1
vote
0answers
100 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 ...
13
votes
3answers
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 ...
13
votes
2answers
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-...
4
votes
3answers
287 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 ...
6
votes
2answers
504 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}.$$
...
2
votes
0answers
119 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 "...
2
votes
1answer
198 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\...
8
votes
1answer
393 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 ...
16
votes
3answers
748 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)^...
26
votes
3answers
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(...
3
votes
1answer
492 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$.
...
7
votes
1answer
830 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}}.$$
3
votes
1answer
146 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 ...
6
votes
2answers
832 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 ...
1
vote
1answer
220 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-...
3
votes
1answer
222 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
0answers
126 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 ...
2
votes
0answers
141 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|^...
3
votes
2answers
371 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)...
2
votes
1answer
244 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 ...
0
votes
1answer
151 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)=...
4
votes
3answers
721 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 ...
2
votes
0answers
176 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
$...
6
votes
1answer
1k 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 ...
8
votes
3answers
948 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?
9
votes
3answers
763 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 ...
7
votes
4answers
440 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 ...
0
votes
1answer
102 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
$...
