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

learn more… | top users | synonyms (1)

4
votes
1answer
38 views

How to prove that any natural number $n \geq 34$ can be written as the sum of distinct triangular numbers?

Sloane's A053614 implies that $2, 5, 8, 12, 23$, and $33$ are the only natural numbers $n \geq 1$ which cannot be written as the sum of distinct triangular numbers (i.e., numbers of the form ...
0
votes
1answer
25 views

Help evaluating a partial sum with factorials and binomial coefficients

I come from a CS background and had to contend with a problem similar to this one. Essentially, I want a general-case estimate on how many rolls I'd have to make to land on the same number twice with ...
3
votes
2answers
104 views

Algebraic proof that $\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$

I'm looking for an algebraic proof of this identity for $n, k \in \mathbb{N}$: $$\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$$ So far, I've turned the left hand side of the equality into ...
5
votes
2answers
112 views

When does this sum of combinatorial coefficients equal zero?

$p>2$ is a prime number, $n\in \mathbb{N}$. Is the following statement true or false? Thanks. $$\sum_{i=0}^{\lfloor n/p\rfloor}(-1)^i {n\choose ip}=0$$ iff $n=(2k-1)p$ for some $k\in \mathbb{N}$.
2
votes
4answers
140 views

Coefficient of binomial expansion

The coefficient of $x^3$ is $4$ times the coefficient of $x^2$ in the new expansion of $(1+x)^n$. Find the value of $n$.
0
votes
0answers
20 views

Dividors of binomialcoefficient

Is it true, that $ \prod\limits_{\frac{n}{2}<p\le \frac{6n}{7}} p$ divides $ \binom{3n}{n} $? Thank you in advance. I have no idea how to prove it.
4
votes
3answers
105 views

Showing ${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}$

Prove that for integers $n \geq 0$ and $a \geq 1$, $${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}.$$ I figured I'd post this question, ...
4
votes
2answers
396 views

This question involves Pascal's Triangle & Binomial Theorem. Full Question

Could anyone please help me on the following problem: Factorize the expression $P(n)=n^x-n$ for $x=2,3,4,5$ Determine if the expression is always divisible by the corresponding $x$. If divisible use ...
0
votes
4answers
110 views

calculate-binomio-newton

i am help Calculate: $$(C^{16}_0)-(C^{16}_2)+(C^{16}_4)-(C^{16}_6)+(C^{16}_8)-(C^{16}_{10})+(C^{16}_{12})-(C^{16}_{14})+(C^{16}_{16})$$ PD : use $(1+x)^{16}$ and binomio newton
4
votes
2answers
166 views

How to calculate the number of integer solution of a linear equation with constraints?

If an equation is given like this , $$x_1+x_2+...x_i+...x_n = S$$ and for each $x_i$ a constraint $$0\le x_i \le L_i$$ How do we calculate the number of Integer solutions to this problem?
8
votes
2answers
131 views

An interesting property of binomial coefficients that I couldn't prove

So when I was trying to prove the argument in this link I've come up with something. When you extract the left term from the right term, you get the term under them. What is interesting is that as ...
1
vote
2answers
71 views

How to derive the Taylor expansion form of a polynomial expression?

I want to change this polynomial into the form $\sum_{k=0}^m a_k x^k$ $$q_m(x)=\sum_{k=0}^m(-1)^k\binom{2m+1}{2k+1}x^k(1-x)^{m-k}$$ I see no way to do this as I fear one might need intricate binomial ...
4
votes
1answer
70 views

Proving a Binomial Identity

Problem $\boldsymbol{25}$ [$\boldsymbol{5}$ Points]: Show that $$ \sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}=2^n $$ Hint: Denote the left hand side by $f(n)$ and prove that $f(n+1)=2f(n)$. Original Image ...
0
votes
0answers
34 views

Binomial-like distribution

