# Questions tagged [binomial-coefficients]

The binomial-coefficients tag has no usage guidance, but it has a tag wiki.

355
questions

-1
votes

1
answer

268
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*}%...

0
votes

0
answers

47
views

### Evaluations of two new series involving Lucas $v$-sequences

Let $A$ and $B$ be integers. The Lucas $v$-sequence $v_n(A,B)\ (n=0,1,2,\ldots)$ is defined by $v_0(A,B)=2,\ v_1(A,B)=A$, and $$v_{n+1}(A,B)=Av_n(A,B)-Bv_{n-1}(A,B)\ \ \ (n=1,2,3,\ldots).$$
From the ...

2
votes

0
answers

119
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 \...

2
votes

0
answers

90
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

1
answer

260
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\...

5
votes

4
answers

660
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(...

0
votes

1
answer

138
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

1
answer

156
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, ...

3
votes

2
answers

176
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 ...

0
votes

1
answer

124
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?

5
votes

2
answers

239
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? (...

3
votes

0
answers

103
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 ...

0
votes

1
answer

156
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\...

0
votes

1
answer

154
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?...

3
votes

3
answers

658
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)...

3
votes

0
answers

216
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 ...

53
votes

4
answers

3k
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 ...

4
votes

1
answer

201
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-...

0
votes

2
answers

166
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} ...

4
votes

1
answer

163
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 ...

2
votes

0
answers

202
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 ...

2
votes

1
answer

96
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$.
...

0
votes

1
answer

136
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{...

1
vote

0
answers

52
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, ...

0
votes

0
answers

95
views

### Subsequence which is identical to A122778

Let $\operatorname{wt}(n)$ is A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).
Let $a(n)$ be A284005,
\begin{align}
a(0)& = 1\\
a(n)& = (1+\operatorname{wt}(n)...

1
vote

0
answers

138
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 ...

2
votes

2
answers

143
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 ...

3
votes

0
answers

135
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)-\...

0
votes

2
answers

234
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}\...

3
votes

1
answer

144
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....

3
votes

3
answers

327
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 ...

0
votes

0
answers

105
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-...

1
vote

1
answer

190
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)\...

5
votes

3
answers

432
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 ...

2
votes

0
answers

86
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}?$

4
votes

2
answers

387
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$ ...

-3
votes

1
answer

187
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}$

1
vote

1
answer

206
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 (...

0
votes

1
answer

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

10
votes

2
answers

396
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):
\...

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 ...

3
votes

0
answers

117
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 ...

2
votes

1
answer

391
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 ...

2
votes

1
answer

212
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. $ ...

10
votes

1
answer

549
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 ...

1
vote

2
answers

189
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 ...

7
votes

1
answer

292
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 ...

3
votes

1
answer

412
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 ...

1
vote

2
answers

230
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}
=...

2
votes

1
answer

219
views

### Evaluations of three series involving binomial coefficients

Question. How to prove the following three identities?
\begin{align}\sum_{k=1}^\infty\frac1{k(-2)^k\binom{2k}k}\left(\frac1{k+1}+\ldots+\frac1{2k}\right)=\frac{\log^22}3-\frac{\pi^2}{36},\tag{1}
\end{...