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)

8
votes
3answers
753 views

Combinatorial proof for two identities [duplicate]

Does exist a combinatorial proof for the following two identities ? $\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$ $\sum_{k = 0}^{n} k\binom{n}{k} = n2^{n-1}$ I know how to derive the ...
12
votes
1answer
1k views

Combinatorial proof of $\sum\limits_{k=0}^n {n \choose k}3^k=4^n$

Using the following equation: $$\sum_{k=0}^n {n \choose k}3^k=4^n$$ I need to prove that both sides of the equation solve the same combinatorial problem. It's easy to see that the right side of the ...
11
votes
5answers
419 views

How to prove that $\sum\limits_{i=0}^p (-1)^{p-i} {p \choose i} i^j$ is $0$ for $j < p$ and $p!$ for $j = p$

Let $p \in \mathbf{N}$. I don't know how to prove that $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^j=0 \textrm{ for } j \in \{0,\ldots,p-1\},$$ and $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^p=p!$$ ...
1
vote
0answers
189 views

Interdependent constraints combination problem

I am trying to solve the following combination problem. You have 4 knobs or levers that have maximum values, such as 0-20, 0-30, 0-50 and 0-100. Their total values must equal an amount, say 47. Their ...
4
votes
2answers
584 views

How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $?

This sum is difficult. How can I compute it, without using calculus? $$\sum_{k = 1}^n \frac1{k + 1}\binom{n}{k}$$ If someone can explain some technique to do it, I'd appreciate it. Or advice using ...
4
votes
1answer
252 views

Proving this identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$ using lattice paths

How can I prove the identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$? I have to prove it using lattice paths, it should be related to Catalan numbers The $n$th ...
2
votes
1answer
1k views

Proving that $n \choose k$ is an integer [duplicate]

Possible Duplicate: Proof that a Combination is an integer I can't think how to prove that ${n\choose k} \in\mathbb{Z}$. I've played with it for a while, using the factorial definition for ...
5
votes
2answers
148 views

An identity on the number of trees

Let $T_n$ be the number of labelled trees on $n$ vertices, then $$ T_n=\sum_kk\binom{n-2}{k-1}T_kT_{n-k} \tag{1}$$ Using this question, I was able to prove that $$ T_n= \frac{n}{2} \ ...
9
votes
2answers
330 views

How can I prove the identity $2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}$?

How can I prove the identity $$2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}?$$ I know that the number of trees on $n$ vertices is $n^{n-2}$, and that a tree with $n$ vertices has $n-1$ ...
7
votes
4answers
583 views

Why does this expected value simplify as shown?

I was reading about the german tank problem and they say that in a sample of size $k$, from a population of integers from $1,\ldots,N$ the probability that the sample maximum equals $m$ is: ...
6
votes
3answers
1k views

Inductive proof for the Binomial Theorem for rising factorials

I want to proove the following equality containing rising factorials $$(x+y)^\overline{n}\overset{(*)}{=}\sum_{k=0}^n\binom{n}{k}x^\overline{k}y^\overline{n-k}.$$ For $n=1$ this equality is ...
9
votes
1answer
710 views

Sum of product of binomial coefficient

Is the following true? $$\sum_{x_1+x_2+...+x_n=n}\ \ \, \prod_{i=1}^{n}{k_i\choose x_i}={\sum_{i=1}^{n}k_i \choose n} .$$ I tried to use the multinomial theorem, but it doesn't seem applicable.
1
vote
2answers
322 views

How to prove the binomial coefficient identity $\binom{n}{c}+ \binom{n}{c+1}= \binom{n+1}{c+1}$ by induction?

$$\binom{n}{c}+ \binom{n}{c+1}= \binom{n+1}{c+1}$$ How can I prove using induction for all values of $n$ and $c$? I have no idea how to start it. Please help!
9
votes
2answers
4k views

Approximating the logarithm of the binomial coefficient

We know that by using Stirling approximation: $\log n! \approx n \log n$ So how to approximate $\log {m \choose n}$?
10
votes
2answers
1k views

Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?

I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$ $O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?
1
vote
2answers
726 views

A Combinations Problem Involving Days Of the Week

I'am reading through Engineering Math by Ken Stroud/Dexter Booth and in page 274 under Combinations. Here's the situation. Assuming that you have a part-time Job in the weekday evenings where you ...
22
votes
6answers
1k views

Proofs of $\lim\limits_{n \to \infty} \left(H_n - 2^{-n} \sum\limits_{k=1}^n \binom{n}{k} H_k\right) = \log 2$

Let $H_n$ denote the $n$th harmonic number; i.e., $H_n = \sum\limits_{i=1}^n \frac{1}{i}$. I've got a couple of proofs of the following limiting expression, which I don't think is that well-known: ...
0
votes
1answer
156 views

Is my argument wrong? (A combinatorial exercise)

How many ways are there to arrange $m$ distinct flags on a row of $r$ flagpoles? The order of the flags on the flagpoles (from top to bottom) matters. My argument is: I have $mr$ points and I have to ...
1
vote
1answer
83 views

