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)

3
votes
1answer
530 views

Number of possible triangle for the given triangle.

An equilateral triangle has n equally spaced dots on each side. How many triangles can be formed (of any size)? Analysis If there are n dots on each side then total no of dots =n(n+1)/2 Number of ...
2
votes
1answer
167 views

Proving $(1+i)^{2n}=2^n\cos {\pi n \over 2}$ using binomial expansion

Use the binomial expansion of$(1+i)^{2n}$ to prove that $$\binom{2n}{0}-\binom{2n}{2}+\binom{2n}{4}-\binom{2n}{6}+...+(-1)^n\binom{2n}{2n}=2^n\cos {\pi n \over 2}, n\in \mathbb{Z^+}$$ I've been ...
0
votes
1answer
469 views

Counting the number of combinations when some values are fixed

A reading list for a humanities course consists of 10 books; of which 4 are biographies and the rest are novels. Each student is required to read a selection of 4 books from the list including ...
7
votes
2answers
220 views

About one generating function

Initially, I have the following problem: find $$\sum_{k=0}^{n+1}(−1)^{n−k}4^k{n+k+1 \choose 2k}.$$ I thought, if I found the function $g_n(x) = \sum_{k=0}^{n}{n+k \choose 2k}x^k$, the answer would be ...
16
votes
8answers
2k views

Proving $\sum\limits_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$

Show that $$\sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$$ So for odd $n$ we have an even number of terms. So $\binom{n}{k} = \binom{n}{n-k}$ which have opposite signs. Thus the sum is $0$. For even $n$ ...
4
votes
3answers
475 views

Alternating sign Vandermonde convolution

