Questions tagged [combinatorial-identities]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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-...