What is Binomial coefficients: Definition and 43 Discussions

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written

(

n
k

)

.

{\displaystyle {\tbinom {n}{k}}.}
It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n, and is given by the formula

(

n
k

)

=

n
!

k
!
(
n

k
)
!

.

{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}
For example, the fourth power of 1 + x is

(
1
+
x

)

4

=

(

4
0

)

x

0

+

(

4
1

)

x

1

+

(

4
2

)

x

2

+

(

4
3

)

x

3

+

(

4
4

)

x

4

=
1
+
4
x
+
6

x

2

+
4

x

3

+

x

4

,

{\displaystyle {\begin{aligned}(1+x)^{4}&={\tbinom {4}{0}}x^{0}+{\tbinom {4}{1}}x^{1}+{\tbinom {4}{2}}x^{2}+{\tbinom {4}{3}}x^{3}+{\tbinom {4}{4}}x^{4}\\&=1+4x+6x^{2}+4x^{3}+x^{4},\end{aligned}}}
and the binomial coefficient

(

4
2

)

=

4
!

2
!
2
!

=
6

{\displaystyle {\tbinom {4}{2}}={\tfrac {4!}{2!2!}}=6}
is the coefficient of the x2 term.
Arranging the numbers

(

n
0

)

,

(

n
1

)

,

,

(

n
n

)

{\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},\ldots ,{\tbinom {n}{n}}}
in successive rows for

n
=
0
,
1
,
2
,

{\displaystyle n=0,1,2,\ldots }
gives a triangular array called Pascal's triangle, satisfying the recurrence relation

(

n
k

)

=

(

n

1

k

)

+

(

n

1

k

1

)

.

{\displaystyle {\binom {n}{k}}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}.}
The binomial coefficients occur in many areas of mathematics, and especially in combinatorics. The symbol

(

n
k

)

{\displaystyle {\tbinom {n}{k}}}
is usually read as "n choose k" because there are

(

n
k

)

{\displaystyle {\tbinom {n}{k}}}
ways to choose an (unordered) subset of k elements from a fixed set of n elements. For example, there are

(

4
2

)

=
6

{\displaystyle {\tbinom {4}{2}}=6}
ways to choose 2 elements from

{
1
,
2
,
3
,
4
}
,

{\displaystyle \{1,2,3,4\},}
namely

{
1
,
2
}

,

{
1
,
3
}

,

{
1
,
4
}

,

{
2
,
3
}

,

{
2
,
4
}

,

{\displaystyle \{1,2\}{\text{, }}\{1,3\}{\text{, }}\{1,4\}{\text{, }}\{2,3\}{\text{, }}\{2,4\}{\text{,}}}
and

{
3
,
4
}
.

{\displaystyle \{3,4\}.}

The binomial coefficients can be generalized to

(

z
k

)

{\displaystyle {\tbinom {z}{k}}}
for any complex number z and integer k ≥ 0, and many of their properties continue to hold in this more general form.

View More On Wikipedia.org
1. B How to interpret Pascal's Triangle for negative numbers?

This answer shows an extended version of Pascal's Triangle that works for negative numbers too. In This video, Sal shows how to interpret the members of Pascal's Triangle as the sum of all the possible paths to get to that member. Is there any way we can use this same 'sum of all the possible...
2. Maple Help with a Maple Program: Binomial Coefficients

Please see attached image. I'm not sure why I'm getting this error because this is the format I have used to write programs in Maple before. Any ideas? I'm new to this so not sure how to independently trouble shoot or problem solve this, Thanks!
3. I Sum of Binomial Expansion | Spivak Chapter 2, Excercise 3 part d

Hello, I am working through Spivak for self study and sharpening my math skills. I have become stuck on an exercise. What I need to show is the following: $$(a + b) \sum_{j = 0}^{n} \binom nj a^{n-j}b^{j} = \sum_{j = 0}^{n + 1} \binom{n+1}{j} a^{n-j + 1}b^{j}$$ My attempt, starting from...
4. B Understanding the Evolution of Binomial Coefficient Notation: Old vs. New

I am learning binomial theorem now on my long journey to calculus. I noticed that in older textbooks, the binomial coefficient looks like C(n on top,k on bottom) I don’t think that I can display it here and in newer ones,they look like ##\binom{n}{k}## is the old notation outdated?or this is...
5. Using binomial coefficients to find sum of roots

