2
$\begingroup$

I tried to figure this out the other day, but failed to arrive at a formula. It seems like a simple problem, though. Forgive me if my use of terminology sounds off, I have never had any formal mathematical training.

If I have 5 different colored balls, and can match-up 3 at a time, how many different matchings are there?

And generally, if I have m different colored balls and I can choose n at a time, how many different matchings are there? What formula can I use to arrive at this number?

These being balls, a permutation like red-green-blue would be equivalent to green-blue-red, blue-red-green, green-red-blue, red-blue-green, and blue-green-red. (I thought this step could be solved by simply dividing by n!, where n is the number of balls allowed at one time.)

  • 0
    Please see [Wikipedia on combinations](http://en.wikipedia.org/wiki/Combinations)2011-08-02

1 Answers 1

7

It is worthwhile to work out small examples "by hand." The numbers $5$ and $3$ are small enough that we can simply list carefully and count. But in this answer, we look at the problem more or less in general.

I will change notation on you a little. Suppose that we have $n$ different objects. Let $k$ be an integer such that $0 \le k \le n$. We want to count the number of different of ways to choose $k$ objects from these $n$, where order does not matter. Thus, in your example, $n=5$ and $k=3$.

There are many different symbols for this number. The one most commonly used by mathematicians is $\binom{n}{k}$. In the schools, and on the keyboards of scientific calculators, the number of ways of choosing $r$ objects from $n$ is denoted by ${}_n\text{C}_r$. There are many other notations. Anything with so many names must be important!

Let's practice a bit. How many ways are there to choose $3$ colours from $5$? Answer: $\binom{5}{3}$. How many ways are there to choose a $5$-card hand from a standard $52$-card deck? Answer: $\binom{52}{5}$. How many $8$-bit strings are there, where a bit is $0$ or $1$, which have exactly $3$ $1$'s? Answer: $\binom{8}{3}$. This is because an $8$-bit string with $3$ $1$'s is completely determined once we choose the $3$ places where a $1$ will go.

Our answers have not been fully informative! In many applications, we need to produce an explicit number. Most scientific calculators have a key for evaluating $\binom{n}{k}$, aka ${}_n\text{C}_k$. But that's not a satisfying solution.

We give a detailed analysis of how to compute $\binom{16}{5}$, the number of ways to choose $5$ objects from $16$. We are using explicit numbers for the sake of concreteness. However, the method that we will use is perfectly general.

So imagine that we have $16$ different letters, and we want to choose $5$ of them. By definition, the number of ways to do this is $\binom{16}{5}$.

We ask a quite different question. How many $5$-letter "words" are there, with all the letters different? We will count the number of such words in two different ways. When we are counting words, the order of letters matters.

First way: The first letter can be chosen in $16$ ways. For each such choice, there are $15$ ways to choose the second letter. So there are $(16)(15)$ $2$-letter words. For each way of writing down the first two letters, there are $14$ ways to choose the third letter, for a total of $(16)(15)(14)$ $3$-letter words. Similarly, there are $(16)(15)(14)(13)$ $4$-letter words, and therefore $(16)(15)(14)(13)(12)$ $5$-letter words. To summarize: $ \text{There are}\qquad (16)(15)(14)(13)(12) \qquad \text{$5$-letter words.}$

Second way: Let us first of all choose which letters will be used to make our $5$ letter word. This can be done in $\binom{16}{5}$ ways. Now for each choice of $5$ letters, there are $(5)(4)(3)(2)(1)$ ways of lining them up in a row to make a $5$-letter word. It follows that: $ \text{There are}\qquad \binom{16}{5}[(5)(4)(3)(2)(1)] \qquad \text{$5$-letter words.}$

The two ways of counting must give the same answer. It follows that $\binom{16}{5}[(5)(4)(3)(2)(1)]=(16)(15)(14)(13)(12),$ and therefore $\binom{16}{5}=\frac{(16)(15)(14)(13)(12)}{(5)(4)(3)(2)(1)}.$

Exactly The same reasoning shows that in general $\binom{n}{k}=\frac{(n)(n-1)(n-2)\cdots(n-k+1)}{(k)(k-1)(k-2)\cdots(1)}\qquad\qquad \text{(Equation $1$)} $

We can now use the general method to compute the $\binom{5}{3}$ of your question, though of course for such small numbers we could just list and count: $\binom{5}{3}=\frac{(5)(4)(3)}{(3)(2)(1)}=10.$

Comment: Equivalently, we have the formula $\binom{n}{k}=\frac{n!}{k!(n-k)!} \qquad\qquad \text{(Equation $2$)}$ Equation $2$ can be obtained by multiplying "top" and "bottom" in Equation $1$ by $(n-k)!$. Equation $2$ is more compact than Equation $1$, but less pleasant from the point of view of calculation.

For much more information, please look at the Wikipedia article on Binomial Coefficients.

  • 1
    So the long waits are to give us time to do mathematics. Very thoughtful.2011-08-02