# Questions tagged [combinatorial-identities]

The combinatorial-identities tag has no usage guidance.

**9**

votes

**1**answer

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

**0**answers

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

**2**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**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 ...

**33**

votes

**7**answers

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

**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,...

**30**

votes

**3**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**3**answers

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

**1**answer

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

**2**answers

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

**2**answers

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

**0**answers

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

**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 ...

**13**

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-...

**4**

votes

**3**answers

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

**2**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**3**answers

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

**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(...

**3**

votes

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**3**answers

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

**0**answers

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

**1**answer

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

**3**answers

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

**3**answers

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

**4**answers

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

**1**answer

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
$...