Questions tagged [combinatorial-identities]
The combinatorial-identities tag has no usage guidance.
31 questions
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 ...
11
votes
1
answer
579
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.
...
- 43.2k
3
votes
1
answer
439
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'...
- 43.2k
30
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 ...
- 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
18
votes
3
answers
860
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)^...
- 43.2k
13
votes
6
answers
3k
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 , ...
- 24.9k
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-...
- 1,190
7
votes
1
answer
325
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 \...
- 43.2k
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 $...
- 3,432
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; ...
- 321
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
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,...
- 5,622
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}\...
- 33.8k
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}
$$
...
- 1,509
12
votes
3
answers
892
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.
...
- 884
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-...
- 43.2k
10
votes
1
answer
434
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}^\...
- 15.6k
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 ...
- 103
10
votes
0
answers
349
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^...
- 1,190
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
8
votes
0
answers
351
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 ...
- 15.6k
8
votes
2
answers
325
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 $...
- 43.2k
7
votes
3
answers
478
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\...
- 34.3k
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}^...
- 237
6
votes
1
answer
519
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, ...
- 15.6k
5
votes
1
answer
1k
views
A (known?) hypergeometric identity
Incidentally I've obtained a hypergeometric identity that I've not seen before:
$${}_3F_2(-m,-n,m+n; 1, 1; 1) = \frac{m^2+n^2+mn}{(m+n)^2} {\binom{m+n}{m}}^2$$
So, I wonder if it is well-known and ...
- 34.3k
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 ...
- 4,952
4
votes
0
answers
208
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+\...
- 43.2k
3
votes
1
answer
186
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, ...
- 43.2k
2
votes
1
answer
507
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)...
