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*}%...
- 390
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 ...
- 12.8k
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 \...
- 1,716
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 ...
- 868
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\...
- 115
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(...
- 115
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
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, ...
- 643
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 ...
- 115
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?
- 563
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? (...
- 17.2k
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 ...
- 12.4k
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?...
- 103
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)...
- 37.8k
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 ...
- 345
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,681
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-...
- 43
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} ...
- 39
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 ...
- 51
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 ...
- 1,587
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$.
...
- 1,587
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,587
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, ...
- 1,587
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,587
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 ...
- 1,587
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 ...
- 1,587
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)-\...
- 1,587
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....
- 31
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 ...
- 6,159
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-...
- 6,834
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,093
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 ...
- 390
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}?$
- 5,093
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$ ...
- 282
-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}$
- 103
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 (...
- 13.6k
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 ...
- 461
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):
\...
- 37.8k
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 ...
- 37.8k
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 ...
- 14.4k
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 ...
- 461
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. $ ...
- 461
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 ...
- 13k
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 ...
- 461
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 ...
- 23.5k
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 ...
- 133
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}
=...
- 37.8k
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{...
- 12.8k