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

Filter by
Sorted by
Tagged with
3 votes
3 answers
87 views

Evaluating $\sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k}$

So far I've been able to determine that if $n, r, s$ are nonnegative integers, then $$ \sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k} = \begin{cases} 0 &\qquad\text{ if } r+s < n, \\...
user avatar
1 vote
1 answer
38 views

A combinatorial proof of a binomial coefficient summation identity. [duplicate]

$$\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$$ This is the exercise 3.3.6 of the book Invitation to Discrete Mathematics. The answer in book is Let M be an m-...
user avatar
6 votes
4 answers
172 views

Inequality involving sums with binomial coefficient

I am trying to show upper- and lower-bounds on $$\frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}\min(i, n-i)$$ (where $n\geq 1$) in order to show that it basically grows as $O(n)$. The upper-bound is easy to ...
user avatar
1 vote
1 answer
85 views

Determinant of matrix with binomial coefficient elements equal to $\binom{2n-1}{n}$

Given an $n \times n$ matrix $A_n$ with elements $a_{ij}=\binom{n+i-1}{j}$, $1 \le i \le n$, $1 \le j \le n$, I noticed that its determinant $\lvert A_n \rvert$ seem to satisfy: $$\lvert A_n \rvert = \...
user avatar
  • 1,869
3 votes
1 answer
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 ...
user avatar
  • 41
-1 votes
0 answers
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.
user avatar
0 votes
1 answer
40 views

When $\text{ord}_n(p)/m = \text{ord}_{n/m}(p)=1$

$\newcommand\ord{\text{ord}}$ For integers $n,m,p$, suppose $m$ and $n$ share the same prime divisors with $m$ dividing $n$, and suppose $\text{gcd}(p,n)=1$. I want to show that $\ord_n(p)/m=\ord_{n/m}...
user avatar
-1 votes
1 answer
60 views

Finite summation including binomial coefficients [closed]

I'm trying to solve the summation below, but I can't get a nice algebraically reduced equation. $$\sum_{k=1}^{2n} (-1)^{k-1}\frac{1}{\binom{2n}{k}} $$ I have tried to convert this into $\sum_{k=1}^{n}\...
user avatar
-1 votes
1 answer
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 ...
user avatar
0 votes
0 answers
27 views

If there are closed form for $\sum\limits_{m=i}^\infty \frac{2}{(2m-1)(2m-1)!}\binom{2m-1}{m-i}$

If there are closed form for $$\sum\limits_{m=i}^\infty \frac{2}{(2m-1)(2m-1)!}\binom{2m-1}{m-i},$$ where $m,i$ are positive integers. I have tried defining the generating function $$\sum\limits_{i=1}^...
user avatar
-1 votes
1 answer
49 views

Could someone please step me through the process of answering the Probability question?

Suppose that three unbiased dice are rolled. Find the probability that at least two of the three dice have a face value of five or more. Give your answer to two decimal places. I understand there are ...
user avatar
3 votes
3 answers
104 views

Prove that $\binom{13+m}{m}-(m+1)\binom{6+m}{m}\geq m$ for $m\in \mathbb{N}\backslash \{0,1\}$

Prove the following inequality for every $m\in \mathbb{N}\backslash \{0,1\}$: $$ \binom{13+m}{m}-(m+1)\binom{6+m}{m}\geq m.$$ By some computational arguments, the inequality seems to be true and in ...
user avatar
  • 125
0 votes
2 answers
41 views

Expected number of pairs with Hamming distance $d$ for a sample of $k$ random bit strings of length $n$

Say we were to uniformly sample $k$ times from a bit string with length $n$. What is the expected number of pairs with a Hamming distance $d$? In the limit of Hamming distance 0, I realize this ...
user avatar
1 vote
2 answers
28 views

Upper bound for binomial coefficients tighter than $(ne/k)^k$

In Shiryaev's book problems in probability, an upper bound for binomial coefficients is shown in section 1.2.1: $$\binom{m+n}{n}\le(1+m/n)^n(1+n/m)^m.$$ It seems that this bound is sharper than the ...
user avatar
  • 11
0 votes
3 answers
94 views

Generalizing observations made from the sequence $1,2,4,8,16,31,57,99,...$