Homework Statement >Find the sum of the roots, real and non-real, of the equation x^{2001}+\left(\frac 12-x\right)^{2001}=0, given that there are no multiple roots. While trying to solve the above problem (AIME 2001, Problem 3), I came across three solutions on...
6. Generating functions, binomial coefficients

Homework Statement a) I have to find and expression for sequence of $b_n$ in terms of generating functions of the sequence of $a_n$ $$b_n = (-1)^{n}(n+1)a_0 +(-1)^{n-1}n a_1+...+(-1)2a_{n-1}+a_n$$ with $$a_n = a_{n-1} +8a_{n-2} -12a_{n-3} +25(-3)^{n-2} + 32n^2 -64$$ b) I have to use the...
7. MHB Prove an identity with binomial coefficients

Prove, that $\sum_{j=1}^{2n-1}\frac{(-1)^{j-1}j}{{2n \choose j }} = \frac{n}{n+1}$ i have tried with proof by induction, but it is very difficult to use this technique. I should be very glad to see any approach, that can crack this nut.
8. I Need closed form for a Binomial series

Hello I was solving a problem in probability. Here is the statement. Seven terminals in an on-line system are attached to a communications line to the central computer. Exactly four of these terminals are ready to transmit a message. Assume that each terminal is equally likely to be in the ready...
9. Help with basic binomial coefficient

