Questions tagged [binomial-coefficients]

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

Filter by
Sorted by
Tagged with
-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*}%...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
  • 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 ...
user avatar
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\...
user avatar
  • 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(...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
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? (...
user avatar
  • 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 ...
user avatar
  • 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\...
user avatar
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?...
user avatar
  • 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)...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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-...
user avatar
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} ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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$. ...
user avatar
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{...
user avatar
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, ...
user avatar
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)...
user avatar
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 ...
user avatar
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 ...
user avatar
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)-\...
user avatar
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}\...
user avatar
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....
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
  • 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)\...
user avatar
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 ...
user avatar
  • 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}?$
user avatar
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$ ...
user avatar
-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}$
user avatar
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 (...
user avatar
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 ...
user avatar
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): \...
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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. $ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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} =...
user avatar
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{...
user avatar
  • 12.8k

1
2 3 4 5
8