# Questions tagged [combinatorial-identities]

The combinatorial-identities tag has no usage guidance.

106
questions

**1**

vote

**0**answers

42 views

### How prove this combinatorial-identities

if $n\ge 1$ be postive integers,and $x,y,z$ be any real numbers,such $x+y+z=n-1$,for any real number $a$.show that
$$\dfrac{(-4)^n}{\binom{2x}{n}}\sum_{r+s=n,r,s\in Z}\dfrac{\binom{y}{r}\binom{y-a}{r}...

**5**

votes

**4**answers

471 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_{...

**2**

votes

**1**answer

361 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

**2**answers

244 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

**0**answers

169 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$ ...

**4**

votes

**1**answer

199 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

**2**answers

157 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 ...

**3**

votes

**1**answer

243 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

**2**answers

397 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

**0**answers

165 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

**1**answer

855 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

**0**answers

70 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

**5**answers

645 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

**1**answer

236 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 ...

**29**

votes

**3**answers

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

**3**answers

272 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

**1**answer

333 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

**1**answer

242 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

**0**answers

430 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

**0**answers

150 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

**3**answers

204 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

**3**answers

341 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

**2**answers

815 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

**2**answers

233 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

**1**answer

133 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

**2**answers

226 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

**1**answer

456 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

**2**answers

865 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

**1**answer

562 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

**2**answers

418 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

**1**answer

380 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}...

**7**

votes

**2**answers

197 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

**1**answer

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

**1**answer

547 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

**0**answers

177 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

**0**answers

162 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

**1**answer

320 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

**3**answers

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

**7**answers

1k 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

**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,...

**30**

votes

**3**answers

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

**2**answers

893 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-...

**21**

votes

**2**answers

1k 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 \...

**6**

votes

**1**answer

158 views

### An identity involving hook-lengths

I am reading Macdonlad's book on "symmetric functions and Hall polynomials" and I have difficulty figuring out an identity which involves hook-lengths. I would like to ask for a hint.
Let $\lambda=(\...

**3**

votes

**1**answer

146 views

### Proving a particular “Abel type” identiy

I have reduced solving this question to proving the following identity, for $n, \ell \ge 0$:
$$
(n-2\ell+1)^{n-1} \binom{n}{\ell-1} =
\\ \frac{1}{2} \sum_{n_1+n_2=n-1}\left[ (n_1+1)^{n_1-1} (n_2-2\...

**13**

votes

**3**answers

683 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**

vote

**1**answer

169 views

### One trig “survives” a binomial summation: why?

I've seen many trigonometric identities but here is one that I encountered for which I did not find a reference.
In case you wonder where this came from, I was investigating certain $q$-series in ...

**16**

votes

**2**answers

705 views

### Sum of multinomals = sum of binomials: why?

I stumbled on the following identity, which has been checked numerically.
Question. Is this true? If so, any proof?
$$\sum_{j=0}^{\lfloor\frac{k}2\rfloor}\binom{n-2k+j}{j,k-2j,n-3k+2j}
=\sum_{j=0}...

**7**

votes

**2**answers

282 views

### Identity with Pochhammer and harmonic numbers

This came out of some work on the digamma function.
Let $(x)_k=x(x+1)\cdots(x+k-1)$ denote the Pochhammer symbol. Then,
Question. Can you prove/disprove this identity?
$$\pmb{\frac{(\frac12)_j^...

**1**

vote

**0**answers

104 views

### In search of multiple expressions for a sequence

The sequence $a_n=\sum_{k=0}^n\binom{n}k^24^k$ is listed on OEIS along with a couple of combinatorial interpretations. What interested me at the moment is the plethora of binomial single-sums for the ...