< Mentor Note -- thread moved to HH from the technical math forums, so no HH Template is shown > Hello. I'm currently working my way through Lang's Basic Mathematics and cannot make sense of this question: Show that if n is a positive integer at most equal to m, then {m \choose n}+{m\choose...
10. I Summation for extended binomial coefficients

Is there a way of writing summation(s) to obtain the extended binomial coefficients? i.e., Considering the expansion of (1+x+x^2+x^3+...+x^N)^M can we write expressions (presumably involving summation and/or product notation) for the coefficients (on x^j in the expansion of the above, for each...
11. A Is this product always greater than these sums?

I've been working on a problem for a couple of days now and I wanted to see if anyone here had an idea whether this was already proven or where I could find some guidance. I feel this problem is connected to the multinomial theorem but the multinomial theorem is not really what I need . Perhaps...
12. What is the closed form for the sum of binomial coefficients over any interval?

Is there a way to find the following sum in closed form: ∑K(N,n) , where K(N,n) is the binomial coefficient and the sum can extend over any interval from n=0..N. I.e. not necessarily n=0 to N in which case on can just use the binomial theorem.
13. MHB Sum of binomial coefficients multiplied by k^2

Evaluate \sum\limits_{k=1}^{12} {12\choose{k}}k^2 The answer is 159744.
14. Binomial Distribution for successive events

So I new to probability and need someone to help me out if you could. I wanted to look into the probability of a process being complete if each operation of the process has its own likely hood of success or failure. I know that I should be using a binomial distribution to study the process...
15. Use of binomial theorem in a sum of binomial coefficients?

Homework Statement How to use binomial theorem for finding sums with binomial coefficients? Example: S={n\choose 1}-3{n\choose 3}+9{n\choose 5}-... How to represent this sum using \sum\limits notation (with binomial theorem)? Homework Equations (a+b)^n=\sum\limits_{k=0}^{n}{n\choose...
16. Prove the binomial coefficients are (-1)^n

Homework Statement Show that the binomial coefficients ## \binom {-1}{n}=(-1)^n## Homework Equations ##\binom{n}{k}=\frac{n!}{(n-k)!k!} \\ ## The Attempt at a Solution ##-1!=(-1)\cdot 1! \\ -1!=-1 \\ -2!=(-1)^2 \cdot 2! \\ -n!=(-1)^n \cdot n!\\ \mbox{for n=0} \\...
17. Summation with binomial coefficients question

Homework Statement ##\sum\limits_{r=0}^n\frac{1}{^nC_r}=a##. Then find the value of $$\sum\sum\limits_{0\le i<j\le n}(\frac{i}{^nC_i}+\frac{j}{^nC_j})$$ Homework Equations I have used two equations which I derived myself. This is the first one. The second one is: 3. The Attempt at a...
18. Series with binomial coefficients

Hi all, I have an apparently simple equation. I copy here its Mathematica code: Sum[(p/(1 - p))^s*(q/(1 - q))^s*Binomial[n, s]*(Binomial[m - 1, s]*(p*q*(m + n) + (2*m - 1)*(-p - q + 1))), {s, 0, n}] == Sum[(p/(1 - p))^s*(q/(1 - q))^s*Binomial[n, s]*((-(-p - q + 1))*Binomial[m - 2, s] +...
19. MHB Evaluating a sum involving binomial coefficients

Problem: Evaluate $$\mathop{\sum \sum}_{0\leq i<j\leq n} (-1)^{i-j+1}{n\choose i}{n\choose j}$$ Attempt: I wrote the sum as: $$\sum_{j=1}^{n} \sum_{i=0}^{j-1} (-1)^{i-j+1}{n\choose i}{n\choose j}$$ I am not sure how to proceed from here. I tried writing down a few terms but that doesn't seem...
20. MHB Evaluating an Infinite Sum of Binomial Coefficients

Evaluate $\displaystyle\lower0.5ex{\mathop{\large \sum}_{n=2009}^{\infty}} \dfrac{1}{n \choose 2009}$.
21. Summing up binomial coefficients

Homework Statement The value of ((^n C_0+^nC_3+...) - \frac{1}{2} (^nC_1+^nC_2+^nC_4+^nC_5+...))^2 + \frac{3}{4} (^nC_1-^nC_2+^nC_4-^nC_5...)^2 The Attempt at a Solution I can see that in the left parenthesis, the first bracket contains terms which are multiples of 3 and in the second...
22. Proof by Induction involving Binomial Coefficients

Homework Statement Prove by induction that for any positive integers a, b, and n, (a choose 0)(b choose n) + (a choose 1)(b choose n-1) + ... + (a choose n)(b choose 0) = (a+b choose n) Homework Equations (x choose y) = (x!)/((x-y)!y!) The Attempt at a Solution I am able to do the...
23. MHB Divisibility of Binomial Coefficients

Hi all, I am trying to figure out if there is a pre-existing theorem and proof of whether or not each of the binomial coefficients in a binomial expansion of (a +b)^n are divisible by n, particularly in the case where n is a prime number. Has this already been asked and answered somewhere in...
24. MHB What is the result of the sum of binomial coefficients with alternating signs?

Evaluate sum: $\displaystyle S=\sum_{k=0}^{2n}(-1)^k{2n\choose k}{4n\choose 2k}$
25. MHB A sum involving the central binomial coefficients

Wolfram MathWorld states that $$\sum_{n=1}^{\infty} \frac{1}{n^{3} \binom{2n}{n}} = \frac{ \pi \sqrt{3}}{18} \Big[ \psi_{1} \left(\frac{1}{3} \right) - \psi_{1} \left(\frac{2}{3} \right) \Big]- \frac{4}{3} \zeta(3)$$ where $\psi_{1}(x)$ is the trigamma function. But I can't get my answer in...
26. Interpretation for identity with binomial coefficients

I am looking for a counting interpretation to make the following identity evident: \sum_{k=0}^{n-j}(-1)^k\binom{j-1+k}{j-1}\binom{n}{j+k} = 1 The form of it looks like inclusion-exclusion. The sum is 1, more or less independent of j. So that makes me think it would be something like "how...
27. Expressing the binomial coefficients

Homework Statement Expressing the binomial coefficients in terms of factorials and simplifying algebraically, show that (n over r) = (n-r+1)/r (n over r-1);Homework Equations The Attempt at a Solution I honestly don't even know how to come about this problem...I really need help in this...
28. MHB Sum with Binomial Coefficients

I'm having trouble proving the following identity (I don't even know if it's true): $$\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\binom{n-1}{k-1}$$ $$\forall n,k \in \mathbb{N} : n>k$$ Thank you in advance for any help! Vincent
29. Proof involving binomial coefficients.

Homework Statement Prove that \sum\limits_{k=o}^l {n \choose k}{m \choose l-k} = {n+m \choose l} Hint: Apply binomial theorem to (1+x)^n * (1+x)^m Homework Equations The Attempt at a Solution Using the hint, I started by saying that (1+x)^n * (1+x)^m = (1+x)^(n+m) =...
30. Generating functions and sums with binomial coefficients

Homework Statement Show that the generating function A(x) = \sum_n a_n x^n of a_n = \sum_{k=0}^n {n+k \choose 2k} 2^{n-k} satisfies A(x) = \frac{1-2x}{4x^2-5x+1}Homework Equations The Attempt at a Solution A hint was given to "interchange the sums". After doing that, I don't see how to...
31. Sum of binomial coefficients and cos(kx)

Homework Statement Calculate the following sum: (click to expand)The Attempt at a Solution I tried something with Moivre formula and Newton binomial theorem but no result :redface:, should i continue with these or is there any simpler approach? I just need some hints. Thanks.
32. Divisible binomial coefficients

Homework Statement I need to sum the binomial coefficients that are divisible by a positive integer t, i.e. \sum_{i=0}^{s}\binom{ts}{ti} Is there any way to get rid of the sum sign? Homework Equations Let t be fixed and s go to (positive) infinity (both t and s are positive...
33. Binomial coefficients sum conjecture about exponential

Fix some constant 0<\alpha \leq 1, and denote the floor function by x\mapsto [x]. The conjecture is that there exists a constant \beta > 1 such that \beta^{-n} \sum_{k=0}^{[\alpha\cdot n]} \binom{n}{k} \underset{n\to\infty}{\nrightarrow} 0 Consider this conjecture as a challenge. I don't...
34. Summation of Products of Binomial Coefficients

Homework Statement Find and prove a formula for sum{ (m1 choose r)(m2 choose s)(m3 choose t) } where the sum is over all nonnegative integers r, s, ant t with fixed sum r + s + t = n. Homework Equations The Attempt at a Solution I first attempted to find the number of combinations of r...
35. Binomial Coefficients Identity

Homework Statement Prove that for an integer n greater than or equal to 2, nC1 - 2nC2 + 3nC3 - + ... = 0. (nCm means n choose m) Also, 2x1 nC2 + 3x2 nC3 + 4x3 nC4 +... = n(n-1)2^(n-2) Homework Equations (1+t)^a = 1 + aC1(t) + aC2(t^2) + ... The Attempt at a Solution I don't know...
36. Casio fx-9860G - calculating binomial coefficients and binomial distribution

How to calculate 1) binomial coefficients and 2) binomial distribution on a Casio fx-9860G calculator?
37. Understanding Binomial Coefficients: Solving a Sample Problem

I understand permutations, combinations and such, but I can't seem to make sense of binomial coefficients, or at least the notation. As an example, could someone walk me through the notation for a generic problem.. something like 100 people eligible for an award and the winner can choose 1...
38. Proving Binomial Coefficients for Even n | Combinatorial Argument

Suppose n is even, prove: \sumk=0->n/2, C(n,2k)=2^(n-1)=\sumk=1->n/2, C(n,2k-1) Give a combinatorial argument to prove that: (I've figured out this one...) \sumk=1->n, C(n,k)^2=C(2n,n) For the first problem, I tried to break C(n, 2k) into C(n+1,2k)-C(n, 2k-1), but they didnt seem to work very...
39. Understanding Binomial Coefficients: n Choose r

Hey guys, I've been reading up on binomial coefficients and I have found a brief section on n choose r. I understand vaguely what it actually is, however in my textbook there is a step by step proof of how we show that: ( \stackrel{n}{r} ) = \frac{n!}{r!(n-r)!} I can follow where...
40. Understanding the Simplification of Binomial Coefficients

Here is the problem i am having trouble: Expressing the binomial coefficients in terms of factorials and simplifying algebraically show that (n over r) = (n-2+1)/r (n over r-1) i got that equals ((n-r+1)/r) ((n!)/((r-1)!(n-(r-1))!)) but i am trying to get that to equal n!/r!(n-r)! which...
41. Calculating Sum of Binomial Coefficients in Terms of a and n

Homework Statement If \sum^{n}_{r=0} \frac{1}{^{n}C_{r}} = a, then find the value of \sum^{n}_{r=0} \frac{r}{^{n}C_{r}} in terms of a and n.[/tex] The Attempt at a Solution I tried to write down the terms of both the series, but to no avail. i can't think of...
42. Understanding Binomial Coefficients: Exploring the Formula and Its Applications

k, maybe wrong forum... whatever... Anyway, so i was hoping someone could maybe derive or at least explain binomial coefficients. Like, i know that binomial(n,r)= n!/(n-r)!r! but why? in class the guy was explaining something like, if you're counting, and you're trying to arrange 3 balls into...
43. Binomial coefficients and pascal's triangle

I am working through a mathematics olympiad problem book, and I am asked to prove that n choose r, where n is the row number and r is the term number in the row is equal to that term. Can someone please give me a hint? I have not been able to find ANY proofs on the internet through a basic...