Introducing the Binomial Coefficient for Positive Integers

Home / Introducing the Binomial Coefficient for Positive Integers

How many ways are there to select ‘k’ outcomes from ‘n’ possible outcomes, without concern for the order (or sequence) of the selection? The answer lies in the binomial coefficient, which also answers several related questions in combinatorics (the study of countable objects) and algebra.

Let’s Keep the Discussion of Binomial Coefficients “Positive”

This article discusses only non-negative integer values of ‘k’ and ‘n,’ so “n ≥ k ≥ zero” and “both ‘n’ and ‘k’ are integers.”

Although the “Gamma function”, ‘Γ(x)’, extends the factorial function beyond the non-negtive integers, it will not be discussed here.

Introducing the Binomial Coefficient

Choose K of N in factorial math. Image by Mike DeHaan

When this factorial formula: “C(n, k) = n! / ( k! * (n – k)! )” is read aloud as “n choose k,” its meaning is to “choose any ‘k’ of ‘n’ items in any order.” What does this mean in a real example from combinatorics, the mathematics of counting?

Let’s say we have the four aces from a standard deck of playing cards, and want to select a pair. The formula for “4 choose 2″ provides the calculation.

• C(4, 2) = 4! / ( 2! * 2! ) = (4*3*2*1)/((2*1)*(2*1)) = 6

Let’s count out the possibilities. Let A={c, d, h, s} represent the aces of clubs, diamonds, hearts and spades. The “2-subsets of A” is the set of pairs from A, disregarding order. This set is {(c,d), (c,h), (c,s), (d,h), (d,s), (h,s)}. Note that there are six unique pairs.

Math can help you find a pair of aces. Photo by Images_of_Money

In general, “n choose k” gives the cardinality, or size, of the set of “k-subsets” that can be chosen from a set with ‘n’ elements.

Try to solve this exercise: Each side in the game of chess has bishops, a King, knights, pawns, a Queen and rooks. Therefore there are 6 types of pieces. Let P={b, K, k, p, Q, r}. In how many ways can one select any two types from this set?

Why Use the Word “Binomial?”

The word “binomial” relates to the two terms inside the brackets in the construction “(x + y)^n” for a non-negative integer ‘n.’

In the expansion of “(x + y)^n = (x + y)*(x + y)*…*(x + y),” there are terms such as “m*(x^j * y^(n-j))” for every “j from zero to n.” The integer ‘m’ in this expansion is the “coefficient.” Here is an example:

• (x + y)^2
• = (x + y)*(x + y)
• = x*x + x*y + y*x + y*y
• = 1*x^2 + 2*x*y + 1*y*2″

The above coeficients are ‘1‘, ‘2‘ and ‘1‘.

The “Binomial Theorem” states that in any expansion of “(x + y)^n,” the coefficient for “x^j * y^(n-j)” is C(n, j).

The Symmetry Rule of Binomial Coefficients

One unusual but obvious fact about the binomial coefficient is the symmetry rule. “C(n, k) = C(n, n-k).”

The simple algebraic proof uses the commutative property of multiplication.

• C(n, n-k) = n! / ( (n – k)! * (n – (n – k))! )
• = n! / ( (n – k)! * k! ) , by simplifying “n – (n – k)” = “n – n + k” = ‘k’
• = n! / ( k! * (n – k)! )
• = C(n, k) , as required
Categories Uncategorized