Questions tagged [binomial-coefficients]

For questions involving the coefficients involved in the binomial theorem. $ \binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
42 views

On a quick proof to the following congruence relation

Let $n$ be a positive integer and $p$ be a prime number. Let $v_p(n)$ represent the exponent of the highest power of $p$ that divides $n$. I wonder if there is a simple way to prove the congruence ...
  • 39
5 votes
1 answer
57 views

Convergence of a weighted alternating binomial series

Consider the alternating series $$S_n = \sum_{k=0}^{n} (-1)^k {n\choose k} a_k$$ where the weights $a_k$ are non-negative, bounded and monotonically decreasing ($a_{k+1} < a_k$). Can it be shown ...
  • 123
6 votes
1 answer
93 views

Conjecture: Shallow diagonals in Pascal's triangle form polynomials whose roots are all real, distinct, and in $(-2,2)$.

Here are the first few "shallow diagonals" in Pascal's triangle. We can use these shallow diagonals to make polynomials. Note that the even degree polynomials have an extra $\pm x$ at the ...
  • 8,418
4 votes
1 answer
80 views

Is there a $q$-analog for the product of binomial coefficients?

The $q$-analog of the binomial coefficient $\binom{n}{k}$ may be defined as the coefficient of $x^k$ in $\prod_{i=0}^{n-1}(1+q^ix)$. Classical arithmetic identities tend to have $q$-analogs. I am ...
1 vote
1 answer
63 views

Explanation of $\sum_{k}[x^k]f(x)g(y)^k=f(g(y))$

In the book "Mathematics for the Analysis of Algorithms" by Daniel H. Greene and Donald E. Knuth, they cover the example, $$S=\sum_{k}\binom{m}{k}\left(-\frac{1}{2}\right)^k\binom{2k}{k}$$ ...
  • 151
1 vote
2 answers
73 views

How to prove that $\sum_{k=0}^n (-1)^k k^p \binom{n}{k}$ is non-zero for p>1

Let $p\in \mathbb{N}_0$ and consider $\sum_{k=0}^n (-1)^k k^p \binom{n}{k}$. For $p=0$, this clearly vanishes as the sum then equals $(1-1)^n$. For $p=1$ and $n$ even, this sum also vanishes as one ...
0 votes
1 answer
50 views

The limit of a Nasty Summation

I'm trying to evaluate the limit as h approachs 0 of the sum from k = 0 to n of: $\frac{1}{h^n}(-1)^{k+n}\binom{n}{k}\frac{1}{(x+kh)^2-2(x+kh)+17}$ If it helps, it's the limit definition of the nth ...
  • 65
5 votes
1 answer
201 views

Series of polynomials very nearly follows binomial coefficients but doesn't quite

I'm modelling a system using a Markov chain and by a few iterations of the transition matrix I can see a pattern emerging in the resulting polynomial that really looks like Pascal's triangle, but isn'...
-1 votes
1 answer
61 views

Sum of squares of combinations having value of n different from index of sum

Two sums are - $$ \sum_{r=0}^n [{2n+1 \choose 2r}] ^2 $$ $$ \sum_{r=0}^n [{2n+1 \choose 2r+1}] ^2 $$ The question basically asks to simplify these sums such that the final expression is only in terms ...
0 votes
0 answers
121 views

Collatz Conjecture 1-cycles and Pascal's triangle.

Question: Is there a pattern in Pascal's triangle that precludes the existence of non-trivial 1-cycles in the Collatz conjecture? Efforts to Answer the Question: I did a search engine query for "...
  • 343
3 votes
0 answers
114 views

Binomial Coefficient through multiplication only

Is there any method to obtain $n \choose k$, for all $n, k \in \mathbb{N}$, using only products of natural numbers without using recursion on binomial coeffcients? A method that allows one to compute ...
  • 39
7 votes
2 answers
168 views

Partial sum of alternating series involving binomials

I ran across an interesting expression that I cannot prove (but tested numerically): $$ 1 = \sum_{j=0}^{n} (-1)^j \binom{n+i}{n-j-1} \binom{n+j}{n-i-1} \binom{i+j}{i} $$ for any $0 \leq i < n$. In ...
  • 181
0 votes
1 answer
51 views

How to get this lower bound for $C(m^2,m-1)$?

While applying Nechiporuk’s Theorem to get a lower bound on the formula size of Element distinction function, the following inequality is used: (ref here) $C(m^2,m-1) \geq (m^2-m+1)^{m-1}$. Is there a ...
  • 214
3 votes
1 answer
74 views

Combinatorially proving $F_{n} = \sum_{i=0}^{\left\lfloor n/2 \right\rfloor}\binom{n-i}{i}$, where $F_n$ is the $n$-th Fibonacci number [duplicate]

