Why can $ \frac {n!}{k!(n-k)!}$ be used as binominal coefficient?

Question

I am having trouble grasping how $ \frac {n!}{k!(n-k)!}$ could possibly equal the binominal coefficient.

As far as I can tell, $ \frac {n!}{k!(n-k)!}$ tells us how many combinations that are possible, if you take say, k differently numbered balls from a population of n. The $k!$ in the denominator eliminates all permutations of the same combination.

The binominal coefficient seems to tell another thing entirely, namely the number of permutations for any given combination of $ka*(n-k)b$. In this later scenario the "balls" aren't differently numbered.

How can both of theses things be calculated by the same formula?

If this question has been asked before, then kindly point me in the right direction.

/Magnus

Answer 1

How can both of theses things be calculated by the same formula?

It seems like what's confusing you isn't really the math, but the combinatorial intuition behind it. If so, perhaps the following thought experiment will help:

1. Take $n$ balls, numbered from $1$ to $n$.
2. Choose $k$ of them.

Clearly, there are $\frac{n!}{k!(n-k)!}$ ways to do this.

3. Paint the $k$ chosen balls red, and the $n-k$ other balls blue.
4. Put the balls in a line, ordered by their numbers.
5. Erase the numbers.

You now have a line of $n$ un-numbered balls, with $k$ of them painted red and the rest blue. I'm sure you'll agree (since you stated as much in your question) that there are ${n \choose k}$ ways to arrange these $k$ red balls in the line.

All you need to do now is observe that each choice of $k$ numbered balls out of $n$ in step 2 corresponds to a different arrangement of the red balls in step 5, and vice versa. Thus, $\frac{n!}{k!(n-k)!} = {n \choose k}$.

More generally, the key observation is that, in both cases, we're choosing $k$ elements out of $n$ distinct ones. In the first case, those $n$ distinct elements are the numbered balls; in the second case, they're the positions that the balls occupy in the line.

Answer 2

In the binomial expansion of $(a+b)^n$, you get $2^n$ terms, each consisting of a product of $a$s and $b$s, for a total of $n$ factors in each term. Because multiplication commutes, we can group together the terms which contain the same number of $a$s and $b$s. So now we want to know how many terms have $k$ $a$s in them.

To see this, note that again each term has $n$ factors. To have $k$ $a$s, we need only pick $k$ of the positions to be $a$, then the other $n-k$ will be $b$. Thus we get the correct count if we know the number of ways to choose $k$ objects from $n$ objects regardless of order. This is $\frac{n!}{k!(n-k)!}$.

This is a little bit tricky because of the fact that we are choosing from the positions, which might make it sound like we should use the formula for permutations. But we should not, because reordering the $a$s within the same $k$ positions does not result in a new term.

To put it another way, the binomial coefficient arises as the answer to the question: if we have $n$ places to put balls, and we have $k$ indistinguishable red balls and $n-k$ indistinguishable blue balls, how many ways can we position the balls?

Still another perspective: suppose we want to determine the number of terms containing $k$ $a$s and $n-k$ $b$s recursively (like how we learn to count things using the addition and multiplication rules). Call this number $B(n,k)$. First $B(m,0)=B(m,m)=1$ for any $m$; this is because once we have exhausted the supply of $a$s or $b$s, there is only one way to fill in the remaining positions. Next, if we put an $a$ in the first position, then we have $n-1$ remaining positions and $k-1$ remaining $a$s. If instead we put a $b$ in the first position, then we have $n-1$ remaining positions and $k$ remaining $a$s. Thus

$$B(n,k)=B(n-1,k-1)+B(n-1,k)$$

which, coupled with the boundary conditions, is the famous "Pascal's triangle" recurrence for the binomial coefficient. This again has an interpretation in terms of "choosing objects".

Answer 3

The expression $\dfrac{n!}{(n-k)!}$, a.k.a. ${}_nP_r$, is the answer to the question

If we have $n$ distinct objects, how many ways are there of choosing $k$ of them, where we have decided that the order in which we take them out does matter?

The expression $\dfrac{n!}{k!(n-k)!}$, a.k.a. ${}_nC_r$ and $\binom{n}{k}$, is the answer to the question

If we have $n$ distinct objects, how many ways are there of choosing $k$ of them, where we have decided that the order in which we take them out does not matter?

Answer 4

First the definition of $\dbinom nk$ is that it is the coefficient of $x^k$ when you develop $(1+x)^k$. The number of ways to chose $k$ objects among $n$ objects should be denoted $C_n^k$.

Second the closed formula for $\dbinom nk$ with factorials comes from the fundamental formula: $$\binom nk=\frac nk\binom{n-1}{k-1}\quad \forall k\ge 1$$ through an easy induction.

The fundamental formula itself comes from comparing $\displaystyle\bigl((1+x)^n\bigr)'$ as $\Bigl(\sum_{k=0}^n\dbinom nk x^k\Bigr)'$ and the binomial development of $n(1+x)^{n-1}$.

Answer 5

I'm not sure where the breakdown in understanding is occurring, but it seems to be in reconciling the heuristic with the numerical. Let me present things in a (possibly) different way that may show how things work.

---

First of all, we use the following

Definition: Given an integer $n\ge0,$ let $n!$ be the number of distinct orders in which we may arrange a set of $n$ objects.

