Questions tagged [binomial-coefficients]

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

Filter by
Sorted by
Tagged with
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
  • 11.5k
0 votes
1 answer
169 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
267 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,879
-1 votes
1 answer
336 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
  • 836
3 votes
0 answers
211 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,879
2 votes
0 answers
108 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
2 votes
1 answer
375 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
  • 145
5 votes
4 answers
816 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
  • 145
0 votes
1 answer
159 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
267 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
  • 835
4 votes
2 answers
260 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
  • 145
0 votes
1 answer
234 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
349 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
  • 19.4k
3 votes
0 answers
142 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
  • 13.2k
1 vote
1 answer
197 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
298 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
2 votes
3 answers
731 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)...
T. Amdeberhan's user avatar
3 votes
0 answers
236 views

Function maximized by $\left\{\left\lfloor\frac np\right\rfloor,\dots,\left\lfloor\frac{n+p-j}p\right\rfloor\right\}$

Since this MSE question didn't find any suitable answers, I decided to post it here. I was trying to maximize the function $$f(r)=\binom nr\cdot 2^{n-r}$$ This can be done by the standard technique of ...
Sayan Dutta's user avatar
54 votes
4 answers
4k views

When do binomial coefficients sum to a power of 2?

Define the function $$S(N, n) = \sum_{k=0}^n \binom{N}{k}.$$ For what values of $N$ and $n$ does this function equal a power of 2? There are three classes of solutions: $n = 0$ or $n = N$, $N$ is odd ...
John D. Cook's user avatar
  • 5,147
4 votes
1 answer
222 views

Does anyone have ideas about how to simplify this combinatorial expression (mod 2)?

