Definition:Binomial Coefficient

From ProofWiki
(Redirected from Definition:N Choose K)
Jump to navigation Jump to search

Definition

Definition 1

Let $n \in \Z_{\ge 0}$ and $k \in \Z$.

Then the binomial coefficient $\dbinom n k$ is defined as:

$\dbinom n k = \begin {cases} \dfrac {n!} {k! \paren {n - k}!} & : 0 \le k \le n \\ & \\ 0 & : \text { otherwise } \end{cases}$

where $n!$ denotes the factorial of $n$.


Definition 2

Let $n \in \Z_{\ge 0}$ and $k \in \Z$.

The number of different ways $k$ objects can be chosen (irrespective of order) from a set of $n$ objects is denoted:

$\dbinom n k$

This number $\dbinom n k$ is known as a binomial coefficient.


Definition 3

Let $n \in \Z_{\ge 0}$ and $k \in \Z$.

Then the binomial coefficient $\dbinom n k$ is defined as the coefficient of the term $a^k b^{n - k}$ in the expansion of $\paren {a + b}^n$.


Definition for Real Numbers

Let $r \in \R, k \in \Z$.

Then $\dbinom r k$ is defined as:

$\dbinom r k = \begin {cases}

\dfrac {r^{\underline k} } {k!} & : k \ge 0 \\ & \\ 0 & : k < 0 \end {cases}$ where $r^{\underline k}$ denotes the falling factorial.


That is, when $k \ge 0$:

$\ds \dbinom r k = \dfrac {r \paren {r - 1} \cdots \paren {r - k + 1} } {k \paren {k - 1} \cdots 1} = \prod_{j \mathop = 1}^k \dfrac {r + 1 - j} j$

It can be seen that this agrees with the definition for integers when $r$ is an integer.


For most applications the integer form is sufficient.


Definition for Complex Numbers

Let $z, w \in \C$.

Then $\dbinom z w$ is defined as:

$\dbinom z w := \ds \lim_{\zeta \mathop \to z} \lim_{\omega \mathop \to w} \dfrac {\map \Gamma {\zeta + 1} } {\map \Gamma {\omega + 1} \map \Gamma {\zeta - \omega + 1} }$

where $\Gamma$ denotes the Gamma function.


When $z$ is a negative integer and $w$ is not an integer, $\dbinom z w$ is infinite.


Definition for Multiindices

Let $k = \sequence {k_j}_{j \mathop \in J}$ and $\ell = \sequence {\ell_j}_{j \mathop \in J}$ be multiindices.

Let $\ell \le k$.


Then $\dbinom k \ell$ is defined as:

$\ds \binom k \ell = \prod_{j \mathop \in J} \binom {k_j} {\ell_j}$


Note that since by definition only finitely many of the $k_j$ are non-zero, the product in the definition of $\dbinom k \ell$ is convergent.


Notation

The notation $\dbinom n k$ for the binomial coefficient was introduced by Andreas Freiherr von Ettingshausen in his $1826$ work Die kombinatorische Analysis, als Vorbereitungslehre zum Studium der theoretischen höheren Mathematik.

It appears to have become the de facto standard in recent years.

As a result, $\dbinom n k$ is frequently voiced the binomial coefficient $n$ over $k$.


Other notations include:

$C \left({n, k}\right)$
${}^n C_k$
${}_n C_k$
$C^n_k$
${C_n}^k$

all of which can cause a certain degree of confusion.


Examples

$2$ from $5$

The number of ways of choosing $2$ objects from a set of $5$ is:

$\dbinom 5 2 = 10$


$5$ from $2$

$\dbinom 2 5 = 0$


$2$ from $-5$

$\dbinom {-5} 2 = 15$


$5$ from $-2$

$\dbinom {-2} 5 = -6$


$3$ from $7$

The number of ways of choosing $3$ objects from a set of $7$ is:

$\dbinom 7 3 = \dfrac {7 \times 6 \times 5} {3 \times 2 \times 1} = \dfrac {7!} {3! \, 4!} = 35$


$3$ from $8$

The number of ways of choosing $3$ objects from a set of $8$ is:

$\dbinom 8 3 = \dfrac {8 \times 7 \times 6} {3 \times 2 \times 1} = \dfrac {8!} {3! \, 5!} = 56$


$4$ from $52$

The number of ways of choosing $4$ objects from a set of $52$ (for example, cards from a deck) is:

$\dbinom {52} 4 = \dfrac {52 \times 51 \times 50 \times 49} {4 \times 3 \times 2 \times 1} = \dfrac {52!} {48! \, 4!} = 270 \, 725$


Number of Bridge Hands

The total number $N$ of possible different hands for a game of bridge is:

$N = \dfrac {52!} {13! \, 39!} = 635 \ 013 \ 559 \ 600$


Also see

  • Results about binomial coefficients can be found here.


Historical Note

The binomial coefficients have been known about since at least the ancient Greeks and Romans, who were familiar with them for small values of $k$.

See the historical note to Pascal's Triangle for further history.


Technical Note

The $\LaTeX$ code to render the binomial coefficient $\dbinom n k$ can be written in the following ways:

\dbinom n k

or:

\ds {n \choose k}


The \dbinom form is preferred on $\mathsf{Pr} \infty \mathsf{fWiki}$ because it is simpler.

It is in fact an abbreviated form of \ds \binom n k, which is the preferred construction when \ds is required for another entity in the expression.

While the form \binom n k is valid $\LaTeX$ syntax, it renders the entity in the reduced size inline style: $\binom n k$ which $\mathsf{Pr} \infty \mathsf{fWiki}$ does not endorse.


To render compound arguments, braces are needed to delimit the parameter when using \dbinom, but (confusingly) not \choose.

For example, to render $\dbinom {a + b} {c d}$ the following can be used:

\dbinom {a + b} {c d}

or:

\ds {a + b \choose c d} $\ds {a + b \choose c d}$

Again, for consistency across $\mathsf{Pr} \infty \mathsf{fWiki}$, the \dbinom form is preferred.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Binomial_Coefficient&oldid=651340"