Main Applications Identities History FAQ Algorithms

Questions answered by the binomial coefficients

                               
1. How do we expand a binomial (a+b)ⁿ?
Of course, this is how the numbers got the name binomial coefficients; since (a+b)⁴=a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴, we can think of the numbers 1,4,6,4,1 as the 4^th row and 6 is the 2^nd entry in the row.

2. How many ways are there to choose 7 things out of a collection of 10 distinct things?
The answer here would be , and this is the reason we pronounce the two numbers in the parentheses “10 choose 7”.

3. How many bitstrings of length 9 have exactly 4 zeros and 5 ones?
Again, the answer is a binomial coefficient ; instead of bitstrings, it could be thought of as ways to arrange four red balls and five green balls in a row, or ways to arrange four short notes and five long notes into a musical arrangement; this second problem is called prosody, and it was of interest to the mathematicians who first looked into the binomial coefficients in India.

4. How many different results are there when I roll three six-sided dice that I can't tell apart?
, where n is the number of sides on each die and k the number of dice.  If the dice can be distinguished from each other, then there are n^k different results.  For example, there are 36 ways to roll two dice of different colors, but in most games, two dice of the same color are used, and there are only 21 distinct results, since 6-5 is equivalent to 5-6 in terms of game play.  (For three six sided dice, the answers are 216 if distinguishable and 56 if not.)

5. How many different solutions are there in non-negative integers to the problem a₁ + a₂ + ... + a_n = k ?   
.

6. How can we match up Answer 4 to Answer 5?
If we take the example of three six-sided dice, let a_i = # of dice on this roll that are showing the number i; for example, the roll 344 would be sent to 0+0+1+2+0+0 = 3, since there is 1 three and 2 fours.  This is a 1-1 correspondence (or bijection), which means the cardinality of the two sets must be the same.

7. You have k beads, which you cannot tell apart, and n boxes, numbered 1 through n.
        a. How many different ways can you put the beads into the boxes?
         , just like the answers to Problems 4 and 5.  (It is left to the reader to see why this is the same by a 1-1 correspondence.)

        b. How many different ways can you put the beads into the boxes if no more than one bead is in each box?
         , which will equal 0 if n < k.

        c. How many ways can you put the beads into the boxes if every box contains at least one bead?
         , which will equal 0 if n > k.