The well-known Vandermonde convolution gives us the closed form $\sum_{k=0}^n {r\choose k}{s\choose n-k} = {r+s \choose n}$. For the case $r=s$, it is also known that $\sum_{k=0}^n (-1)^k {r \choose ...
3
votes
1answer
1k views

Counting the number of directed graphs with $N$ vertices and $E$ edges?

Does any body who has good back ground in graph theory tells me that how many possible directed graphs will be there with $N$ vertices and $E$ edges. I need all the possible combinations even even ...
16
votes
2answers
344 views

On computing: $ \gcd \left({2n \choose 1}, {2n \choose 3},\cdots, {2n \choose 2n-1}\right)$

I would like to calculate $$ d=\gcd \left({2n \choose 1}, {2n \choose 3},\cdots, {2n \choose 2n-1}\right) $$ We have: $$ \sum_{k=0}^{n-1}{2n \choose 2k+1}=2^{2n-1} $$ $$ d=2^k, 0\leq k\leq2n-1 $$ ...
8
votes
4answers
467 views

Inequality with central binomial coefficients

For every even positive number $N$ we have: $$ {2N \choose N } < 2^N {N \choose N/2 } < 2 {2N \choose N } $$ (Furthermore, $\frac{2^N {N \choose N/2 }}{{2N \choose N }} \to \sqrt{2} $ for ...
6
votes
2answers
295 views

Is there a binomial identity for this expression $\frac{\binom{r}{k}}{\binom{n}{k}}$?

What I'm trying to prove is this summation: $$\sum_{i=0}^{k} \dfrac{\dbinom{r}{i} \cdot \dbinom{n - r}{k - i}}{\dbinom{n}{k}} \cdot i = \dfrac{r}{n} \cdot k$$ I used induction on $k$ as follows: ...
3
votes
2answers
343 views

Number of nonnegative integral solutions of $x_1 + x_2 + \cdots + x_k = n$

To find all solutions greater than or equal to $1$ of a linear equation in the form $$x_1+x_2+x_3+\cdots+x_k=n ,$$ the number of them is $\binom{n-1}{k-1}$. If I need all solutions to be greater or ...
3
votes
4answers
13k views

Probability of winning a prize in a raffle

My work is having it's annual Christmas raffle today. 1600 tickets have been sold, and there are 40 prizes to win. I have bought ten tickets. What are the odds I will win a prize? While an initial ...
2
votes
2answers
5k views

How many solutions are there to the equation $x + y + z + w = 17$?

How many solutions are there to the equation $x + y + z + w = 17$? I don't know if I'm doing this right, but I guessed that the solution would be $\binom{20}{3}$, which equals $1140$. Am I doing ...
4
votes
3answers
140 views

Property of a polynomial $f\in\mathbb{Q}[X]$ such that $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$?

We can always view $\binom{x}{k}$ as a polynomial in $x$ of degree $k$. With this in mind, why is it so that a polynomial $f\in\mathbb{Q}[x]$ is such that $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$ ...
2
votes
1answer
88 views

Is there a simple expression for this generating function that is almost like the binomial formula?

This is a curiosity I when looking at the binomial theorem. Say you have an ordinary generating function $\displaystyle\sum_{n,m\geq 0}\binom{n}{m}x^ny^m$. This looks kind of like ...
2
votes
1answer
486 views

Combinatorial interpretation for the identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?

A known identity of binomial coefficients is that $$ \sum_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}. $$ Is there a combinatorial proof/explanation of why it holds? Thanks.
1
vote
3answers
482 views

Binomial inequality

Show that we have: $$ \binom{n}{s}\leq n^n $$
4
votes
3answers
237 views

Combinatorial proof of $\binom{n}{k} = \binom{n}{n-k}$

How do I prove this combinatorially? $$\displaystyle \binom{n}{k} = \binom{n}{n-k}$$
0
votes
3answers
134 views

Evaluating $\binom{100}{i}a^i(1-a)^{(100-i)}$ in GMP-GNU [closed]

I want to calculate $\binom{100}{i}a^i(1-a)^{(100-i)}$ for different $i$ with $a=0.001$ using GMP-GNU. How can this be done?
3
votes
1answer
500 views

Combinatorial Argument

Can you give a Combinatorial argument that $$\binom{3n}{3}=3\binom{n}{3}+(3)(2)\binom{n}{2}\binom{n}{1}+\binom{n}{1}\binom{n}{1}\binom{n}{1}?$$
4
votes
2answers
232 views

Proof of $(2n)!/(n!)^2\le2^{2n}$ by mathematical induction?

How do I approach this problem using mathematical induction? $$\frac{(2n)!}{(n!)^2} \leq 2^{2n}$$
1
vote
1answer
137 views

Algebra on $\binom{k+1}{i} = \binom{k+1}{0} + \binom{k+1}{1} + \cdots + \binom{k+1}{k} + \binom{k+1}{k+1}$ [duplicate]

Possible Duplicate: Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$ I am trying to prove $\sum \limits_{i=0}^n \binom{n}{i} = 2^n$ by induction. I've been all over the net ...
3
votes
3answers
1k views

How can I prove that the binomial coefficient ${n \choose k}$ is monotonically nondecreasing for $n \ge k$?

I want to prove that the binomial coefficient ${n \choose k}$ for $n \ge k$ is a monotonically nondecreasing sequence for a fixed $k$. How do I do this?
2
votes
1answer
167 views

Cardinality of set containing true order relations from a power set

This question is from the book Introduction to Topology and Modern Analysis by GF Simmons, Problem 3(d) at end of Section 1. I'll paraphrase the question here. Suppose $U$ is a containing $n$ ...
3
votes
3answers
342 views

Closed form for a sum involving binomial coefficient [duplicate]

Possible Duplicate: How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $? How to derive the following equality? $$\sum_{j=0}^n \binom{n}{j} \frac1{j+1} = ...
7
votes
3answers
508 views

Hard elementary combinatorics problem

How does one compute (without brute force) the smallest integer $n$ such that $\binom{2n}{1}(-3)^0 + \binom{2n}{3}(-3)^1 + \binom{2n}{5}(-3)^2 + \cdots + \binom{2n}{2n-1}(-3)^{(n-1)} = 0$?
26
votes
7answers
1k views

Prove: $\binom{n}{k}^{-1}=(n+1)\int_{0}^{1}x^{k}(1-x)^{n-k}dx$ for $0 \leq k \leq n$

I would like your help with proving that for every $0 \leq k \leq n$, $$\binom{n}{k}^{-1}=(n+1)\int_{0}^{1}x^{k}(1-x)^{n-k}dx . $$ I tried to integration by parts and to get a pattern or to ...
2
votes
3answers
7k views

why is ${n+1\choose k} = {n\choose k} + {n\choose k-1}$? [duplicate]

Possible Duplicate: Proving ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$ can someone explain to me the proof of $${n+1\choose k} = {n\choose k} + ...
1
vote
1answer
123 views

The curve of expansion $(a+b)^n$

I have read very interesting article about binomial form $(a+b)^n$,article says that if we expand $(a+b)^n$ and arrange it,then we can see very beautiful shape,in particular,if we make $n$ bigger ...
3
votes
0answers
134 views

Defining a signed involution

We define the displacement of $\pi$ as $\mathrm{disp}(\pi)=\sum_{i=1}^n|\pi(i)-i|$. I know that it's even. Could you help me to find a good signed involution of the set of permutation with ...
9
votes
2answers
467 views

Derive a closed form for a sum with inverse binomial coefficients

First off, I would like to apologize again for the integral I posted several days ago involving $\zeta(5)$. I was careless and did not examine the decimals out far enough. With that said, I would ...
6
votes
2answers
14k views

Negative Exponents in Binomial Theorem

I'm looking at extensions of the binomial formula to negative powers. I've figured out how to do $n \choose k$ when $n < 0 $ and $k \geq 0$: $${n \choose k} = (-1)^k {-n + k - 1 \choose k}$$ So ...
4
votes
2answers
110 views

Binomials in associative algebras

Given any associative algebra $A$ over a field of characteristic zero, $x\in A$ and $k\in \mathbb Z_+$, set $\binom{x}{k} = \frac{x(x-1)\cdots(x-k+1)}{k!}$. It is not hard to see that is is still in ...
7
votes
5answers
367 views

Are there surprisingly identical binomial coefficients?

Suppose $\binom{n}{k}=\binom{n'}{k'}$ with $k \geq 2$, $k' \geq 2$, $n \geq 2k$ and $n' \geq 2k'$. Does it follow that $n=n'$ and $k=k'$? EDIT: Yup, ...
7
votes
1answer
310 views

Bounds on $\sum_{k=0}^{m} \binom{n}{k}x^k$ and $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}, m<n$

