Editing Binomial coefficient (section)

== Definition and interpretations ==
{| class="wikitable" style="float:right;line-spacing:0.8;margin-left:1ex;"
|-
! {{diagonal split header|''n''|''k''}} !! 0 !! 1 !! 2 !! 3 !! 4 !! ⋯
|-
! 0
| 1 || {{silverC|0}} || {{silverC|0}} || {{silverC|0}} || {{silverC|0}} || ⋯
|-
! 1
| 1 || 1 || {{silverC|0}} || {{silverC|0}} || {{silverC|0}} || ⋯
|-
! 2
| 1 || 2 || 1 || {{silverC|0}} || {{silverC|0}} || ⋯
|-
! 3
| 1 || 3 || 3 || 1 || {{silverC|0}} || ⋯
|-
! 4
| 1 || 4 || 6 || 4 || 1 || ⋯
|-
! ⋮
| ⋮ || ⋮ || ⋮ || ⋮ || ⋮ || ⋱
|-
| colspan="7"|The first few binomial coefficients<br />on a left-aligned Pascal's triangle
|}

For [[natural number]]s (taken to include 0) {{mvar|n}} and {{mvar|k}}, the binomial coefficient <math>\tbinom nk</math> can be defined as the [[coefficient]] of the [[monomial]] {{math|''X''<sup>''k''</sup>}} in the expansion of {{math|(1 + ''X'')<sup>''n''</sup>}}. The same coefficient also occurs (if {{math|''k'' ≤ ''n''}}) in the [[binomial formula]]
{{NumBlk2|:|<math>(x+y)^n=\sum_{k=0}^n\binom nk x^ky^{n-k}</math>|∗}}
(valid for any elements {{mvar|x}}, {{mvar|y}} of a [[commutative ring]]),
which explains the name "binomial coefficient".

Another occurrence of this number is in combinatorics, where it gives the number of ways, disregarding order, that {{mvar|k}} objects can be chosen from among {{mvar|n}} objects; more formally, the number of {{mvar|k}}-element subsets (or {{mvar|k}}-[[combination]]s) of an {{mvar|n}}-element set. This number can be seen as equal to that of the first definition, independently of any of the formulas below to compute it: if in each of the {{mvar|n}} factors of the power {{math|(1 + ''X'')<sup>''n''</sup>}} one temporarily labels the term {{mvar|X}} with an index {{mvar|i}} (running from {{math|1}} to {{mvar|n}}), then each subset of {{mvar|k}} indices gives after expansion a contribution {{math|''X''<sup>''k''</sup>}}, and the coefficient of that monomial in the result will be the number of such subsets. This shows in particular that <math>\tbinom nk</math> is a natural number for any natural numbers {{mvar|n}} and {{mvar|k}}. There are many other combinatorial interpretations of binomial coefficients (counting problems for which the answer is given by a binomial coefficient expression), for instance the number of words formed of {{mvar|n}} [[bit]]s (digits 0 or 1) whose sum is {{mvar|k}} is given by <math>\tbinom nk</math>, while the number of ways to write <math>k = a_1 + a_2 + \cdots + a_n</math> where every {{math|''a''<sub>''i''</sub>}} is a nonnegative integer is given by {{tmath|1= \tbinom{n+k-1}{n-1} }}. Most of these interpretations can be shown to be equivalent to counting {{mvar|k}}-combinations.