Questions tagged [binomial-coefficients]

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

Filter by
Sorted by
Tagged with
2 votes
2 answers
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 ...
Sam Hopkins's user avatar
  • 21.3k
6 votes
1 answer
308 views

A summation involving fraction of binomial coefficients

I need to prove the following statement. Let $ n, g, m, a ,t$ be integers. Prove that the following statement is true for all $ n \geq g(1+2m)+1 $, $ g\geq 2t $, $ m\geq t $, $ 0\leq a <t $, and $ ...
Arda Aydin's user avatar
8 votes
3 answers
718 views

Alternating Sum Involving Catalan Numbers

I was wondering if anyone knew how to obtain a simpler closed form of the following sum(or had any other insights regarding it): $$\sum_{k=0}^n (-1)^k{n \choose k} C_{2n-2-k} $$ Here $C_n = \frac{1}{n+...
interstice's user avatar
0 votes
0 answers
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 ...
Robert Wegner's user avatar
0 votes
0 answers
76 views

On level-$12$ of the McKay-Thompson series of the Monster and the Domb numbers

(This continues from level 10.) Given some moonshine functions $j_{N}$. There are nice descending and consistent relations for levels $6m$ with $m= 2,3,5,$ $$j_{12A} = \left(\sqrt{j_{12H}} + \frac{\...
Tito Piezas III's user avatar
1 vote
0 answers
86 views

On level $6$ of the McKay–Thompson series of the Monster and Apéry numbers, et al

After the McKay–Thompson series of levels $1$, $2$, $3$, $4$ of the Monster were mentioned in this MO post, level $6$ has very interesting relations as well. (Level 10 is in this post.) I. Level-6 ...
Tito Piezas III's user avatar
0 votes
2 answers
149 views

How fast does this summation grow?

$n,i\in\mathbb N$. The summation in question is $$\sum_{k=1}^n\prod_{l=1}^k\binom{2^n}{2^l}^i.$$ How fast does this grow? I am specifically looking at $i=1,2$.
Turbo's user avatar
  • 13.5k
0 votes
0 answers
180 views

Looking for a combinatorial proof of an identity

I've come up with an interesting combinatorial identity (thanks to P. Belmans who precomputed the numbers and pointed out to me that they correspond to OEIS A002697): $$ \sum_{i=0}^{n-1}\binom{n+1-i}{...
Anton Fonarev's user avatar
1 vote
0 answers
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 ...
Max Alekseyev's user avatar
11 votes
1 answer
1k views

New method to compute square roots [closed]

In 2011 when I was in school I created a formula to calculate square roots... For $x\in\mathbb{R}$ with $x>0$ the following holds: $$\sqrt{x} = \sum_{n=0}^{\infty}\frac{\left(\prod_{k=1}^{n}\left(\...
polygamma's user avatar
3 votes
1 answer
371 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 ...
wkmath's user avatar
  • 33
0 votes
0 answers
207 views

An alternating sum involving a product of binomial coefficients

I encountered the sum below, where $c_{1}$, $c_{2}$, $c_{3}$, $c_{4}$ and $d$ are some given positive constants. Does anyone have an idea how to simplify it? $$ \sum\limits_{k=1}^{d} \frac{(-1)^{k-1}k}...
sdd's user avatar
  • 109
3 votes
0 answers
123 views

Irreducibility of polynomials associated to binomial coefficients

Let $n \geq 2$. Let $M_n$ be the $(n+1) \times (n+1)$ matrix with entries $\binom{l}{k}$ for $0 \leq l,k \leq n$ and $U_n=M_n + M_n^T$ and let $f_n(x)$ denote the characteristic polynomial of $U_n$. ...
Mare's user avatar
  • 25k
2 votes
0 answers
65 views

Integer coefficients such that $T(n,k)=R(n,k)-R(n,k-1)$

Let $a(n)$ be A000085, i.e., the number of self-inverse permutations on $n$ letters, also known as involutions; number of standard Young tableaux with $n$ cells. Here $$a(n) = a(n-1) + (n-1)a(n-2), a(...
Notamathematician's user avatar
0 votes
2 answers
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 ...
rk95's user avatar
  • 1
7 votes
1 answer
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 ...
Sela Fried's user avatar
1 vote
0 answers
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\...
IVG's user avatar
  • 11
3 votes
1 answer
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 ...
Aaron Li's user avatar
13 votes
1 answer
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$...
Roland Bacher's user avatar
4 votes
0 answers
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)$...
Fabius Wiesner's user avatar
4 votes
2 answers
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 ...
Vladimir Dotsenko's user avatar
9 votes
1 answer
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}^\...
Zhi-Wei Sun's user avatar
  • 13.9k
3 votes
2 answers
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 ...
Vlad Matei's user avatar
4 votes
0 answers
267 views

What is the exact value of the series $\sum_{k=0}^\infty \binom{2k}k^4/256^k$?

By Stirling's formula $n!\sim\sqrt{2\pi n}(n/e)^n$, we have $$\binom{2k}k\sim\frac{4^k}{\sqrt{k\pi}}$$ and hence $$\frac{\binom{2k}k^4}{256^k}\sim\frac1{k^2\pi^2}.\tag{1}$$ So the series $$\sum_{k=0}^\...
Zhi-Wei Sun's user avatar
  • 13.9k
1 vote
0 answers
66 views

Closed-form expression for combinatorial summation with a quadratic exponent?

In a current project, I have encountered sums of the form $$A_N(\theta_1,\theta_2) = \sum_{x=0}^{N}{N \choose x} \theta_1^x \theta_2^{x^2}$$ for $\theta_1$ and $\theta_2$ positive reals. My current ...
MeanLearner's user avatar
1 vote
1 answer
306 views

How to calculate this limit (if exist)?

I have just asked the calculation of the following summation see here $$S(a,b,m,n_1,n_2)=\sum_{k=0}^m a^k b^{m-k} {n_1\choose k} {n_2\choose m-k}, $$ which is motivated by the calculation of the ...
Dian's user avatar
  • 57
4 votes
1 answer
373 views

How to calculate this summation $\sum_{k=0}^m a^k b^{m-k} {n_1\choose k} {n_2\choose m-k} $?

Question: How to calculate this summation $S=\sum_{k=0}^m a^k b^{m-k} {n_1\choose k} {n_2\choose m-k} $? Where $m<n_1,m<n_2$ Remark1: When $a=b$, I know the above summation $S=a^m\sum_{k=0}^m {...
Dian's user avatar
  • 57
1 vote
0 answers
86 views

polynomial approximation of hypergeometric function 2F1

I have the following function $T(k_1,k_2)$ resulting from multiphoton transition matrix elements calculations: $T(k_1,k_2)=\gamma^{-k_2}\sum_{j=0}^{k_1}(j+2)_{l+1}\binom{k_1}{j}(k_1+1)_3(\gamma-1)^{j}{...
Omer Amit's user avatar
7 votes
1 answer
158 views

A formula for the generating function of Hoggatt binomials or of some Young tableaux

Let ${\left\langle\matrix {n \cr k}\right\rangle}_r$ denote the $r-$Hoggatt binomials defined by $${{\left\langle\matrix {n \cr k}\right\rangle}_r=\frac{\langle n \rangle_r!}{\langle k \rangle_r! \...
Johann Cigler's user avatar
5 votes
3 answers
362 views

How to calculate the sum of general type $\sum_{k=0}^n {n\choose k} {n\choose k+a} {2 k- n + a \choose r }$?

QUESTION. How to calculate the sum of such general type? $$\sum_{k=0}^n {n\choose k} {n\choose k+a} {2 k - n + a \choose r }. $$ Some particular examples $$\sum_{k=0}^n {n\choose k} {n\choose k+a} = ...
Sergii Voloshyn's user avatar
29 votes
1 answer
2k views

Reason for breakdown of a nice binomial identity

One has the nice identities $${xy\choose 1}={x\choose 1}{y\choose 1},$$ $${xy+1\choose 2}={x+1\choose 2}{y+1\choose 2}+{x\choose 2}{y\choose 2}$$ and $${xy+2\choose 3}={x+2\choose 3}{y+2\choose 3}+4{x+...
Roland Bacher's user avatar
0 votes
1 answer
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?
liu_c_6's user avatar
  • 11
2 votes
1 answer
144 views

Counting spanning trees of $K_{b+1,w+1}$ with certain properties or calculating a combinatorial sum

For $b,w \geq 0$ let $K_{b+1,w+1}$ be the complete bipartite graph with vertices $a_1,...,a_{b+1}$ on the left hand side and $c_1,...,c_{w+1}$ on the right hand side. For given $1 \leq d \leq w$ and $...
Tardis's user avatar
  • 767
2 votes
0 answers
195 views

Question on globally convergent formulas for the Riemann zeta function $\zeta(s)$

Consider the following two formulas for $\zeta(s)$ $$\zeta(s)=\underset{K\to\infty}{\text{lim}}\left(\frac{1}{1-2^{1-s}}\sum\limits_{n=0}^K \frac{1}{2^{n+1}}\sum\limits_{k=0}^n \binom{n}{k} \frac{(-1)^...
Steven Clark's user avatar
20 votes
3 answers
3k views

Analogue of Fermat's "little" theorem

Let $p$ be a prime, and consider $$S_p(a)=\sum_{\substack{1\le j\le a-1\\(p-1)\mid j}}\binom{a}{j}\;.$$ I have a rather complicated (15 lines) proof that $S_p(a)\equiv0\pmod{p}$. This must be ...
Henri Cohen's user avatar
  • 10.6k
0 votes
1 answer
148 views

upper bound on sum of product of binomial coefficients

For positive integers $\ell < m < n$, consider a partition of $[2n]$ into two $n$-element sets $(X,Y)$. How many ways are there to choose an $m$-subset $A \subset [2n]$ such that the size of the ...
wandering_lambda's user avatar
3 votes
0 answers
259 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^...
Luis Ferroni's user avatar
  • 1,970
-1 votes
1 answer
321 views

Could you please confirm or deny two identities involving weighted Stirling numbers of the second kind?

In the paper [1] below, among other things, Carlitz introduced weighted Stirling numbers of the second kind $R(n,k,r)$. He also proved that the numbers $R(n,k,r)$ can be generated by \begin{equation*}%...
qifeng618's user avatar
  • 716
2 votes
0 answers
177 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 \...
Luis Ferroni's user avatar
  • 1,970
2 votes
0 answers
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 ...
Hhhhhhhhhhh's user avatar
  • 1,032
1 vote
1 answer
338 views

Lower bound and limit of a sum with binomial coefficients

Let $$A_k = \sum_{i=1}^k i {3k-2i-1 \choose i-1} {2i-2 \choose k-i}$$ $$B_k = \sum_{i=1}^k i {3k-2i-2 \choose i-1} {2i-1 \choose k-i}$$ $$C_k = \sum_{i=1}^k (3k-2i-2) {3k-2i-3 \choose i-1} {2i\...
macat's user avatar
  • 115
5 votes
4 answers
772 views

Limit of a sum with binomial coefficients

Let $$A_k = \frac{\sum_{i=1}^ki{2k-i-1 \choose i-1}{i-1 \choose k-i}}{k{2k-1\choose k}}$$ $$B_k = \frac{\sum_{i=1}^ki{2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$ $$C_k = \frac{\sum_{i=1}^k(...
macat's user avatar
  • 115
0 votes
1 answer
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 ...
eyejay's user avatar
  • 1
1 vote
1 answer
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, ...
eti902's user avatar
  • 795
3 votes
2 answers
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 ...
macat's user avatar
  • 115
0 votes
1 answer
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?
Matt Majic's user avatar
5 votes
2 answers
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? (...
James Propp's user avatar
3 votes
0 answers
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 ...
Wolfgang's user avatar
  • 13k
0 votes
1 answer
184 views

A binomial product sum that turns out to be 1

The binomial product sum \begin{align*} \sum\limits_{\substack{i_1> i_2> \cdots > i_k\\i_1, i_2, \cdots, i_k \in \{1, 2, \cdots, n-1\}}}\binom{n}{i_1}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots\...
Vishnu Namboothiri K's user avatar
0 votes
1 answer
246 views

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?...
one user's user avatar
  • 113

1
2 3 4 5
8