Fix $k > 0$ for $\lceil \frac{2k+1}{3} \rceil \le j \le k$, $$ \sum_{i = 0}^{2j-k-1} \binom{j}{i} + \sum_{b = \lceil \frac{k+1}{2} \rceil}^{\lfloor \frac{2k-j}{2} \rfloor} \left( \sum_{l = 0}^{2b-k-...
user473047's user avatar
0 votes
2 answers
219 views

Closed form expression for power of binomial expression with radical

When performing binomial expansion of $(a+b\sqrt c)^n$ I get $x+y\sqrt c$ where $x$ is $\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k} a^{n-2k} b^{2k} c^k$ $y$ is $\sum_{k=0}^{\lfloor (n-1)/2\rfloor} ...
Eugene's user avatar
  • 39
4 votes
1 answer
278 views

Approximating binomial coefficient sum

I have the following exact sum for the expectation of an event $$\sum_{m=0}^{nk} \sum_{j=1}^n (-1)^{j-1}\binom{n}{j} \binom{(n-j)k}{m} / \binom{nk}{m}$$ which is exactly correct but I want to give an ...
Doc Stories's user avatar
2 votes
0 answers
213 views

Two conjectures about generalised A329369

Let $m \geqslant 2$ be a fixed integer. Let $$\operatorname{wt}(n,m)=\operatorname{wt}\left(\left\lfloor\frac{n}{m}\right\rfloor,m\right)+n\bmod m, \operatorname{wt}(0,m)=0$$ Then we have an integer ...
Notamathematician's user avatar
2 votes
1 answer
110 views

Modulo $2$ binomial transform of A243499 applied $k$ times

Let $m \geqslant 1$ be a fixed integer. Let $f(n)$ be A007814, exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. ...
Notamathematician's user avatar
0 votes
1 answer
149 views

Modulo $2$ binomial transform of A124758

Let $f(n)$ be A153733, remove all trailing ones in binary representation of $n$. Here \begin{align} f(2n)& = 2n\\ f(2n+1)& = f(n)\\ \end{align} Then we have an integer sequence given by \begin{...
Notamathematician's user avatar
1 vote
0 answers
56 views

Inverse modulo $2$ binomial transform of generalised A284005

Let $m \geqslant 1$ be a fixed integer. Let $\operatorname{wt}(n)$ be A000120, $1$'s-counting sequence: number of $1$'s in binary expansion of $n$ (or the binary weight of $n$). Let $f(n)$ be A007814, ...
Notamathematician's user avatar
1 vote
0 answers
154 views

Open tours by a biased rook (proof verification)

Related questions: Number of open tours by a biased rook on a specific $f(n)\times 1$ board which end on a $k$-th cell from the right Sum with products turned into subsequences Combinatorial ...
Notamathematician's user avatar
2 votes
2 answers
171 views

Modulo $2$ binomial transform of $m^n$

Let $m \in \mathbb{R}$. Let $f(n)$ be A007814, exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. Let $g(n)$ be ...
Notamathematician's user avatar
3 votes
0 answers
145 views

Combinatorial interpretation of inverse modulo $2$ binomial transform of A284005

My question is related to the following: Sum with products turned into subsequences We have an identity $$a(n, -1) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(-1)^{\operatorname{wt}(n)-\...
Notamathematician's user avatar
0 votes
2 answers
309 views

Closed form for a binomial product sum

Is there any closed formula for the binomial product sum \begin{align*} \sum\limits_{\substack{i_1> i_2> \cdots > i_k\\i_1, i_2, \cdots, i_k \in \{n-j+1, n-j+2, \cdots, n-1\}}}\binom{n}{i_1}\...
Vishnu Namboothiri K's user avatar
3 votes
1 answer
314 views

Prove the identity $2(n-1)n^{n-2} = \sum^{n-1}_{i=1}\binom nii^{i-1}(n-i)^{n-i-1}$ [closed]

The given identity: $$2(n-1)n^{n-2} = \sum^{n-1}_{i=1}\binom nii^{i-1}(n-i)^{n-i-1}$$ It seems to be a binomial coefficient problem, but I have tried many ways. There are no more ideas how to prove it....
zerouser's user avatar
3 votes
3 answers
366 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 ...
Libli's user avatar
  • 7,210
0 votes
0 answers
137 views

A p adic limit of a binomial coefficient

Let $0 \leq a \leq p^n$ be a number coprime to p. Consider the following sequence of binomial coefficients: $$B_k = \binom{p^{n+k}}{p^ka} $$ as $k\to \infty$. If I did the computation right, the p-...
Asvin's user avatar
  • 7,648
1 vote
1 answer
215 views

Worpitzky-like identities?

Let $$r_k(x)=\prod_{j=1}^k {(\frac{x+j}{j}})^{\min(j,k-j)}.$$ Computations suggest that $$r_{2k}(x)=\sum_{j=0}^{(k-1)^2}a(2k,j)\binom{k^2+x-j}{k^2}$$ and $$r_{2k+1}(x)=\sum_{j=0}^{k^2-k}a(2k+1,j)\...
Johann Cigler's user avatar
5 votes
3 answers
668 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 ...
qifeng618's user avatar
  • 836
2 votes
0 answers
99 views

Terminology: Central binomial coefficients?

Is there a special terminology for the binomial coefficients $\binom{n}{\lfloor\frac{n}{2}\rfloor}$ which distinguishes them from the central binomial coefficients $\binom{2n}{n}?$
Johann Cigler's user avatar
4 votes
2 answers
444 views

Asymptotics of an alternating sum involving the prefix sum of binomial coefficients

Let $c>1$. Question. What is the asymptotic behaviour of the sum \begin{align} S_n = \sum_{k=0}^{n} \left(-\frac{1}{2} \right)^k \binom{n}{k} \sum_{j=0}^{k} \binom{cn+k}{j} \end{align} as $n$ ...
Daniel Paleka's user avatar
-3 votes
1 answer
823 views

combinatoric proof $\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n-i+k-1}{k}=\binom{k-1}{k-n}$ [closed]

I would like help with combinatorial proof , not algebraic proof . Thank you for your time $\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n-i+k-1}{k}=\binom{k-1}{k-n}$
maya cohen's user avatar
1 vote
1 answer
268 views

There seem to be only few primes of the form ${n\choose k}+1$ if $k\geq 3$ is odd

We consider the sequence $n\longmapsto {n\choose k}+1$ for $k\geq 1$ a fixed integer. For $k\geq 3$ odd, this sequence seems to contain surprisingly few prime numbers while there are many primes (...
Roland Bacher's user avatar
0 votes
1 answer
362 views

Prove for all $k \in \mathbb{N}$, that $\sum_{j=0}^{2k+1} {n+j-1\choose j} + \sum_{j=0}^{2k+1}(-1)^j{n+2k+2\choose j} = 0$

Prove that this sum holds for all positive integers $k$. I'm quite sure this is right but I can't see immediately how to go about proving it. This will help resolve a problem regarding sums of ...
Benjamin L. Warren's user avatar
10 votes
2 answers
477 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): \...
T. Amdeberhan's user avatar
3 votes
4 answers
1k views

Proving a binomial sum identity

QUESTION. Let $x>0$ be a real number or an indeterminate. Is this true? $$\sum_{n=0}^{\infty}\frac{\binom{2n+1}{n+1}}{2^{2n+1}\,(n+x+1)}=\frac{2^{2x}}{x\,\binom{2x}x}-\frac1x.$$ POSTSCRIPT. I like ...
T. Amdeberhan's user avatar
3 votes
0 answers
132 views

A recursion involving binomial coefficients: looking for a q-analog

Let $a_n := \frac{1}{2n+1}\binom{3n}{n}$. Then it is known that (one can find references in the OEIS for this.) $$ a_n = \sum_{\substack{i,j,k \geq 0 \\ i+j+k=n-1} } a_i a_j a_k. $$ Is there a natural ...
Per Alexandersson's user avatar
2 votes
1 answer
673 views

Prove that $ \sum_{i=0}^{2k}( {n+R-1\choose R+i} + (-1)^{i+1}{ n+R+i\choose R+i } )\sum_{j=0}^i {i\choose j}(-1)^j(i+1-j)^{2k}=0 $

For all $k,R \in \mathbb{N}$ fixed, prove that $ \sum_{i=0}^{2k}( {n+R-1\choose R+i} + (-1)^{i+1}{ n+R+i\choose R+i } )\sum_{j=0}^i {i\choose j}(-1)^j(i+1-j)^{2k}=0 $. I'm quite sure this is true but ...
Benjamin L. Warren's user avatar
2 votes
1 answer
328 views

Show that $\sum_{i=0}^{2k} [ {n\choose i+1} + (-1)^{i+1}{n+i+1\choose i+1} ] \sum_{j=0}^i {i\choose j}(-1)^j (i+1-j)^{2k} =0.$

Let $u(k,j) = 1$ if $j=0$, $0$ if $j > k$, or else it is $j*u(k-1,j-1) +(j+1)*u(k-1,j) $. Prove that $ \sum_{i=0}^{2k} {n \choose i+1} u(2k,i) +\sum_{i=0}^{2k} {-n-1 \choose i+1} u(2k,i)=0. $ ...
Benjamin L. Warren's user avatar
10 votes
1 answer
615 views

A conjecture on binomial coefficients and roots of unity

Is the following true? Let $p$ be a prime and let $w$ be a $(p-1)$st root of unity (not necessarily primitive). Then $$\binom{w}{n}=\frac{w(w-1)\cdots(w-n+1)}{n!}$$ is $p$-integral; i.e., it can be ...
Ira Gessel's user avatar
  • 16.2k
1 vote
2 answers
344 views

Closed form of $ \sum_{i=1}^{n-k} {n-1-i\choose k-1}i^a + \sum_{i=1}^k {n-1-i\choose n-1-k}$

For all natural numbers $a$, is there a known closed form of $ \sum_{i=1}^{n-k} {n-1-i\choose k-1}i^a + \sum_{i=1}^k {n-1-i\choose n-1-k}$, where $k$ is fixed? For example, letting $k=1$ gives the ...
Benjamin L. Warren's user avatar
7 votes
1 answer
315 views

For which pairs $k$ and $n$, $n\mid{{n-2} \choose {k}}$

The question This question that arose in a discussion with Ron Adin is quite simple: For which pairs $k$ and $n$ does $n$ divide ${{n-2} \choose {k}}$? Simple observations It is easy to see that ...
Gil Kalai's user avatar
  • 24.2k
3 votes
1 answer
484 views

Conjecture on bernoulli numbers and binomial coefficients

Crossposted from https://math.stackexchange.com/questions/4116414/conjecture-on-bernoulli-numbers-and-binomial-coefficients In playing around with some formulas, I have come up with the following ...
Fox Mulder's user avatar
1 vote
2 answers
275 views

In search of a combinatorial proof for a multinomial sum

There is this sequence listed on OEIS - named Domb numbers. I'm curious about QUESTION. Is there a direct combinatorial proof for the identity $$\sum_{k=0}^n\binom{n}k^2\binom{2k}k\binom{2n-2k}{n-k} =...
T. Amdeberhan's user avatar

1
2
3 4 5
9