Questions tagged [combinatorial-identities]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
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
4answers
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
1answer
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
2answers
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
0answers
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
1answer
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
2answers
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
5answers
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
1answer
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
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
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
1answer
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
1answer
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
0answers
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
0answers
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
3answers
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
3answers
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
2answers
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
2answers
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
1answer
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
2answers
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
1answer
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
2answers
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
1answer
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
2answers
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
1answer
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
2answers
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
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
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
0answers
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
0answers
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
1answer
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
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
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
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
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
2answers
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
1answer
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
1answer
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
3answers
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
1answer
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
2answers
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
2answers
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
0answers
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 ...