Starting with $1$, for $n$ trials multiply by either $1+p$ or $1-p$, with $0 \le p< \le 1$. Does this distribution have a name? What are its properties, such as density (PDF)? It is like a skewed ...
10
votes
0answers
89 views

Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem: Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$ Where the Problem Comes From: If we ...
7
votes
3answers
148 views

Show that $p \in \left[\frac{4^m}{2\sqrt{m}},\frac{4^m}{\sqrt{2m+1}}\right]$

If the number of ways in which $m$ identical apples can be put in $2m$ boxes, so that no box contains more than one apple, is $p$, prove that $$p \in ...
-1
votes
1answer
40 views

Equality involving binomial coefficient

I think the following equality is correct, but I'm not sure, so I'm asking you: $$\left(\prod_{\large\tfrac{n}{2}\,<\,p\,\le\,\tfrac{6n}{7}}p\right)\cdot\left(\prod_{\large ...
0
votes
1answer
46 views

Approximation for a binomial coefficient sequence summation

What is a good approximation to $$\dfrac{{\binom{k}{i}}{\binom{k}{i}}(i-1)!}{\binom{k(k-1)/2}{i}}$$ $$\dfrac{{\binom{k}{i}}{\binom{k}{i}}(i-1)!}{(2^{(\log ...
4
votes
0answers
73 views

On a unique(?) binomial property of $3003$

Given the triangular number, $$T_k = \frac{k(k+1)}{2}$$ and remembering that, $$\binom{n}{m}=\binom{n}{n-m}$$ Excluding $a_0=1$, we then have the six-fold (at least) equalities, $$\begin{aligned} ...
0
votes
2answers
77 views

Is there a good approximation for this?

What is a good approximation for $\dfrac{k!}{\binom{k^2}{k}}$ as a function of $k$? Is there a $k_0\in\Bbb N$ such that for all $k\gt k_0$, ...
-1
votes
1answer
44 views

Is there a short expression for this?

Is there a closed form expression for $$\Bigg(\binom{n}{k-1}+\binom{n-1}{k-1}+\dots+\binom{k-1}{k-1}\Bigg)(k-1)!= \sum_{i=0}^{n-k+1}\frac{(n-i)!}{(n-k+1-i)!},$$ ...
0
votes
3answers
47 views

Lower bound for binomial coefficient

Prove that for sufficiently large $ n $ the following inequality holds: $ \binom{5n}{4n}>12^n $. Thank you in advance.
12
votes
5answers
2k views

Combinatorial proof of a binomial coefficient summation.

Let $n$ and $k$ be integers with $1 \leq k \leq n$. Show that: $$\sum_{k=1}^n {n \choose k}{n \choose k-1} = \frac12{2n+2 \choose n+1} - {2n \choose n}$$ I was told this is supposed to use a ...
1
vote
1answer
44 views

Is it possible to evaluate this binomial sum?

Would it be possible to evaluate this sum? $$\sum_{k=0}^{N/2}k\binom{N+1}{k},$$ where $N$ is even? I know that the sum $$\sum_{k=0}^{N+1}k\binom{N+1}{k}=2^N(N+1)$$ (by ...
2
votes
3answers
594 views

Algebraic proof of $\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$

I can't figure out an algebraic proof for the following identity: $$\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$$ Combinatorical solution: We can see that as choosing some from ...
3
votes
4answers
54 views

How do i prove that $\sum\limits_{r=0}^k \binom{m}{r}\binom{n}{k-r} = \binom{m+n}{k}$ [duplicate]

I have tried the following: Expanding the coefficients and i end up with something like this: $\sum\limits_{r=0}^k \binom{m}{r}\binom{n}{k-r} = \frac{m!}{(m-r)!r!} \frac{n!}{(n-k+r)!(k-r)!}$ and then ...
1
vote
0answers
70 views

A Summation Challenge

I am trying to understand the solution of problem from its editorial by djdolls' answer,I am not able to understand a particulare step which is as follows: $$S(n)=\sum_0^D (-1)^i \cdot ...
1
vote
0answers
55 views

How prove $\frac{1}{4a b}\;\left[\frac{(b+1)^{b+1}}{b^{b}}\right]^{a}\;<\;\dbinom{a(b+1) }{a}\;<\;\left[\frac{(b+1)^{b+1}}{b^{b}}\right]^{a} $

Let $a\in\mathbb N$, and $b\in\mathbb R, b\geq 1$ How prove $\frac{1}{4a b}\;\left[\frac{(b+1)^{b+1}}{b^{b}}\right]^{a}\;<\;\dbinom{a(b+1) }{a}\;<\;\left[\frac{(b+1)^{b+1}}{b^{b}}\right]^{a} $
1
vote
0answers
23 views

How to calculate the $k$-dimension of a subspace of a polynomial ring?

Let $k$ be an infinite field and $R:=k[x_1,...,x_n]$ the polynomial ring in $n$ indeterminates. Why is the $k$-dimension of $U$ given by $\begin{pmatrix} n+m-1 \\ m\end{pmatrix}$, when $U$ is the ...
2
votes
2answers
17 views

Generate an integer matrix such that all submatrices are non-singular

I need to generate an $\infty \times N$ integer matrix with a few properties. The top $N$ rows (and $N$ columns) should be the identity matrix. Any square submatrix (meaning the result after ...
4
votes
1answer
559 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
2
votes
3answers
94 views

How to prove that $(\frac{n}{k})^k\leq{{n}\choose{k}}\leq\frac{n^k}{k!}$?

How to prove that $(\frac{n}{k})^k\leq{{n}\choose{k}}\leq\frac{n^k}{k!}$? I can only manage to see the second inequality, could any one give a hint about the first one?
0
votes
1answer
43 views

Evaluating a cube root

How to evaluate $(8.024)^{1/3}$ from $(1+3x)^{1/3}$.I already expand it until $x^3$ but i still can't get the answer. I tried googling for the working using binomial theorem but i failed.
2
votes
2answers
332 views

Counting binary strings that have atmost k consecutive 0's

I know how to count how many binary strings with length n and having exactly k 0's are there but i am not able to find a way to count the number of binary strings that have exactly x 0's and y 1's and ...
4
votes
2answers
47 views

Another binomial coefficient sum

In my work I ran across the following binomial coefficient sum: $$ S=\sum_{a=0}^{n-1-l} (-1)^a \binom{n}{l+1+a} \binom{l+a}{l} $$ where $n\geq 0$ and $0\leq l \leq n-1$. I browsed the web and found ...
0
votes
0answers
42 views

Sum involving binomial $\sum_{k=0}^{n} \binom{3n}{3k}$ [duplicate]

The main question is to evaluate: $$\sum_{k=0}^{n} \binom{3n}{3k}$$ There is a standard technique but I cannot split the sums apart and then add them together. Could you help with this step?
4
votes
3answers
229 views

Nested… binomials coefficients? [closed]

Can I have a proof that this number exists? The number: $$\binom{1}{\binom{2}{\binom{3}{\binom{4}{\vdots}}}}$$ If the number exists, then what is the closed form of that number?
0
votes
2answers
34 views

Radius of convergence of complex series

I need help for this exercise: We consider the following sequence of function $(f_n)_{n\ge0}$: $$f_n:\mathbb{C} \rightarrow \mathbb{C}$$ $$z \mapsto \frac{1}{p_n}[z(1-z)]^{4^n}$$ where $p_n$ is the ...
13
votes
1answer
134 views

“Binomiable” numbers

Is there a nice criterion to determine whether a given natural $m$ can be written as a binomial number $\binom{n}{k}$ with $1 < k < n-1$? I've been thinking on this problem with a friend and ...
1
vote
3answers
31 views

Switching the order of summations of a certain function

I am looking to switch the order of the summations of the following function: $$ \lambda = -\sum_{c=1}^{n-1} \sum_{k=c}^n {k \choose c} \frac{(-1)^k}{k!} f^{k-c}U(-c,k-2c+1,-f)\phi(n,k) $$ I don't ...
11
votes
3answers
438 views

Evaluating a sum involving binomial coefficient in denominator

I came across the following sum: $$\sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1)^2}\frac{4^k}{{2k \choose k}}$$ I thought that this can be evaluated using the expansion of ...
2
votes
0answers
46 views

Finding a closed form for this summation

I have been trying to derive a few identities using some bell polynomials and a technique i have come up with and i came across this summation: $$ \rho(n,k) = \sum_{j=0}^k {k \choose j} {\frac{-j}{2} ...
0
votes
1answer
18 views

Success rate of a player trying to guess a bitstring with given constriants

For work at my university I try to solve a problem. I have a bit string with given length $len$ and count of active bit $active$ An example could be: 1001 0110 ...
4
votes
4answers
188 views

Permutations containing a given subsequence

Let $f(n)$ denote the number of $4n$-long strings formed from $2n$ a's and $2n$ b's, such that the string contains, as a (possibly non-consecutive) subsequence, a pattern containing $n$ a's and $n$ ...
6
votes
2answers
221 views

Prove $(1-x)^{2k+1} \sum\limits_{n\ge 0}\binom{n+k-1}{k}\binom{n+k}{k} x^n = {\sum\limits_{j\ge 0} \binom{k-1}{j-1}\binom{k+1}{j} x^j} $

I stumbled upon the identity $$(1-x)^{2k+1} \sum\limits_{n\ge 0}\binom{n+k-1}{k}\binom{n+k}{k} x^n = {\sum\limits_{j\ge 0} \binom{k-1}{j-1}\binom{k+1}{j} x^j}. $$ The right-hand side is a polynomial. ...
2
votes
0answers
22 views

Prove for $ \forall n \in \mathbb{N}, \exists x,y,z$ ( $0 \leq x < y < z$ ) such that $ n = \binom{x}{1} + \binom{y}{2} + \binom{z}{3}$ [duplicate]

I'm trying to solve a problem from the combinatorics book. Prove or disprove for $ \forall n \in \mathbb{N}, \exists x,y,z \in \mathbb{N} $ ($0 \leq x < y < z$) such that $$ n = \binom{x}{1} + ...
3
votes
1answer
64 views

Let n and k be integers such that $n > k ≥ 0$. Show that ${n\choose k }$+ ${n\choose k + 1 }$ = ${n + 1\choose k + 1 }$

I'm trying to prove it using algebra and it didn't get very far. Here is how far I got. Now I know ${n\choose k } = \frac{n!}{k!(n-k)!}$ So the entire expression would be $$\frac{n!}{k!(n-k)!} + ...
4
votes
4answers
204 views

Convolution of binomial coefficients

As part of a (SE) problem I've been working on, I came up with this expression: $$ \sum_{i=0}^M\binom{M-1+i}{i}\binom{M+i}{i} $$ I'd like to get a closed form for this, but after a considerable amount ...
2
votes
2answers
39 views

$\sum_{i=1}^n\frac{1}{i}\binom{n}{i}p^i(1-p)^{n-i}\leq\frac{K}{n} $

How can it be proved that, if $0<p<1$, then $$\sum_{i=1}^n\frac{1}{i}\binom{n}{i}p^i(1-p)^{n-i}\leq\frac{K}{n} $$ for some constant $K$? Thanks in advance for every suggestion.
3
votes
2answers
227 views

How can I prove this combinatorial identity?

Let $n,m$ be non-negative integers. How can one prove the following identity? $$\sum_{j=0}^n j\binom{2n}{n+j}\binom{m+j-1}{2m-1}=m\cdot4^{n-m}\cdot\binom{n}{m}$$