Questions tagged [combinatorial-identities]
The combinatorial-identities tag has no usage guidance.
106
questions
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 ...
