Questions tagged [combinatorial-identities]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
177 views

A conjectural identity involving infinite series

Recently I formulated the following curious conjecture based on my computation. Conjecture. For all $|x|>1$, we have the identity $$\sum_{k=0}^\infty\frac{\sum_{j=0}^{k}\binom{2k+1}{2j}(1-x)^jx^{k-...
user avatar
  • 12.8k
-1 votes
1 answer
268 views

Could you please confirm or deny two identities involving weighted Stirling numbers of the second kind?

In the paper [1] below, among other things, Carlitz introduced weighted Stirling numbers of the second kind $R(n,k,r)$. He also proved that the numbers $R(n,k,r)$ can be generated by \begin{equation*}%...
user avatar
  • 390
2 votes
2 answers
178 views

Ask for a proof of an identity involving the product of two Bernoulli numbers

It is well known that the Bernoulli numbers $B_{k}$ for $k\in\{0,1,2,\dotsc\}$ can be generated by \begin{equation*} \frac{z}{\textrm{e}^z-1}=\sum_{k=0}^\infty B_k\frac{z^k}{k!}=1-\frac{z}2+\sum_{k=1}^...
user avatar
  • 390
15 votes
2 answers
864 views

A rather curious identity on sums over triple binomial terms

While exploring the Baxter sequences from my earlier MO post, I obtained a rather curious identity (not listed on OEIS either). I usually try to employ the Wilf-Zeilberger (WZ) algorithm to justify ...
user avatar
9 votes
2 answers
361 views

Identity involving a quadratic term inside the Pochhammer symbol

This identity came up in my research: $$ \sum_{m=1}^n m^2 \frac{(\frac{xy}n + m-1)_{2m-1} (n+m-1)_{2m-1}}{(x+m)_{2m+1} (y+m)_{2m+1}} = \frac{n^2}{(x^2-n^2) (y^2 - n^2)}. $$ Here $n$ is a fixed ...
user avatar
  • 3,472
3 votes
2 answers
308 views

Ask for a reference or a proof of a combinatorial identity $\sum_{k=0}^n\binom{2n+1}{2k}\binom {k}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m}$

Could you please recommend a reference to or supply a proof of the following identity \eqref{combin-ID-Maclaurin}, or \eqref{first-equiv-form}, or \eqref{combin-ID-Mac-Equiv}, or \eqref{combin-ID-Mac-...
user avatar
  • 390
4 votes
1 answer
123 views

$0,1$-matrices with $1$ in every row/column vs. all $0,1$-matrices

Chapter 2, Exercise 25 of R. Stanley's "Enumerative Combinatorics" Vol. 1 asserts that $$ \sum_{m,n \geq 0} \left(\sum_{t \geq 0} f_i(m,n)t^i\right)\frac{x^m}{m!}\frac{y^n}{n!} = e^{-x-y}\...
user avatar
  • 18.8k
12 votes
3 answers
776 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. ...
user avatar
  • 619
5 votes
1 answer
397 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, ...
user avatar
  • 12.8k
4 votes
0 answers
139 views

Identities involving derangements and roots of unity

For a positive integer $n$, a derangement of $\{1,\ldots,n\}$ is a permutation $\tau$ of $\{1,\ldots,n\}$ with $\tau(j)\not=j$ for all $j=1,\ldots,n$. For convenience, we let $D(n)$ denote the set of ...
user avatar
  • 12.8k
9 votes
1 answer
580 views

Permanent identities

The permanent $\mathrm{per}(A)$ of a matrix $A$ of size $n\times n$ is defined to be: $$\mathrm{per}(A)=\sum_{\tau\in S_n}\prod_{j=1}^na_{j,\tau(j)}.$$ Let $$A=\left[\tan\pi\frac{j+k}n\right]_{1\le j,...
user avatar
  • 619
5 votes
3 answers
427 views

How to prove the combinatorial identity $\sum_{k=\ell}^{n}\binom{2n-k-1}{n-1}k2^k=2^\ell n\binom{2n-\ell}{n}$ for $n\ge\ell\ge0$?

With the aid of the simple identity \begin{equation*} \sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^{k}}=2^n \end{equation*} in Item (1.79) on page 35 of the monograph R. Sprugnoli, Riordan Array Proofs of ...
user avatar
  • 390
3 votes
1 answer
144 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, ...
user avatar
7 votes
1 answer
256 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 \...
user avatar
10 votes
0 answers
305 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^...
user avatar
6 votes
2 answers
204 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: $$\...
user avatar
3 votes
2 answers
63 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 &...
user avatar
5 votes
0 answers
85 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})\...
user avatar
2 votes
1 answer
219 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{...
user avatar
  • 12.8k
3 votes
2 answers
236 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 ...
user avatar
7 votes
1 answer
155 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 ...
user avatar
18 votes
0 answers
706 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)$ ...
user avatar
  • 12.8k
3 votes
1 answer
358 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{...
user avatar
  • 3,478
6 votes
5 answers
766 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_{...
user avatar
3 votes
1 answer
408 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'...
user avatar
14 votes
2 answers
413 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$...
user avatar
  • 243
2 votes
0 answers
187 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$ ...
user avatar
  • 12.8k
6 votes
1 answer
237 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} = \...
user avatar
  • 3,070
1 vote
2 answers
197 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 ...
user avatar
4 votes
1 answer
287 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 ...
user avatar
4 votes
2 answers
449 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 ...
user avatar
  • 1,716
5 votes
0 answers
263 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}(\...
user avatar
9 votes
1 answer
936 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/...
user avatar
  • 12.8k
1 vote
1 answer
109 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 ...
user avatar
9 votes
5 answers
753 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 ...
user avatar
-1 votes
1 answer
242 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 ...
user avatar
  • 23
30 votes
3 answers
3k 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}...
user avatar
  • 12.8k
7 votes
3 answers
337 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\...
user avatar
7 votes
1 answer
597 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}^...
user avatar
  • 237
4 votes
1 answer
260 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=...
user avatar
  • 417
1 vote
0 answers
491 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, ...
user avatar
  • 12.8k
3 votes
0 answers
169 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 ...
user avatar
0 votes
3 answers
284 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}.$$
user avatar
  • 307
3 votes
3 answers
450 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}.$$
user avatar
  • 307
6 votes
2 answers
963 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 ...
user avatar
2 votes
2 answers
255 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.$$
user avatar
1 vote
1 answer
142 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 ...
user avatar
2 votes
2 answers
245 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 ...
user avatar
11 votes
1 answer
508 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. ...
user avatar
10 votes
2 answers
990 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_{\...
user avatar