# Questions tagged [binomial-coefficients]

Coefficients involved in the Binomial Theorem. $\dbinom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

6,902 questions
Filter by
Sorted by
Tagged with
87 views

38 views

### Proving by Induction a Combinatorial Binomial

I'm currently stuck trying to prove that for all items in the sequence $\binom{n+1}{2}$, for all $n\geq 1$, that $\binom{n+1}{2}=\sum \limits _{i=0}^ni$. My first assumption is to solve for my base ...
38 views

### Simplifying $\sum_{k=1}^n\binom n{k-1}\frac{x^{k+n}y^{n-k+1}}k.$ [closed]

I want to simplify this binomial expression: $$\sum_{k=1}^n\binom n{k-1}\frac{x^{k+n}y^{n-k+1}}k.$$ I tried to simplify it but it's pretty hard . So if someone can help with a hint or solution.
40 views

33 views

### Number of ones in the dyadic expansion of m [closed]

I was going through a paper where I stuck on a combinatorial argument as follows I want help with the first assertion i.e proving the inequality $\alpha(m+l)\le\alpha(m)$. As the author suggests it is ...
27 views

56 views

### Find $100$th number $k$ such that there is no $n$ for which $n$! ends in $k$ zeroes.

$24! = 620,448,401,733,239,439,360,000$ ends in four zeroes, and $25! = 15,511,210,043,330,985,984,000,000$ ends in six zeroes. Thus, there is no integer $n$ such that $n!$ ends in exactly five zeroes....
207 views
+500

### Asymptotic for a binomial sum

