Questions tagged [combinatorial-identities]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Alexandra Seceleanu's user avatar
11 votes
1 answer
569 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. ...
T. Amdeberhan's user avatar
3 votes
1 answer
434 views

An identity for polynomials over partitions

Given an integer partition $\lambda=(\lambda_1,\dots,\lambda_{\ell(\lambda)})$ of $n$ where $\ell(\lambda)$ is the length of $\lambda$, associate its conjugate partition $\lambda'$. Denote by $\lambda'...
T. Amdeberhan's user avatar
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 \...
Terry Tao's user avatar
  • 108k
18 votes
3 answers
858 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)^...
T. Amdeberhan's user avatar
12 votes
6 answers
2k 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 , ...
Alexander Chervov's user avatar
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-...
Alexander Burstein's user avatar
7 votes
1 answer
308 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 \...
T. Amdeberhan's user avatar
33 votes
7 answers
3k 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 $...
WhatsUp's user avatar
  • 3,232
31 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; ...
ken's user avatar
  • 311
29 votes
4 answers
3k views

A mysterious Heisenberg algebra identity from Sylvester, 1867

I am trying to understand two papers by James Joseph Sylvester: P92: "Note on the properties of the test operators which occur in the calculus of invariants, their derivatives, analogues, and laws of ...
darij grinberg's user avatar
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(...
T. Amdeberhan's user avatar
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,...
Johann Cigler's user avatar
18 votes
3 answers
2k views

A binomial sum is divisible by p^2

This is a question I have since longer time, but I have absolutely no idea how to proceed on it. Let $p>3$ be a prime. Prove that $\displaystyle\sum\limits_{k=1}^{p-1}\frac{1}{k}\binom{2k}{k}\...
darij grinberg's user avatar
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-...
T. Amdeberhan's user avatar
12 votes
3 answers
864 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. ...
Deyi Chen's user avatar
  • 844
12 votes
3 answers
982 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} $$ ...
Drew's user avatar
  • 1,469
10 votes
0 answers
342 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^...
Alexander Burstein's user avatar
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 ...
Steffen Marcus's user avatar
9 votes
1 answer
387 views

Series for $\frac{\log m}{\pi}$ with summands involving harmonic numbers

The classical rational Ramanujan-type series for $1/\pi$ have the following four forms: \begin{align}\sum_{k=0}^\infty(ak+b)\frac{\binom{2k}k^3}{m^k}&=\frac{c}{\pi},\label{1}\tag{1} \\\sum_{k=0}^\...
Zhi-Wei Sun's user avatar
  • 14.4k
8 votes
2 answers
301 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 $...
T. Amdeberhan's user avatar
8 votes
1 answer
464 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 ...
T. Amdeberhan's user avatar
8 votes
0 answers
315 views

A hypergeometric series for $\sqrt3\pi$ with converging rate $1/9$

Recently, I found a (conjectural) new series for $\sqrt3\pi$: $$\sum_{k=1}^\infty\frac{(8k-3)\binom{4k}{2k}}{k(4k-1)9^k\binom{2k}k^2}=\frac{\sqrt3\pi}{18}.\label{1}\tag{1}$$ The series converges fast ...
Zhi-Wei Sun's user avatar
  • 14.4k
7 votes
1 answer
1k views

Identity involving sum over permutations

In some work on QFT the following identity has come up: $$ \sum_{\sigma \in S_n}\sum_{j=1}^n \left(\sum_{l=1}^j w_{\sigma_l}\right)\prod_{i=1,i\neq j}^{n}\frac{1}{\sum_{l=1}^j z_{\sigma_l}-\sum_{l=1}^...
Petter's user avatar
  • 237
7 votes
3 answers
435 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\...
Max Alekseyev's user avatar
6 votes
1 answer
506 views

A novel identity connecting permanents to Bernoulli numbers

For a matrix $[a_{j,k}]_{1\le j,k\le n}$ over a field, its permanent is defined by $$\mathrm{per}[a_{j,k}]_{1\le j,k\le n}:=\sum_{\pi\in S_n}\prod_{j=1}^n a_{j,\pi(j)}.$$ In a recent preprint of mine, ...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Alex R.'s user avatar
  • 4,902
4 votes
0 answers
200 views

Extract this constant term

Given a Laurent polynomial $F$ in the variables $\mathbf{t}=(t_1,\dots,t_n)$, let $CT_{\vec{\mathbf{t}}}\,F$ denote its constant term. For example, $CT_{t_1,t_2}((8t_1-\frac1{3t_1t_2})(5t_1t_2+t_2^2+\...
T. Amdeberhan's user avatar
3 votes
1 answer
174 views

Is there a $q$-analogue to Shapiro's convolution identity?

Let $C_n=\frac1{n+1}\binom{2n}n$ denote the Catalan numbers. This question is motivated by the (unanswered) MO post by Alexander Burstein and my own (answered by Fedor Petrov) MO post. Specifically, ...
T. Amdeberhan's user avatar
2 votes
1 answer
485 views

Integer eigenvalues of a class of matrices inspired by Prof. Zhi-Wei Sun's conjecture

Theorem: Let $n>1$ be an odd number and $\zeta$ a primitive $n$-th root of unity. Then \begin{eqnarray} &&\sum_{\tau\in D(n-1)}\mathrm{sign}(\tau)\prod_{j=1}^{n-1}\frac{1}{1-\zeta^{j-\tau(j)...
Keqin Liu 'Kevin''s user avatar