Prove the following combinatorially: $$F_{n} = \sum_{i=0}^{\left\lfloor n/2 \right\rfloor}\binom{n-i}{i}$$ So, I know that the Fibonacci number counts the number of ways to cover a $1 \times n$ ...
  • 55
1 vote
3 answers
70 views

Why does the multinomial coefficient count permutations but the binomial coefficient count combinations?

The binomial coefficient $n \choose k$ counts the number of ways to choose $k$ objects from a set of $n$ objects (order does not matter). The more general multinomial coefficient $n \choose {n_1,n_2,.....
  • 922
0 votes
2 answers
33 views

In how many ways can a given process occur

An auditorium has two rows of seats, with 50 seats in each row. 100 indistinguishable people sit in the seats one at a time, such that each person, except for the first person to sit in each row, must ...
  • 1,919
3 votes
1 answer
72 views

Find the expected number of hours all 512 people suffer

In a crowded room with 512 people, there are 9 different types of blood antigens. Each person has a blood type corresponding to a distinct subset of the antigens; the remaining of the antigens are ...
  • 1,919
2 votes
1 answer
83 views

Proving that for all $1 \leq k \leq p - 1$, $p$ prime, $\binom{p}{k} \equiv 0 \bmod p$

I decided to prove by induction (though am running into some issues). (Base case) When $k = 1$, we have $$\binom{p}{1} = \frac{p!}{1! \cdot (p - 1)!} = p \equiv 0 \bmod p.$$ When $k = p - 1$, we have $...
1 vote
0 answers
55 views

Summation of series involving binomial coefficients : $\sum_{r=1}^n {n\choose r}r^{n-r}$.

I was trying to find the sum of the following series: $\sum_{r=1}^n {n\choose r}r^{n-r}.$ Actually, this series came out as the answer to the question : Find the number of functions $f(n)$ on set $A,$ ...
1 vote
0 answers
53 views

Sum of $n$ degree derivatives taken w.r.t. different combinations of arguments

Consider $$ \Pi(b, s) = \int_{0}^{b} \chi(t)\ln(s-t) dt. $$ Notice that taking derivatives with respect to $s$ can help in obtaining formulae for integrals with the derivatives of $\chi$. $$ \frac{d}{...
2 votes
2 answers
87 views

Chebyshev polynomials to hypergeometric function?

I am trying to derive this hypergeometric version of the Chebyshev polynomials https://en.wikipedia.org/wiki/Chebyshev_polynomials#Explicit_expressions $$U_n(x) = \frac{\left (x+\sqrt{x^2-1} \right )^...
  • 125
1 vote
0 answers
33 views

Proof of entity (5.24) of Concrete mathematics - Page 169? [duplicate]

I've tried everything but can't quite figure out how to prove this entity using non-induction approach. Anyone have any idea on this entity? $${\sum_{k}}\binom{l}{m + k}\binom{s + k}{n}(-1)^{k} = (-1)^...
1 vote
2 answers
79 views

Find the coefficients of product

Given the following product, $$(1+ax)(1+a^2x)(1+a^3x)\cdots (1+a^mx) $$ where $a$ is some real number which will be taken to be unity in the end. I want to know the coefficient of general term of ...
2 votes
1 answer
71 views

Asymptotic Stirling approximation of binomial coefficients

In the paper [B. Derrida, K. Mallick, J. Phys. A 30 (1997) 1031–1046] the following approximation (equation 27 page 6) is done for products of binomial coefficients invoking the Stirling approximation:...
  • 187
0 votes
2 answers
55 views

Is there a closed form of $\sum\limits_{r=0}^n \binom{n-r}{r}x^r$? [duplicate]

$\sum\limits_{r=0}^n \binom{n-r}{r}x^r=\sum\limits_{r=0}^{\lfloor n/2\rfloor} \binom{n-r}{r}x^r$ I need its closed form for a probability problem. I know about the case where $x=1$. It's the sum of ...
5 votes
1 answer
120 views

Positivity of a matrix built on Pascal's triangle

For an integer $n$, let $T_n$ be the $(n+1) \times (n+1)$ Toeplitz matrix built on the $2n$th row of Pascal's triangle, i.e., its $(i,j)$ entry equals $\binom{2n}{n+i-j}$. For example, $$ T_2 =\begin{...
24 votes
4 answers
1k views

Is this a new discovery in the diagonals of Pascal's triangle?

To preface, I am a senior in high school and my knowledge of combinatorics and its notation is quite limited. I came across Pascal's triangle while drilling the binomial expansions into my head, and I ...
  • 381
2 votes
2 answers
78 views

Number of ways to invest $\$20,000$ in units of $\$1000$ if not all the money need be spent

Working through a combinatorics section currently and am working on this $2$-part problem. I have solved part $a$ quickly and will provide my work below but am having some trouble with part $b$ and ...
1 vote
2 answers
72 views

A certain sum of multinomial coefficients

I would like to know if there is a nice expression for the sum $$ S(n)=\sum_{i+j=n}\binom{3i}{i,i,i}\binom{3j}{j,j,j} $$ where $n$ is a non-negative integer. I have entered in the first few values of ...
2 votes
3 answers
76 views

Find the values of $\sum_{k=0}^{n} \frac{{n\choose k }}{k+1}$

Let m be a positive integer.Find the values of $$\sum_{k=0}^n \frac{{n\choose k }}{k+1}$$. Leave your answer in terms of n where appropriate. Remark. There is an alternative method for computing the ...
  • 21
1 vote
1 answer
52 views

Closed form for $\sum\limits_i (-1)^i \binom{m}{i} \sum\limits_{j \ge k+1} \binom{2k+1-m}{j-i}.$

I would like a closed form for the sum $S(m,k) = \sum\limits_{i=0}^m (-1)^i \binom{m}{i} \sum\limits_{j = k+1}^{2k+1} \binom{2k+1-m}{j-i}.$ For $m=0$ we always get $4^k,$ so I assume $k>0.$ For $1 \...
  • 4,815
0 votes
0 answers
29 views

how to prove that $\sum_{k=1}^{n+1} \binom{n+1}{k} \sum_{\ell=0}^{k-1} \binom{n}{\ell}=2^{2n}$ [duplicate]

I'm trying to solve a problem in two different ways. For the most 'straightforward calculation method' I need that $$\sum_{k=1}^{n+1} \binom{n+1}{k} \sum_{\ell=0}^{k-1} \binom{n}{\ell}=2^{2n}.$$ I ...
2 votes
2 answers
151 views

Showing the root of $\sum_{j=1}^n \binom{n}{j} \frac{j x^{j-1}}{(1-x^j)^2}$ approaches $0$ as $n \to \infty$.

Let $n > 1$, and let $\varepsilon_n$ be the root of $g_n(x) = \sum_{j=1}^n \binom{n}{j} \frac{j x^{j-1}}{(1-x^j)^2}$ that is in the interval $(-1, 1)$. Why is $\lim_{n \to \infty} \varepsilon_n = 0$...
0 votes
0 answers
66 views

A summation formula for number of ways $n$ identical objects can be put in $m$ identical bins

A famous counting problem is to calculate the number of ways $n$ identical objects can be put into $m$ identical bins. I know that this problem is somewhat equivalent to Partition problem. There is no ...
1 vote
0 answers
30 views

Correlation of a binomial RV with itself

I have a vector $\mathbf{A}=\begin{bmatrix}a_1&a_2&a_3\end{bmatrix}$ where $a_i$ is a Bernoulli RV with PMF, $$p(a_i)=\begin{cases} \frac{1}{2} & \text{if } a_i = 1\\ \frac{...
  • 93
3 votes
2 answers
130 views

Finding $\arg\min \sum_{j=1}^n \binom{n}{j} \frac{1}{1-(1-2x)^j}$ for $x \in (0, 1)$.

For a positive integer $n$, let $p_n$ be the value of $x \in (0, 1)$ that minimizes $f(x) = \sum_{j=1}^n \binom{n}{j} \frac{1}{1-(1-2x)^j}$ on the stated interval. What is $p_n$? The function $1/(1-(...
5 votes
2 answers
134 views

Prove that $\sum_{k=1}^n\frac{\prod_{1\leq r\leq n, r\neq m}(x+k-r)}{\prod_{1\leq r\leq n, r\neq k}(k-r)}=1$

For arbitrary $x$ and $1\leqslant m\leqslant n$, prove the following: $$\sum_{k=1}^n\frac{\prod_{1\leq r\leq n, r\neq m}(x+k-r)}{\prod_{1\leq r\leq n, r\neq k}(k-r)}=1$$ I'm looking for a proof that ...
  • 516
0 votes
0 answers
66 views

Find the value of $A,$ a summation

If $n$ is even then find the value of $$S=\binom{n}{0}\binom{n+5}{n}+\binom{n}{2}\binom{n+5}{n-2}+\binom{n}{4}\binom{n+5}{n-4}+\cdots$$ If somehow I can find the value of $$A=\binom{n}{1}\binom{n+5}{...
2 votes
2 answers
103 views

How do you prove that $\sum\limits_{r=0}^{n}\binom{n}{r}\binom{n+r}{r} =\sum\limits_{r=0}^{n}( -1)^{n-r} 2^{r}\binom{n}{r}\binom{n+r}{r}$?

While proving this on Quora, I came across this equality: $\displaystyle \sum _{r=0}^{n}\binom{n}{r}\binom{n+r}{r} =\sum _{r=0}^{n}( -1)^{n-r} 2^{r}\binom{n}{r}\binom{n+r}{r}\tag*{}$ Like how did $2^r$...
3 votes
3 answers
110 views

Evaluating $\binom{40}{0}\binom{20}{10}+\binom{41}{1}\binom{19}{10}+\cdots+\binom{50}{10}\binom{10}{10}$

Finding value of $$\binom{40}{0}\binom{20}{10}+\binom{41}{1}\binom{19}{10}+\cdots+\binom{50}{10}\binom{10}{10}$$ Using $\displaystyle \binom{n}{r}=\binom{n}{n-r}$ $\displaystyle \binom{40}{0}\binom{...
0 votes
0 answers
32 views

How to prove $\sum_{k=0}^{n-1}(-1)^k\binom{n+k}{2k+1}C_k=1$? [duplicate]

How to prove the following identity? $$ \sum_{k=0}^{n-1}(-1)^k\binom{n+k}{2k+1}C_k=1 $$ where $C_k$ is the $k$th Catalan number, $C_n=\frac{1}{k+1}\binom{2k}{k}$. This question is similar to this but ...
4 votes
1 answer
69 views

Expectation of the max number of times an element is chosen, if repeatedly randomly choosing a subset out of a set

Given a set of $n$ elements. For a total of $s$ times, you randomly choose exactly $m$ elements among them. (i.e. each $m$-element set has $p=\frac{1}{\binom{n}{m}}$ of being chosen) Here $n\gg m$ and ...
1 vote
0 answers
59 views

Sum of products of binomial coefficients.

If $(1+x+x^2)^n= \Sigma_{r=0}^{2n}a_r x^r$ then $a_r- \binom n1 a_{r-1}+\binom n2 a_{r-2}-\binom n3 a_{r-3}+....+(-1)^r\binom nr a_{0} $ is equal to (r is not a multiple of 3) Options a)0 b) $^nC_r$ c)...
-2 votes
2 answers
69 views

Prove that $\sum_{k=0}^{n}\binom{n}{k}\frac{1}{2n-2k+1}=\frac{(2n)!!}{(2n+1)!!}$ [closed]

Prove that \begin{equation} \sum_{k=0}^{n}\binom{n}{k}\frac{1}{2n-2k+1}=\frac{(2n)!!}{(2n+1)!!} \end{equation} This sum appears in the orthogonalization of Legendre polynomials.
4 votes
1 answer
263 views

primes and binomial coefficients

Lets us denote by $\mathbb{P}$ the set of prime numbers. It is well known that, given an integer $p>1$ : $$\boxed{p\in\mathbb{P}\Leftrightarrow\forall k\in\{1,\cdots,p-1\},\,p\mid\binom pk}$$ I ...
  • 7,176
0 votes
2 answers
131 views

Can one expand $(a + b)^{{i}}$?

I'm solving a transcendental equation and I currently have: $$-i\ln(ix + \sqrt{1 - x^2}) = \frac{1}{(i\ln(x) + \sqrt{1 - \ln(x)^2})^i}$$ I don't know how to binomially expand the bottom denominator ...
user avatar
2 votes
1 answer
68 views

Sum of binomial coefficient equation

I am trying to show the following equation using binomial expansion but it's not getting me anywhere. How should I set it up? I've tried expanding $(2+2)^{n}$ and using the fact that but it's not ...
  • 173
2 votes
2 answers
62 views

Big-O of the log of sum of binomial coefficient

Let $n\in \mathbb{N}$, $k\in \mathbb{N}$, $k<n$, I want to prove $\log{\left(\sum_{i=0}^k \binom{n}{i}\right)} = O\left(k\log(\frac{n}{k})\right)$. I tried to use the approximation for the ...
  • 145
2 votes
0 answers
46 views

Identity involving q-Pochhammer symbols -- "Normalization"

I am trying to prove the following identity involving q-Pochhammer symbols $$ \sum_{m=0}^{n} \dfrac{1}{(c^{-1};c^{-1})_m (c;c)_{n-m}}=1$$ where $n\in \mathbb{N}$, $c\in \mathbb{R}$ and $(a;q)_n=\prod_{...
4 votes
1 answer
102 views

Why $\bigg\lfloor \frac{n^m}{\binom{n}{m}}\bigg\rfloor=m!$ for $n>(m+1)^{m+2}$?

Let $n,m\in \mathbb{N}_0$. I need to prove that if $n>(m+1)^{m+2}$ then $$ \Bigg\lfloor \frac{n^m}{\binom{n}{m}}\Bigg\rfloor=m!.$$ Since $$ \frac{n^m}{\binom{n}{m}}=\frac{n^m(n-m)!}{n!}m!=m!+\bigg(\...

1
2 3 4 5
145