Is it possible to derive an asymptotic expression as $n \to \infty$ for the following sum: $$S_n(a,x) = \sum_{k=1}^n \binom{n}{k} \frac{k!^2 x^k}{k \cdot (a)_k}$$ $(a)_k$ is the rising factorial (...
1 vote
30 views

### Lower bounding a exponential/binomial expression

I have been struggling to lower bound the following expression \begin{equation} f(N):= \frac{1}{N}\sum_{i=1}^N \frac{1}{2^N} \sum_{k=1}^{i} 2^{i-k} \binom{N+k-2}{k-1} , \end{equation} with some simple ...
42 views

### Find Sum of (-1)^r × nCr/r

Find $\sum_{r=1}^n (-1)^r × \frac{1}{r} \binom{n}{r}$ How to find this? I tried doing it by taking $x$ common from the expansion and then integrate it using by parts but that didn't go well. Please, ...
45 views

### Proving $\sum_{k=0}^{n-m}(-1)^k{n-m\choose k}\frac{k}{k+m}=-{n\choose m}^{-1}$

So apparently we can calculate the value of this series as $$\sum_{k=0}^{n-m}(-1)^k{n-m\choose k}\frac{k}{k+m}=-\frac{m!(n-m)!}{n!}=-{n\choose m}^{-1}$$ But I'm curious to prove this holds. So I ...
1 vote
23 views

### Probability of extracting 1 Red ball from a urn and then k Red balls at the sequent extraction

I'm struggling with a quite basic probability problem, and my knowledge in this field is not very deep, so I would appreciate some help. Here is the problem. Problem formulation We have some balls in ...
81 views

### How do you calculate combinations with fractions (eg, "$\frac13$ choose $2$")? [closed]

I was given "$\frac13$ choose $2$" and asked to compute. I checked the answer and it's $-\frac19$, but I have no clue how to arrive at this answer. How do you deal with fractions in the ...
1 vote
64 views

### finding a closed formula for $\sum_{k=0}^{n} k{2n \choose k}$

my attempt: $\sum_{k=0}^{n} k{2n \choose k}=\sum_{k=0}^{2n} k{2n \choose k}-\sum_{k=n+1}^{2n} k{2n \choose k}$ the first term in the right hand side suppose there are $2n$ poeple, we have to choose a ... 18 views

### Upper bound on a binomial sum

Consider the following binomial series. \begin{equation} \frac{1}{2^{n}a^{n}}\sum_{i=0}^{k}{{n}\choose{i}} a^{i}, \end{equation} where $k = n - \text{poly}(\log n),$ and $a > 1$ is a constant. I am ...
1 vote
42 views

39 views

### A different upper bound for the binomial coefficient

I need to prove the following statement: If $3\leq k < t$ then \begin{equation*} \binom{t}{k} < 2^{t-1}-k+1. \end{equation*} I was given the hint to prove it by induction over $t$ with $k$ ...
40 views

### How do I prove this binomial identity by just using symmetric property and reversing the upper index?

$$\sum_k\binom{l}{m+k}\binom{s+k}{n}(-1)^k=(-1)^{l+m}\binom{s-m}{n-l},l\ge0,\{l,n,m\}\subset\mathbb{N},\{s\}\subset \mathbb{R}$$ P.S. Please use these identities below to prove it Symmetric ...
30 views

### How is the diagonal constraint in lattice path needed for the Catalan proofs?

I have been reading about the Catalan numbers and how they are they appear in many problems such as: lattice paths valid pair of parenthesis mountains with up/downstrokes non-crossing handshakes ...
42 views

### Sum of factorials in 3D symmetrical random walk $\sum_{k=0}^n\binom{n}{k}^2\binom{2(n-k)}{n-k}$

I'm trying to prove that in a tridimensional symmetrical random walk all states are transient. Since it's an irreducible Markov chain, I only have to prove it for a generic state, since they are all ...
26 views

### Order of $m+1$ in the multiplicative group of integers modulo $n$

I'm trying to figure out in what cases of $n$ and $m$ the following isomorphism holds. $$\mathbb{Z}_n^\times/\left<1+m\right>\cong\mathbb{Z}_m^\times$$ I'm considering the restriction that $n$ ...
31 views

### Simplifying $(x-1)\cdot(x-3)\cdots (x-(n-2))$ in terms of binomial coefficients.

Can we write the following product in terms of binomial coefficients ? $(x-1)\cdot(x-3)\cdots (x-(n-2))$. i.e the the product take up odd numbers.
112 views

### Why are the catalan numbers giving the unique/correct patterns from all the combinations?

I am reading about catalan numbers and they are considered to represent the number of valid pair of parentesis, mountains etc. Although the number checks out correct when comparing against specific ...
39 views

### How do we handle the factorials in the binomials/choice numbers?

Apparently the following is a known equality: $\frac{1}{n + 1} {2n \choose n} = \frac{2n!}{n!(n + 1)!} = \frac{1}{2n + 1}{2n + 1 \choose n}$ but I can't really figure out how to produce the equality. ...
17 views

50 views

### Probability of 2 specific people ending up in a random group of 3 people?

18 people are being randomly selected into groups of 3. Bob and Alice want to know the chance that they would be selected to be in the group together. My first thought was to find all groups where ...
80 views

### Show that $\sum_{k=1}^nk {n \choose 2k+1}=(n-2)2^{n-3}$

I am trying to show that $$\sum_{k=1}^nk {n \choose 2k+1}=(n-2)2^{n-3}.$$ When approaching these types of problems I always try to compute a few small, specific values myself just to get a better ...
74 views

### Given $n\geq 0, j\geq 1.$ How many solutions to: $\sum_{i=1}^j x_i=n,$ where $x_i\geq 0$ and $x_i$ are all different?

Given $n\in\mathbb{N}\cup\{0\},\ j\in\mathbb{N}.$ How many solutions are there to: $\sum_{i=1}^j x_i=n,$ where $x_i\in\mathbb{N}\cup\{0\}$ for all $i\in\{1,\ldots,j\}$ and $x_k\neq x_l$ if $k\neq l\ ?$...
57 views

### Can this Sum be reduced? It is calculating the expected value of a poker hand when you "Run it multiple times" for the last card.

There is a scenario in poker (Texas Hold'em) where if two players go "all in", they have the option to deal the remaining cards multiple times and it results in multiple pots that they could ...
29 views

### Expansion of factorial as linear combination of binomial coefficients [duplicate]

Let $k \leq n$ be positive integers. I would like a proof of the following identity: $$n!=\sum_{k=0}^n \binom{n}{k} (-1)^{n-k} k^n.$$ EDIT: For context, I am using this to verify the below ...
### Are there any simple simplifications of $\sum_{n=k}^N \binom{n}{k}^2$?
As the title states, is there any simplification to $\sum\limits_{n=k}^N \binom{n}{k}^2$? I found this which sums the squares of the "rows" of a pascal triangle, but here I'm trying to sum ...
### If $(1+x+x^2)^n=a_0+a_1x+a_2x^2+\dots+a_{2n}x^{2n}$ then prove that $a_0^2-a_1^2+a_2^2-a_3^2+\dots+(-1)^{n-1}a_{n-1}^2=\frac12a_n(1-(-1)^na_n)$
If $(1+x+x^2)^n=a_0+a_1x+a_2x^2+\dots+a_{2n}x^{2n}$ then prove that $a_0^2-a_1^2+a_2^2-a_3^2+\dots+(-1)^{n-1}a_{n-1}^2=\frac12a_n(1-(-1)^na_n)$ My Attempt: Replacing $x$ by $-x$ in the given ...