Note that I say distinct orders, rather than distinguishable orders. This is an important distinction! After all, if we have a set of $n$ indistinguishable objects, then there is only one distinguishable order in which we can place them, and I am certainly not asserting that $n!=1$ for all integers $n\ge0.$ Here's a nice way of thinking of it: suppose that the balls are labeled with numbers from $1$ to $n$ (inclusive), but the numbers are printed with an ink that can only be discerned by beings who can detect wavelengths outside of the "visible spectrum." In this fashion, we can easily see that orders may be distinct, but indistinguishable to us.

Let's show that this definition of $n!$ agrees with the usual recursive definition. First, note that the only way to put $0$ objects in order is to not put any objects in order. On the other hand, if you don't put any objects in order, then you put $0$ objects in order. Hence, perhaps counterintuitively, $0!=1$ by the definition given above.

Now, suppose we have $n$ objects to order, and that $(n-1)!$ agrees with the usual recursive definition. On the one hand, given a particular order of the $n$ objects, there is an initial object (readily, there are $n$ possibilities for this object) and an order of the $n-1$ non-initial objects. Note that different orders either yield different initial objects, or they yield the same initial object, but different orders of the $n-1$ non-initial objects. Thus, we have: $$n!\le n\cdot(n-1)!$$ On the other hand, if we choose one of the $n$ possible initial objects--which we may do in $n$ ways--and then choose an order of the $n-1$ non-initial objects--which, by assumption, we may do in $(n-1)!$ ways--then we have ordered the $n$ objects. Different choices of initial objects yield different orders. Also, among orders with the same initial object, different orders of the $n-1$ non-initial objects yield different orders. Hence, we have: $$n\cdot(n-1)!\le n!$$ Putting our previous work together, we have: $$n!=n\cdot(n-1)!$$

---

Second of all, we use the following

Definition: Given integers $k,n$ with $0\le k\le n,$ let ${}_nP_k$ be the number of distinct ways in which we may choose and order a $k$-element subset of an $n$-element set.

Suppose we have $n$ objects to order. Given a particular order of the $n$ objects, there is a set of the $k$ initial objects and an order of said objects (by definition, we can choose and order such a set in ${}_nP_k$ ways), and there is an order of the $n-k$ non-initial objects. Different sets of the $k$ initial objects yield a different order of the $n$ objects, different orders of the same set of the $k$ initial objects yield different orders of the $n$ objects. Moreover, given a particular set and order of the $k$ initial objects, different orders of the $n-k$ non-initial objects yield different orders of the $n$ objects. Hence: $$n!\le{}_nP_k\cdot(n-k)!$$ On the other hand, similar to the proof in the factorial case (which is the permutation case, with $k=n$), we have: $${}_nP_k\cdot(n-k)!\le n!$$ Combining the two previous results, we have: $$n!={}_nP_k\cdot(n-k)!$$ Since $(n-k)!$ is positive, then we have: $${}_nP_k=\frac{n!}{(n-k)!}$$

---

Third, we use the following

Definition: Given integer $k,n$ with $0\le k\le n,$ let ${}_nC_k$ be the number of distinct $k$-element subsets of an $n$-element set.

Suppose we have a set of $n$ objects from which to choose. Given a particular choice and ordering of $k$ of these objects, there is a set of $k$ chosen objects, and an ordering of these $k$ objects. If we choose a different subset of $k$ objects, or a different ordering of the same $k$-element subset, then we obtain a different $k$-object order, so we have: $${}_nP_k\le{}_nC_k\cdot k!$$ Again, in a similar fashion, the reverse inequality holds, so we have: $${}_nP_k={}_nC_k\cdot k!$$ Since $k!$ is positive, then we have: $${}_nC_k=\frac{{}_nP_k}{k!}=\frac{n!}{k!(n-k)!}$$

---

At this point, the proof that $\binom nk={}_nC_k$ is straightforward. The $n=0,1$ cases are trivial, so take an integer $n>1,$ and let $S=\{i\in\Bbb Z:1\le i\le n\}.$ Consider the expansion of the product $$\prod_{i\in S}(x_i+y_i)=(x_1+y_1)\cdots(x_n+y_n).$$ It should be clear that every term of the expansion is monic, and that each term can be written in the form $$\left(\prod_{i\in A}x_i\right)\cdot\left(\prod_{j\in S\smallsetminus A}y_j\right)$$ for some unique $A\subseteq S.$ That is, $$\prod_{i\in S}(x_i+y_i)=\sum_{A\subseteq S}\left(\prod_{i\in A}x_i\right)\cdot\left(\prod_{j\in S\smallsetminus A}y_j\right).\tag{$\star$}$$ Now, we make the substitution $x_i=x$ and $y_i=y$ for all $i\in S.$ Then the left-hand side of $(\star)$ is precisely $(x+y)^n,$ so applying binomial theorem gives us $$\sum_{k=0}^n\binom nk x^k y^{n-k}\overset{(\star)}{=}\sum_{A\subseteq S}\left(\prod_{i\in A}x\right)\cdot\left(\prod_{j\in S\smallsetminus A}y\right)=\sum_{A\subseteq S}x^{|A|}y^{n-|A|}=\sum_{k=0}^n{}_nC_kx^ky^{n-k}.$$ Since $x,y$ are arbitrary reals, it follows that $\binom nk={}_nC_k$ for all $0\le k\le n.$