Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatorial-identities]

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