What is $ {n\choose k}$?
Andrew Henderson 
This is the Binomial theorem:
$$(a+b)^n=\sum_{k=0}^n{n\choose k}a^{n-k}b^k.$$
I do not understand the symbol $ {n\choose k}.$ How do I actually compute this? What does this notation mean? Help is appreciated.
$\endgroup$ 47 Answers
$\begingroup$The symbol ${n\choose k}$ is read as "$n$ choose $k$." It represents the number of ways to choose $k$ objects from a set of $n$ objects. It has the following formula $$ {n\choose k}=\frac{n!}{(n-k)!k!}.$$ Here, $$ n!=n(n-1)(n-2)\cdots2\cdot1.$$
$\endgroup$ 5 $\begingroup$$$\binom{n}{k}= \frac{n!}{k!(n-k)!}$$
It computes the number of ways we can choose $k$ items out of $n$ items.
$\endgroup$ $\begingroup$$n \choose k$ - n choose k - how many different ways there are to pick $k$ items from a set of $n$ elements. The explanation starts from permutations, through combinations, finishing with binomial theory. If you are familiar with the formulas and the ideas behind them feel free to skip some steps.
Permutations
A permutation of a set $\mathcal{S}$ is an arrangement of its elements in a specific order. The number of possible permutations is denoted as $P$.$$ \begin{aligned} P^n_n &= n(n-1)(n-2)\cdots1 \\\\ &= n! \end{aligned} $$
The idea behind the formula: on the first pick we can choose from $n$ elements - $n$ possible picks. After picking the first element, we are left with $n-1$ elements from which to choose. Following this logic, eventually, we are left with $2$ elements from which to choose and then finally $1$.
It can be observed that we can prematurely end this process and only choose $k$ elements from $\mathcal{S}$:
$$ P^n_k=n(n-1)(n-2)\cdots(n-(k-1)) $$
The idea is the same just that we stop after our $k$-th pick, during which we had $n-(k-1)$ choices as we already picked $k-1$ elements.
Combinations
The base idea behind combinations is that one is picking $k$ elements from the set $\mathcal{S}$ of size $n$ but not putting them in a sequence - meaning that the order is not important. We can view combinations as creating a subset $\mathcal{S'}\subseteq\mathcal{S}$, of size $k$, $k\leq n$. The number of possible ways we can create this subset $\mathcal{S'}$ from the set $\mathcal{S}$ is denoted as $C$ and defined as:
$$ \begin{align} C^n_k & = {n\choose k} \\\\ &=\frac{n(n-1)(n-2)\cdots(n-(k-1))}{k!} \\\\ &= \frac{n!}{(n-k)!k!} \end{align} $$
Observe how the numerator is equivalent to $P^n_k$ and the denominator to $P^k_k$.
The idea behind the formula: notice that the extra variability in $P^n_k$ comes from the different permutations ($P^k_k$) each of those combinations ($C^n_k$) can make. To put this in mathematical terms:$$ \begin{align} P^n_k &= C^n_kP^k_k \\\\ &\Rightarrow \\\\ C^n_k &= \frac{P^n_k}{P^k_k} \\\\ &= \frac{n(n-1)(n-2)\cdots(n-(k-1))}{k!} \\\\ &= \frac{n!}{k!(n-k)!} \end{align} $$
Binomial Coefficients
Let's take the example of $(x+y)^n$ and write it as a product of $n$ binomials:
$$ (x+y)^n = (x+y)(x+y)\cdots(x+y) $$
If we were to expand this, each resulting term in the expansion will be a product of $n$ terms, one term picked from each of the binomials above. We need to focus only on $x$ (one of the terms) - if we choose to pick $x$ $k$ times then we must pick $y$ $n-k$ times. There are $n$ binomials in the expansions and we are making $k$ picks, therefore, the number of resulting terms in the expansion with the $k$ picks of $x$ is $C^n_k$ or $n\choose k$.
$\endgroup$ $\begingroup$$\binom{n}{k}:=\frac{n!}{(n-k)!k!}$
With $n!=n\cdot (n-1)\cdot (n-2)\cdot\dotso\cdot 3\cdot 2\cdot 1=\prod_{i=1}^n i$
$\endgroup$ $\begingroup$$ \binom{n}{k} = \frac{n!}{(n-k)!k!} $
It is used to calculate the number of ways "k" events can occur in "n" choices.
$\endgroup$ $\begingroup$$${n\choose k}={n!\over k!(n-k)!}$$
$\endgroup$ $\begingroup$Number of words of length $n$ over the alphabet $\{a,b\}$ such that $k$ letters are $a$. When you expand the LHS this characterization immediately implies the RHS.
$\endgroup$
