Questions tagged [combinatorial-identities]
The combinatorial-identities tag has no usage guidance.
114
questions
8
votes
0answers
261 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^...
6
votes
2answers
181 views
A convolution-type identity for the “major index”
For a permutation $\pi\in\frak{S}_n$, define the number of descents of $\pi$ as $$\text{des}(\pi)=\vert\{i: \pi(i)>\pi(i+1)\}\vert.$$
The following is a well-known (and interesting) identity:
$$\...
3
votes
2answers
58 views
Optimal scaling of Lipschitz estimates in generalized geometric series
If we did not know it before, then wikipedia teaches us the generalized geometric series
$$\sum_{n \ge 0} \binom{n+k}{n} (1-\mu)^{n} \mu^k = \frac{1}{\mu}.$$
We can then study for $0 <\varepsilon &...
5
votes
0answers
53 views
An identity for rational functions leading to equations for multiple polylogarithms
The following identity is not hard to prove:
$$
\sum_{1\leq i_1<i_2<\ldots <i_{2n}\leq N} (-1)^{i_1+\ldots+i_{2n}}\frac{(1-x_{i_1})(1-x_{i_3})\ldots(1-x_{i_{2n-1}})}{(1-x_{i_2})(1-x_{i_4})\...
2
votes
1answer
170 views
Evaluations of three series involving binomial coefficients
Question. How to prove the following three identities?
\begin{align}\sum_{k=1}^\infty\frac1{k(-2)^k\binom{2k}k}\left(\frac1{k+1}+\ldots+\frac1{2k}\right)=\frac{\log^22}3-\frac{\pi^2}{36},\tag{1}
\end{...
3
votes
2answers
226 views
Is there a combinatorial reason for variable-independence of this binomial-coefficient identity?
Consider the following identity
$$\sum_{n=0}^{R-t}\binom{n+\ell}n\binom{R-\ell-n}{R-t-n}=\binom{R+1}{t+1}.\tag1$$
It is relatively easy to give an algebraic or mechanical proof of (1). But, I like to ...
6
votes
0answers
92 views
Reference for permanent integral identity
$\DeclareMathOperator\perm{perm}\DeclareMathOperator\diag{diag}$Using MacMahon's master theorem, the properties of complex gaussian integrals, and Cauchy's integral theorem one can show that the ...
18
votes
0answers
658 views
Two curious series for $1/\pi$
On Jan. 18, 2012 I conjectured that for any prime $p>3$ we have
$$R_p^2\equiv\frac1{10}\left(512\left(\frac{10}p\right)-27\left(\frac{-15}p\right)-475\right)\pmod p,$$
where $(\frac{\cdot}p)$ ...
3
votes
1answer
303 views
How to prove this combinatorial identity?
If $n \in \mathbb N \setminus \{0\}$ and $x,y,z \in \mathbb R$ such that $x+y+z=n-1$, show that
$$\dfrac{(-4)^n}{\binom{2x}{n}}\sum_{r+s=n,r,s\in Z}\dfrac{\binom{y}{r}\binom{y-a}{r}\binom{z}{s}\binom{...
6
votes
5answers
691 views
Combinatorial proof of Catalan's identity
Consider the problem of tiling a board of length $n$ with squares of size $1×1$ and dominoes of size $1×2$, Let's denote $f_n$ to be the number of ways to tile this so-called ($n$)-board.Then $f_n=F_{...
3
votes
1answer
391 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'...
12
votes
2answers
292 views
Curious identity between the two kinds of Chebyshev polynomials
I have found, by accident, an identity that relates a sum of Chebyshev polynomials of the first kind to a Chebyshev polynomial of the second kind. It goes as follows:
Given an integer partition of $n$...
2
votes
0answers
181 views
For human proofs of two novel combinatorial identities
For $n=0,1,2,\ldots$, let us define the polynomial
$$S_n(x):=\sum_{k=0}^n\binom{x/2}k\binom{(x-1)/2}k\binom{-(x+1)/2}{n-k}\binom{-(x+2)/2}{n-k}.$$
Such polynomials occur in some series for $1/\pi$ ...
5
votes
1answer
218 views
On the sum $\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k}$
Let $n$ be a non-negative integer.
Does there always exist a polynomial $P_n(a,b)$ such that for all integers $a > b \geq n/2$ we have
$$
\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k} = \...
1
vote
2answers
186 views
Bilinear recurrence relation between even Bernoulli numbers
Throughout this question $n$ is a positive integer greater than 1.
Consider the following well-known identity by Euler,
$$\sum_{k=1}^{n-1} \binom{2n}{2k}B_{2k}B_{2n-2k}=-(2n+1)B_{2n}.$$
Rather ...
4
votes
1answer
264 views
“Non-associative” standard polynomials
I saw somewhere (I appreciate if anyone has any references to proof of this fact) that if $A$ is a finite dimensional associative algebra such that $\textrm{dim}(A)<n$, then $A$ satisfies the ...
4
votes
2answers
421 views
Showing this formula counts these things
I'm writing an article, and I got stuck trying to prove that some numbers are positive. I have a relatively good intuition for guessing what an expression is counting, but in this case I'm not being ...
5
votes
0answers
199 views
Sum over permutations involving sign
The problem is to evaluate the following sum over all permutations $\sigma\in S_{d}$ of $\{1,2,...,d\}$:
$\displaystyle\sum_{\sigma\in S_{d}}\text{sgn}(\sigma)\displaystyle\frac{1}{\prod_{i=1}^{d}(\...
9
votes
1answer
894 views
A conjecture on primitive tenth roots of unity
QUESTION. How to solve my following conjecture involving primitive tenth roots of unity?
Conjecture. Let $\zeta$ be any primitive tenth root of unity. Then
$$\prod_{k=1}^{(p-1)/2}(\zeta-e^{2\pi ik^2/...
1
vote
0answers
74 views
A $1$-step convolution identity involving the Motzkin triangle
The Motzkin triangle $T(n,k)$ is built according to the rules:
(1) $T(n,0)=1$;
(2) $T(n,k)=0$ if $k<0$ or $k>n$;
(3) $T(n,k)=T(n-1,k-2)+T(n-1,k-1)+T(n-1,k)$.
After some numerical evidence I ...
9
votes
5answers
705 views
Sums of binomial coefficients weighted by incomplete gamma
I am interested in proving that
$$\sum_{k=0}^n\frac{k}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}=1
$$
and
$$\sum_{k=0}^n\frac{k^2}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}=2.
$$
I verified it numerically ...
-1
votes
1answer
240 views
How do I calculate this sum $\sum_k(k!)^{-n}$? [closed]
How do I evaluate the following finite sum over $k$
$1+\frac{1}{2^n}+\frac{1}{2^n3^n}+\frac{1}{2^n3^n4^n}+\cdots+\frac{1}{2^n3^n\cdots k^n}$
or if there is an expression of this sum in terms of ...
30
votes
3answers
2k views
A conjectural trigonometric identity
Recently, I formulated the following conjecture which seems novel.
Conjecture. For any positive odd integer $n$, we have the identity
$$\sum_{j,k=0}^{n-1}\frac1{\cos 2\pi j/n+\cos 2\pi k/n}=\frac{n^2}...
6
votes
3answers
296 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\...
7
votes
1answer
400 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}^...
4
votes
1answer
248 views
About binomial identity
During my research, I checked using Maple that we have numerically for $ 2 \leq n \leq 20,$ $ \forall t $ integer satisfying $ 0 \leq t \leq n-1$
$$ \displaystyle \frac{1}{2} \displaystyle \sum_{p=...
1
vote
0answers
451 views
Two conjectural identities involving $\zeta(3)$ and the golden ratio $\phi$
Let $\phi$ be the famous golden ratio $\frac{\sqrt5+1}2$, and let
$\zeta(3)=\sum_{n=1}^\infty\frac1{n^3}.$
In 2014, in the paper
Zhi-Wei Sun, New series for some special values of $L$-functions, ...
2
votes
0answers
165 views
Equality of determinants: a direct justification request
Let $I_k$ denote the enumeration of involutions among permutations in $\mathfrak{S}_k$. Here is yet another cute finding for which I ask a:
Question. Is there a direct proof (or interpretation or ...
0
votes
3answers
223 views
How to calculate$ \sum \limits_{k=0}^{m-n} {m-k-1 \choose n-1} {k+n \choose n}$?
How to calculate $$\sum\limits_{k=0}^{m-n} {m-k-1 \choose n-1} {k+n \choose n}.$$
3
votes
3answers
367 views
How to calculate: $\sum\limits_{k=0}^{n-m} \frac{1}{n-k} {n-m \choose k}$
How to calculate:
$$\sum _{k=0}^{n-m} \frac{1}{n-k} {n-m \choose k}.$$
6
votes
2answers
880 views
Products and sum of cubes in Fibonacci
Consider the familiar sequence of Fibonacci numbers: $F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$.
Although it is rather easy to furnish an algebraic verification of the below identity, I wish to see a ...
2
votes
2answers
246 views
Alternating binomial-harmonic sum: evaluation request
Let $H_k=\sum_{j=1}^k\frac1j$ be the harmonic numbers.
QUESTION. Can you find an evaluation of the following sum?
$$\sum_{a=1}^b(-1)^a\binom{n}{b-a}\frac{H_{b-a}}a.$$
1
vote
1answer
138 views
$q$-plane partitions & specialization & interlinks
MacMahon's enumeration of all plane partions (PP) inside an $n$-cube generalizes to
$${\tt PP_n}(q)=\prod_{i,j,k=1}^n\frac{1-q^{i+j+k-1}}{1-q^{i+j+k-2}}.$$
A $q$-analogue of symmetric plane partitions ...
2
votes
2answers
233 views
Equal-valued determinants in search of a proof: Part III
Encouraged by David's proof for my earlier MO question, let's consider a similar problem.
I can prove the below equality by computing each of the two sides, directly. That means, there is an ...
11
votes
1answer
483 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.
...
10
votes
2answers
934 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_{\...
9
votes
1answer
621 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 ...
6
votes
2answers
432 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
401 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}...
8
votes
2answers
241 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
1k 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
562 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
190 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{...
9
votes
0answers
165 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
337 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
2k 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
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-...