Generalizing observations made from the sequence $1,2,4,8,16,31,57,99,...$ The first differences between the terms are: $1,2,4,8,15,26,42...$ The second differences (the differences between the ...
user avatar
  • 8,409
4 votes
2 answers
135 views

Question from isi previous years

(a) Show that $\left(\begin{array}{l}n \\ k\end{array}\right)=\sum_{m=k}^{n}\left(\begin{array}{c}m-1 \\ k-1\end{array}\right)$. (b) Prove that $$ \left(\begin{array}{l} n \\ 1 \end{array}\right)-\...
user avatar
  • 429
3 votes
2 answers
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....
user avatar
2 votes
3 answers
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 (...
user avatar
  • 30.2k
1 vote
0 answers
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 ...
user avatar
  • 198
-2 votes
0 answers
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, ...
user avatar
3 votes
1 answer
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 11
5 votes
3 answers
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 ...
user avatar
  • 59
1 vote
3 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
42 views

proving an inequality based on double products and binomial

Iv been trying to prove the following inequality: let $a_1,\ldots,a_n$ be a non-increasing sequence, i.e., $a_1\geq a_2\geq \cdots \geq a_n\geq 0$ such that $\sum_i a_i=m$. Then, prove that $$\prod_{i=...
user avatar
1 vote
1 answer
43 views

Proving a combinatorial identity related to convolution of central binomial coefficients

I'm trying to calculate the coefficient values for $f(x) = \sum_{k=0}^n {n \choose k}^2 (1+x)^{2n-2k}(1-x)^{2k}$. TL;DR I don't know where to begin in order to prove: $$\sum_{k=0}^r (-4)^k{n \choose k}...
user avatar
0 votes
2 answers
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$ ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1
0 votes
1 answer
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 ...
user avatar
  • 1,507
2 votes
0 answers
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 ...
user avatar
  • 162
0 votes
0 answers
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$ ...
user avatar
0 votes
1 answer
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.
user avatar
  • 3
2 votes
1 answer
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 ...
user avatar
  • 1,507
0 votes
1 answer
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. ...
user avatar
  • 1,507
0 votes
0 answers
17 views

Show that $\binom{r}{k}(p-\frac{k}{n})^k(q-\frac{(r-k)}{n})^{r-k} < q_k < \binom{r}{k}p^kq^{r-k}(1-\frac{r}{n})^{-r}$

Show that $$\binom{r}{k}\left(p-\frac{k}{n}\right)^k\left(q-\frac{r-k}{n}\right)^{r-k} < q_k < \binom{r}{k}p^kq^{r-k}\left(1-\frac{r}{n}\right)^{-r}$$ $q_k$ is given by $$\begin{align}q_k&=\...
user avatar
0 votes
1 answer
78 views

The lower bound about the binomial coefficient

From easy computation we can get \begin{align*} {n\choose{\ell}}=\frac{n}{\ell}\cdot\frac{n-1}{\ell-1}\cdots\frac{n-(\ell-1)}{1}\geq\frac{n^{\ell}}{\ell^{\ell}}, \end{align*} where the last inequality ...
user avatar
  • 1,396
22 votes
0 answers
602 views

A curious identity on $q$-binomial coefficients

Let's first recall some notations: The $q$-Pochhammer symbol is defined as $$(x)_n = (x;q)_n := \prod_{0\leq l\leq n-1}(1-q^l x).$$ The $q$-binomial coefficient (also known as the Gaussian binomial ...
user avatar
  • 2,865
2 votes
1 answer
38 views

Prove that each number $a$ in a Pascal's triangle decreased by $1$ is equal to the sum of the numbers within the parallelogram bounded by the sides of

Prove that each number $a$ in a Pascal's triangle decreased by $1$ is equal to the sum of the numbers within the parallelogram bounded by the sides of the triangle and the diagonalsgoing through $a$ (...
user avatar
  • 539
1 vote
0 answers
30 views

Existing summation approach for computation of combination?

Recently, I bumped into an interesting approach to alternately calculate the combinations. But I am not sure if there is such theory already existing for generic combinations with arbitrary factorials....
user avatar
  • 613
0 votes
1 answer
36 views

Arithmetic triangle and choices

In regards to the arithmetic triangle: 1 1 1 1 2 1 etc we know that it is a way to calculate the binomial coefficients or number of choices $C(n,r)$. ...
user avatar
  • 1,507
0 votes
1 answer
53 views

Triangle of Fibonacci

I was reading in a book a presentation about the arithmetic triangle of Fibonacci (to me it also looks like the pascal triangle). The figure presented is as follows: The text says: Having arranged ...
user avatar
  • 1,507
0 votes
0 answers
50 views

Show that $\sum_{k=0}^n 2^{-k}{k+n \choose k}=2^n$ [duplicate]

I am trying to show that $$\sum_{k=0}^n 2^{-k}{k+n \choose k}=2^n.$$ I try $n=0$: $$ \sum_{k=0}^0 2^{-k}{k+n \choose k}=2^0{0 \choose 0}=1=2^0, $$ and $n=1$: $$ \sum_{k=0}^1 2^{-k}{k+n \choose k}=1+ 2^...
user avatar
0 votes
2 answers
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 ...
user avatar
  • 113
2 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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\ ?$...
user avatar
0 votes
2 answers
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 ...
user avatar
  • 103
0 votes
0 answers
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 ...
user avatar
  • 433
6 votes
1 answer
178 views

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 ...
user avatar
  • 1,731
2 votes
1 answer
50 views

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 ...
user avatar
  • 5,256

1
2 3 4 5
139