# Questions tagged [binomial-coefficients]

For questions that explicitly reference the binomial coefficients, Pascal's Triangle, and Binomial identities.

390 questions
Filter by
Sorted by
Tagged with
146 views

### Sign-reversing involution for $q$-binomial coefficient at $q=-1$

Consider the q-binomial coefficient $\binom{n}{k}_q$. One combinatorial way to define it is as follows. Let $W_{n,k}$ be the set of binary words of length $n$ with $(n-k)$ 0's and $k$ 1's. An ...
308 views

72 views

### Solving a Catalan-like recursion of polynomials, related to the KdV energies

I am working on a PDE problem. The goal is to connect the higher order energies of the Gross-Pitaevskii equation to those of the Korteweg-de-Vries equation. As these higher order energies are ...
76 views

1 vote
123 views

### 3D generalization of Gaussian q-binomial coefficient

It is known that the coefficient of $q^t$ in Gaussian binomial coefficient $\binom{m+n}m_q$ equals the number of permutations of the multiset $\{0^m, 1^n\}$ with $t$ inversions. Is there a closed ...
1k views

207 views

152 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 ...
233 views

### A reference for a sum found in Gould's Combinatorial Identities book

On p. 49 in Gould's book Combinatorial Identities, the author states that the sum $$\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}\binom{2n}{2k}^{-1}$$ "... arises naturally in a statistical problem; it ...
1 vote
75 views

### Maybe with the multinomial theorem

I'm looking for some idea to prove \begin{equation*} \sum_{\substack{ \left( s_{0},\ldots ,s_{r-1}\right) \in \left\{ \mathbb{N}% \cup \left\{ 0\right\} \right\} ^{r}, \\ \sum_{a=0}^{r-1}\left( a+1\...
106 views

### Why is this alternating sum involving Catalan numbers $\sum_{i=0}^{\lfloor t/2 \rfloor} (-1)^{i+1} \binom{t-i}{i} C_{t-i-1} = 0$ for all $t$?

I need the result that for all $t$, $$\sum_{i=0}^{\lfloor t/2 \rfloor} (-1)^{i+1} \binom{t-i}{i} C_{t-i-1} = 0,$$ where $C_{t-i-1}$ is the $(t-i-1)$-th Catalan number. I've checked for $t$ up to ...
540 views

### A congruence for a product of binomial coefficients?

For every prime $p\geq 5$ one seems to have the congruence $$(-1)^{(p-1)/2}\prod_{k=0}^{p-1}{p-1\choose k}\equiv 1-p+\frac{3}{2}p^2-\frac{7}{6}p^3\pmod{p^4}\ .$$ (I have checked all primes up to $5000$...
91 views

### Greatest common divisors of some binomial coefficients

This is cross-posted from math.stackexchange. While making some computation, I stumbled upon a curious relation among some binomial coefficients. Consider the sequence of binomial coefficients $a(k,n)$...
195 views

### (Conceptual) proof and/or interpretation of a $q$-binomial identity

There is a $q$-binomial identity that I encountered in one paper I am reading (https://arxiv.org/abs/1910.06193) which probably admits a very simple proof that I do not see: for two nonnegative ...
312 views

### Series for $\frac{\log m}{\pi}$ with summands involving harmonic numbers

The classical rational Ramanujan-type series for $1/\pi$ have the following four forms: \begin{align}\sum_{k=0}^\infty(ak+b)\frac{\binom{2k}k^3}{m^k}&=\frac{c}{\pi},\label{1}\tag{1} \\\sum_{k=0}^\...
372 views

### Binomial coefficient congruence modulo $p^n$

I am interested in the following congruence $$\binom{ap^n}{bp^n}\equiv \binom{a}{b}\pmod{p^n}$$ I am aware that by some reference in a book the above it should actually hold modulo $p^{3n}$; the ...
267 views

362 views

111 views

### Number of ways to write a finite set of cardinality n as the union of r distinct binary subsets [closed]

I want to know the number of ways to write a finite set of cardinality $n$ as the union of $r$ distinct two-element subsets. Is there a nice formula in binomial coefficients?
144 views

105 views

### Divisibility based on central binomial coefficients

For some prime $p$, it is a standard approach based on Kummer's criterion to bound the number of positive integers $n<X$ for some parameter $X$, such that $p\nmid \binom{2n}{n}$. However, if we ...
1 vote
338 views

151 views

### Restrictions on exponents in multinomial formula

From the multinomial formula we have $$(x_1 + x_2 + \dotsb + x_m)^n = \sum_{k_1+k_2+\dotsb+k_m=n, \ k_1, k_2, \dotsc, k_m \geq 0} {n \choose k_1, k_2, \dotsc, k_m} \prod_{t=1}^m x_t^{k_t}\,.$$ I ...
1 vote
227 views

### Inequalities between sums of products of certain binomial coefficients

I am a PhD student. During my researches, I often have to deal with inequalities involving sums of binomial coefficients, where the sums are indexed by some set of integer compositions. For example, ...
227 views

### An inequality involving binomial coefficients and the powers of two

I came across the following inequality, which should hold for any integer $k\geq 1$: $$\sum_{j=0}^{k-1}\frac{(-1)^{j}2^{k-1-j}\binom{k}{j}(k-j)}{2k+1-j}\leq \frac{1}{3}.$$ I have been struggling with ...
185 views

### Proof for alternating binomial sum over even powers

I have numerical evidence that $$\sum_{k=1}^n (-1)^k\frac{k^{p}}{n+k}\binom{2n-1}{n-k}=0$$ For $p=2,4,6...2n-2$. How could this be proved?
290 views

### Extended binomial coefficients and the gamma function

For which $(a,b,n) \in \mathbb{Z}^3$ satisfying $a+b=n$ does $\frac{\Gamma(z+1)}{\Gamma(x+1)\Gamma(y+1)}$ approach a limit as $(x,y,z) \rightarrow (a,b,n)$ in $\mathbb{C}^3$, and what is that limit? (...
137 views

### Flat polynomials with factors of big height

Let $p(x)$ be a polynomial of degree $n$ with all coefficients in $\{-1,0,1\}$ (such polynomials are sometimes called flat). I am wondering how big the coefficients of a factor of $p$ can be. Call ...
### Sum of the first m terms of the expansion $(x+y)^n$
Let $S(x, y, m, n) = \sum\limits_{i=0}^m \binom{n}{i}x^i y^{n-i}$, where $0 < m < n$. I want to derive the relation between $S(x, y, m, n)$ and $S(x, y, m, n-1)$. Is there any formulas I can use?...