All Questions
Tagged with enumerative-combinatorics binomial-coefficients
14 questions
3
votes
1
answer
392
views
A combinatorial identity involving binomial coefficients
When I was reading an article by CHUN-GANG JI (A SIMPLE PROOF OF A CURIOUS CONGRUENCE BY ZHAO), he mentioned in the acknowledgement
the following identity
$$\sum_{i+j+k=p,\text{ } i,j,k\gt 0}{p\choose ...
- 53
0
votes
2
answers
309
views
Integer solutions of system of inequalities
I am trying to solve a problem in combinatorics and I came up with the following system of inequalities:
$0\leq x<y<z\leq n$ and $x+y<n$ and I am trying to count the number of integer ...
3
votes
0
answers
274
views
Inequalities for Motzkin polynomials
Let us denote by $M_{n}(t)$ the $n$-th Motzkin polynomial. It is defined by $M_1(t) = M_2(t) = 1$ and
$$ M_{n}(t) = \sum_{i=0}^{\lfloor n/2\rfloor } \frac{1}{n-1-i} \binom{n-1-i}{i} \binom{n-1}{i+1} t^...
- 1,889
4
votes
1
answer
376
views
Counting permutations with a fixed number of descents and an extra condition
I am computing the volumes of certain polytopes and it turns out that knowing a "closed formula" for the following number would help a lot.
Determine the number of permutations $\sigma\in \...
- 1,889
2
votes
3
answers
742
views
Asking for a proof for a sum of products of binomials: an "interesting" identity?
The following identity must have received alternative proofs, including a combinatorial argument by David Callan as found at Bijections for the Identity $4^n = \sum_{k = 0}^n \binom{2k}k\binom{2(n - k)...
- 43.1k
3
votes
3
answers
396
views
Chebyshev polynomials and ballot numbers
I have asked this question a short time ago on mathstackexchange, but it has already fallen into the abyss of answered and uncommented questions. So I take the risk to ask it on mathoverflow.
Playing ...
- 7,300
5
votes
3
answers
758
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 ...
- 1,091
11
votes
3
answers
557
views
In search of a $q$-analogue of a Catalan identity
Let $C_n=\frac1{n+1}\binom{2n}n$ be the all-familiar Catalan numbers. Then, the following identity has received enough attention in the literature (for example, Lagrange Inversion: When and How):
\...
- 43.1k
1
vote
1
answer
238
views
Binomial coefficient in a binomial coefficient
I am doing some research in combinatorics, and I found that I have to consider the following binomial coefficient :
$$ \binom{\binom{i}{j}}{k} $$
(In fact, I have to take the product for fixed $i,k$ ...
- 891
12
votes
1
answer
730
views
Two remarkable weighted sums over binary words
This question builds off of the previous MO question Number of collinear ways to fill a grid.
Let $A(m,n)$ denote the set of binary words $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_{m+n-2})$ consisting ...
- 24.2k
3
votes
2
answers
403
views
Closed form for product of Stirling numbers of the second kind
What does the following expression evaluate to:
\begin{equation}
\sum\limits_{k=1}^n \dbinom{n}{k} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix}
\end{...
- 37
12
votes
3
answers
1k
views
A "quantum" identity: in search of a proof -Part II
As usual, denote $[n]_q=1+q+\cdots+q^{n-1}=\frac{\,\,1-q^n}{1-q}$ and $[n]_q!=[1]_q[2]_q\cdots[n]_q$. Furthermore, we write
$$\binom{n}k_q=\frac{[n]_q!}{[k]_q!\cdot[n-k]_q!}.$$
As a follow up on this ...
- 43.1k
12
votes
2
answers
1k
views
An interesting identity: in search of a proof -Part I
I like the following binomial identity in that the RHS extracts the indeterminate $w$ from the LHS.
Question. Can you show that
$$\sum_{k=0}^n\binom{x+kw}k\binom{y-kw}{n-k}=\sum_{k=0}^n\binom{x+y-...
- 43.1k
3
votes
1
answer
253
views
What is the value of this sum involving q-binomials?
Let $n\ge 2r$ be positive integers.
Is there a closed form for following finite summation involving in q-binomial coefficients
$$\sum_{s=0}^r(-1)^sq^{\frac{s(s+1)}{2}}{n-2r+s\brack n-2r}_q{n\brack r-...
- 1,093