I've read this interesting article by Woersch (1994) dealing with approximation of binomial coefficients (rows of Pascal's triangle). I'm just wondering if similar bounds exist for partial binomial ...
5
votes
1answer
268 views

alternative proof to induction, binomial sum identity

$\displaystyle \sum_{q=0}^{k} \begin{pmatrix}n-1+q\\ n-1 \end{pmatrix} = \begin{pmatrix}n+k\\n \end{pmatrix} $ induction $\begin{pmatrix}n \\ k \end{pmatrix} := \frac{n!}{(n-k)!k!}$ ...
3
votes
5answers
585 views

Binomial theorem application

I have a question about the bonomial theorem, and in specifically, a question that I want help on. I have worked out the answer, but by manually expanding each and every alternative. However, I ...
5
votes
2answers
4k views

A fair coin is tossed $n$ times by two people. What is the probability that they get same number of heads?

Say we have Tom and John, each tosses a fair coin $n$ times. What is the probability that they get same number of heads? I tried to do it this way: individually, the probability of getting $k$ ...
0
votes
1answer
794 views

binomial calculation method

I want solve this probability: For $p= 0.4$ $q=0.8$ $n= 20$ $1-P(5<x<11)$ = $1-\sum_{k=6}^{10} \binom{20}{k}(0.4)^k(0.6)^{20-k}. Wolfram Alpha -> = 0,2531$ Is calculation method ...
6
votes
1answer
1k views

Using the Taylor expansion for ${(1+x)}^{-1/2}$, evaluate $\sum_{n=0}^\infty \binom{2n}{n} a^n$

Using the Taylor expansion for $${(1+x)}^{-1/2}$$ we have $${(1+x)}^{-1/2}= \sum_{n=0}^\infty \binom{-1/2}{n} (x^n)$$ for $|x|<1$. But if $|a| <1$, how can we use the above fact to find ...
4
votes
1answer
663 views

Why is $n\choose k$ periodic modulo $p$ with period $p^e$?

Given some integer $k$, define the sequence $a_n={n\choose k}$. Claim: $a_n$ is periodic modulo a prime $p$ with the period being the least power $p^e$ of $p$ such that $k<p^e$. In other words, ...
6
votes
5answers
2k views

How to show that this binomial sum satisfies the Fibonacci relation?

The binomial sum $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$ satisfies the Fibonacci relation. I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any ...
3
votes
3answers
191 views

Proofs from the BOOK: Bertrand's postulate: $\binom{2m+1}{m}\leq 2^{2m}$

I have a very hard proof from "Proofs from the BOOK". It's the section about Bertrand's postulate, page 8: It's about the part, where the author says: $$\binom{2m+1}{m}\leq 2^{2m}$$ because ...
54
votes
2answers
3k views

Combinatorial proof that $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ when $n$ is even

In my answer here I prove, using generating functions, a statement equivalent to $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$ when $n$ is even. (Clearly the sum is ...
5
votes
1answer
394 views

How can I express $\sum_{k=0}^n\binom{-1/2}{k}(-1)^k\binom{-1/2}{n-k}$ without using summations or minus signs?

How can I express $$\sum_{k=0}^n\binom{-1/2}{k}(-1)^k\binom{-1/2}{n-k}$$ without using summations or minus signs?
0
votes
1answer
454 views

Finding number of intersections between line A and B

I was recently working through the IB HL textbook and I came across two interesting problems. Exercise 8E Question 18. Line A contains 10 points and line B contains 7 points. If all points on line ...
2
votes
2answers
184 views

On a formula that relates 2-regular graphs on $n$ vertices and permutations of $n$ elements with no fixed points or cycles of length 2

Let $g_n=$ number of 2-regular graphs on $n$ vertices Let $c_n=$ permutations of $n$ with no fixed points or cycles of length 2 By a computation with the exponential generating function I think that ...
2
votes
1answer
228 views

Evaluating an expression using snake oil and convolutions gives different answers

I have to evaluate this expression $\sum \limits_{k=0}^n(-1)^k\binom{n}{k}\binom{m+n-k}{n-k}$ using snake oil and convolutions. The problem is that I got two different results, could you help me to ...
21
votes
6answers
6k views

prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer

Prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer. For clarity: the denominator is the only part being squared. My thought process: The numerator is the product of the first n even ...
2
votes
1answer
310 views

Evaluating an expression using snake oil

I have to evaluate this expression: $\sum_k\binom{n}{k}\binom{2k}{k}(-2)^{-k}$, (In the original question we had $\sum_k\binom{n}{k}\binom{2k}{k}(-2)^{k}$) this is what I have done: ...