A “fast” approach to compute $\sum_{i=0}^{n} \binom{19}{i} \times \binom{7}{n-i}$ [duplicate]

Possible Duplicate: How to find a closed formula for the given summation I am looking for a fast/best approach to compute $$\sum_{i=0}^{n} \binom{19}{i} \times \binom{7}{n-i}$$ For ...
11
votes
3answers
205 views

Calculating $\sum_{0\le k\le n/2} \binom{n-k}{k}$

I would like to evaluate: $$\sum_{0\le k\le n/2}\binom{n-k}{k}$$ Any idea?
19
votes
2answers
827 views

Combinatorial proof of $\binom{3n}{n} \frac{2}{3n-1}$ as the answer to a coin-flipping problem

In the recent question "What's the probability that a sequence of coin flips never has twice as many heads as tails?" I argue in my answer that the number of ways $S(n)$ to obtain twice as many heads ...
1
vote
1answer
469 views

Lucas' Theorem and Pascal's Triangle

I have a general question about Lucas' Theorem. Lucas' Theorem says the following: Theorem (Lucas' Theorem) Let $p$ be a prime number. Write $n$ and $k$ in base $p$: $n = a_0 + a_{1}+a_{2}p^{2} + ...
5
votes
2answers
195 views

On a property of the binomial coefficient

Let $n$ be a positive integer and $p$ a prime, how can I prove that the highest power of $p$ that divides $\binom{2n}{n}$ is exactly the number of $k\geq1$ such that $\lfloor 2n/p^k\rfloor$ is odd?
3
votes
2answers
124 views

A combinatorial exercise

Suppose to have a jar containing 100 coins. I want to count the possibile configuration with pennies, nickels, dimes, quarters and half-dollars. This is what I have done, but I realized that it's ...
1
vote
2answers
166 views

Expanding Equation with Binomial Theorem

How do I expand this equation: $(1+t+t^2)^5$ I formed the equation into a binomial equation this way: $(1+t+t^2)^5=\sum \binom{5}{r_1}\binom{5-r_1}{r_2}t^{r_2}t^{2r_1}$ But I cannot remember how to ...
11
votes
4answers
2k views

Elementary central binomial coefficient estimates

How to prove that $\quad\displaystyle\frac{4^{n}}{\sqrt{4n}}<\binom{2n}{n}<\frac{4^{n}}{\sqrt{3n+1}}\quad$ for all $n$ > 1 ? Does anyone know any better elementary estimates?
2
votes
2answers
454 views

Divisibility using binomial coefficients

I have to prove that $6 \mid n^3 + 5n$ in a number of ways. One that I've been finding impossible is binomial coefficients. This is the problem statment: Use an expression in terms of binomial ...
15
votes
2answers
1k views

Combinatorial interpretation of Binomial Inversion

It is known that if $f_n = \sum\limits_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is ...
0
votes
1answer
543 views

How many routes are there through from top left corner to top right in a 20x20 grid? Binomial Coefficent explanation [duplicate]

Possible Duplicate: Counting number of moves on a grid I'm trying to solve this computer programming problem on Project Euler: http://projecteuler.net/index.php?section=problems&id=15 ...
8
votes
1answer
332 views

Construction of generating function from identity

I am trying to solve identity involving binomials and fibbonaci numbers by using generating functions: $$\sum_{k=0}^n{n \choose k}{n+k\choose k}f_{k+1}=\sum_{k=0}^n{n \choose k}{n+k\choose ...
1
vote
1answer
108 views

Combination Problem with a Variable

I have the following problem: $_xC_6$ = $_xC_4$ I expand both sides to: $$\frac{x!}{[(x-6)!]6!} = \frac{x!}{[(x-4)]!4!}$$ Next I multiply both sides by the denominator of the right-hand ...
2
votes
2answers
798 views

Combinatorial proof of binomial coefficient summation

While doing some Computer Science problems, I found one which I thought could be solvable using combinatorics instead of programming: Given two positive integers $n$ and $k$, in how many ways do $k$ ...
6
votes
1answer
814 views

Relation between different ways of accessing bernoulli numbers with matrices

First Variant: Bernoulli numbers can easily be expressed by linear algebra equations. For example just using the recursion formula $$\sum_{k=0}^{n-1}{n\choose k}B_k=0$$ which is equation (34) from ...
4
votes
2answers
256 views

Binomial division

Looks very easy, but I can't make it: $s \geq 2$ and $w \geq 2$ are prime numbers. $k$ is a natural number and $k \leq \min \{s,w \}$ Show that $\binom{s+w}{k}-\binom{w}{k} - \binom{s}{k}$ can be ...
16
votes
7answers
3k views

Prime dividing the binomial coefficients

It is quite easy to show that for every prime $p$ and $0<i<p$ we have that $p$ divides the binomial coefficient $\large p\choose i$; one simply notes that in $\large \frac{p!}{i!(p-i)!}$ the ...
6
votes
3answers
342 views

Yet another sum involving binomial coefficients

Let $k,p$ be positive integers. Is there a closed form for the sums $$\sum_{i=0}^{p} \binom{k}{i} \binom{k+p-i}{p-i}\text{, or}$$ $$\sum_{i=0}^{p} \binom{k-1}{i} \binom{k+p-i}{p-i}\text{?}$$ ...
4
votes
4answers
196 views

Expansion concerning the binomial theorem

The question goes: Expand $(1-2x)^{1/2}-(1-3x)^{2/3}$ as far as the 4th term. Ans: $x + x^2/2 + 5x^3/6 + 41x^4/24$ How should I do it?
1
vote
1answer
45 views

Distribution of number of special elements chosen: m choices of n items with k special items

Suppose I a set with $n$ items, $k$ of which have a certain property($k\leq n$), and I choose $m$ items randomly from that set($m\leq n$), what is the distribution of the number of chosen items having ...
5
votes
3answers
364 views

What does the notation $\binom{n}{i}$ mean?

What do the parentheses next to the summation involving the binomial coefficients mean? Like this: $$\sum _{i=0}^{n} \binom{n}{i}a^{(n-i)}b^i=\left(a+b\right)^n $$
2
votes
2answers
161 views

Convergence of $\sum _{i=0}^{n}\min\left[\binom{n}{i}\ q^{i} (1-q)^{n-i} ,\binom{n}{i}\ p^{i} (1-p)^{n-i} \right]$

I have a series $E_n$ and would like to prove that $E_n$ (composed of two binomials) converges to zero, where $0 \lt p, q \lt 1$: $$ E_{n} =\frac{1}{2} \sum _{i=0}^{n}\min\left[\binom{n}{i}\ q^{i} ...
3
votes
1answer
197 views

Quick way of showing an $n\times n$ Jordan block associated to $1$ is similar to the companion matrix of $(x-1)^n$

Is there a quick, clean way of proving that the $n\times n$ Jordan block with $1$'s on the diagonal and the Frobenius companion matrix corresponding to the polynomial $(x-1)^n$ are similar matrices? ...
1
vote
1answer
84 views

Looking for a combinatorical explanation

Let $X_n$ be the set of all word of the length $2 n$ over the alphabet $\{A,B\}$ which contain as many A's as B's. The amount of elements of $X_n$ is $\displaystyle \binom{2n}{n}$, but why? I ...
3
votes
2answers
103 views

Digit in the ten's place of an expression

What is the digit in the ten's place of $23^{41}* 25^{40}$ ? How do you calculate this? The usual method for this kind of problem is using the Binomial theorem, but I couldn't solve it.
11
votes
4answers
817 views

Combinatorial proof that binomial coefficients are given by alternating sums of squares?

A student recently asked whether there was a combinatorial proof of the following identity: $\begin{equation*} \sum^n_{k=1}(-1)^{n-k}k^2 = {n+1 \choose 2}. \end{equation*}$ I was in a rush and ...
1
vote
1answer
285 views

Two generating functions involving binomial coefficients

Are any of you familiar with the closed form solutions for $\sum_{k=0}^{n} k C(n,k) x^k$ and $\sum_{k=0}^{n} k^2 C(n,k) x^k$ where $0 < x < 1$? Thanks!
9
votes
4answers
224 views

Bounding ${(2d-1)n-1\choose n-1}$

Claim: ${3n-1\choose n-1}\le 6.25^n$. Why? Can the proof be extended to obtain a bound on ${(2d-1)n-1\choose n-1}$, with the bound being $f(d)^n$ for some function $f$? (These numbers ...
2
votes
3answers
97 views

Further simplify this $\sum \limits_{i=1}^{k}{{k \choose i} \cdot 12^i \cdot 2^i}$

Could we further simplify this: $$ \sum_{i=1}^{k}{{k \choose i} \cdot 12^i \cdot 2^i}$$ or, at least, find a close upper bound?
4
votes
3answers
396 views

Evaluate $\displaystyle \sum_{k=1}^n \binom{2k}{2}$ combinatorially

How to evaluate the expression $$\displaystyle \sum_{k=1}^n \binom{2k}{2}$$ using a combinatorial argument? Sorry I have little clue so cannot provide any working for it. Not homework. Related to ...
14
votes
5answers
933 views

Evaluate $\sum\limits_{k=1}^n k^2$ and $\sum\limits_{k=1}^n k(k+1)$ combinatorially

$$\text{Evaluate } \sum_{k=1}^n k^2 \text{ and } \sum_{k=1}^{n}k(k+1) \text{ combinatorially.}$$ For the first one, I was able to express $k^2$ in terms of the binomial coefficients by ...
10
votes
6answers
573 views

Evaluate $ \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{2k}+\cdots$ [duplicate]

I need to evaluate, for a certain worded question: If n is even $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots\binom{n}{n}$$ If n is odd ...