Math Applications – Number of Combinations When Selecting ‘r’ Objects Out Of ‘n’ Objects
The shaded gray areas in the sections below present advanced concepts that are suitable for high school junior and senior class students. Younger children should skip these sections.
We discussed factorials in a previous section. We will use factorials to understand the concept of combinations.
Combination refers to the number of combinations of n objects taken r objects at a time. Let us explain the concept of combinations by using an example. Your after-school activities offer four sports – soccer (S for short), tennis (T), volleyball (V), and football (F). Each student in after-school is required to enroll in two (and not more than two) sports. What are the possible number of combinations for the student to select two of these four sports activities?
Combinations – Example
Let us suppose you select Soccer (S) as one of the sports. Then you can select one of T, V, or F as the second sport. That is ST, SV, and SF for a total of three combinations.
Alternatively, you could have selected Tennis (T) as one of the sports. Then, you have the option to select volleyball (V) and football (F) as your second sport. That is TV and TF for a total of two combinations.
Finally, you could have selected volleyball (V) as one of the sports. Then you have left only Football (F) as your second sport. That is VF for a total of one combination.
If we add the combinations discussed above, we have ST, SV, SF, TV, TF, and VF. This is a total of six combinations.
Therefore, if we select two objects out of four objects, we have six different ways of doing it.
Note that the definition of combination implies that order is ignored, meaning that ST combination is the same as TS combination.
For our simple after-school sports example, the total number of combinations for selecting two sports activities out of four are shown in the Table below:
Combinations of After-school Sports Activities Example:
| COMBINATIONS | TOTAL | ||
|---|---|---|---|
| Soccer – Tennis | Tennis – Volleyball | Volleyball – Football | |
| Soccer – Volleyball | Tennis – Football | ||
| Soccer – Football | |||
| Sub-total = 3 | Sub-total = 2 | Sub-total = 1 | 6 |
That is a total of six combinations. We were able to do this exercise mentally very easily. What if we have a task to find the total possible number of combinations by selecting six objects out of a population of ten?
As an example, suppose your high school offers ten subjects of study (for example, English, math, history, social studies, computer science, creative writing,…… etc.). School requires that you must select any six out of these ten courses of study to graduate. It would be a little harder to determine the total number of possible combinations by selecting six out of the ten subjects using the approach we used for our after-school sports activities example.
Combinations Formula
In your High school math class, you will study (or you may have already studied) the formula for finding the number of combinations when selecting “r” objects out of “n” objects. In math, it is denoted by nCr and the formula is:
Number of combinations of n objects taken r at a time = nCr = n! / ((n-r)! * r!)
Where n! = n*(n-1)*(n-2)*……..3*2*1
The same formula applies to (n-r)! and r!
Now we know
- how to calculate the factorial of a number using math
- how to calculate the number of combinations taking r objects out of a total of n objects using math
Let us now write a Python program to calculate the combinations using nCr formula.
PROGRAM EXAMPLE: COMBINATIONS – COMBINATIONS OF ‘r’ OBJECTS OUT OF ‘n’ OBJECTS
Program Name: factorial_nCr.py
This program first defines a procedure fctrl(n) to calculate the factorial of a number using a recursive call. Note that the factorial of 1 is 1. Then, it defines procedure nCr(n, r), which calls the procedure fctrl(n) to calculate the number of combinations of r objects out of a total of n objects.
Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 22:39:24) [MSC v.1916 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>> # This program calculates the number of combinations taking r objects
>>> # at a time out of a total of n objects.
>>> # Define a procedure fctrl(n) to calculate the factorial of a number n.
>>> # This fctrl procedure uses recursive calls to calculate factorial.
>>> def fctrl(n):
if n == 1:
return 1 # Factorial of 1 is 1.
else:
return n * fctrl(n-1) # Recursive call to procedure fctrl(n)
>>> # Define a procedure to calculate the number of combinations of
>>> # r objects taking r objects at a time out of a total of n objects.
>>>
>>> def nCr(n,r):
combinations = fctrl(n) // (fctrl(n-r) * fctrl(r))
print(combinations)
>>> nCr(6, 2)
15
>>> nCr (6, 4)
15
>>> nCr(5, 3)
10
>>>
Math Applications – BINOMIAL THEOREM
In your high school Elementary Algebra class, you will get introduced to the Binomial Theorem. Possibly, the high school senior class may already know what Binomial Theorem is.
Binomial Theorem is the expansion of the expression (x + y)n.
Where n is the exponent, meaning (x+y) is raised to the power of n.
The expression (x + y)n expands into a sum of terms of the form a*xbyc, where ‘b’ and ‘c’ are called exponents and are integers such that b + c = n. And ‘a’ in each term, a*xbyc is called the binomial coefficient and is an integer, whose value is determined by the value of ‘n’ and ‘b’.
The following table shows the Binomial Expansion of the expression (x + y)n for the various values of exponent ‘n’. The last column of the table lists the Binomial Coefficients from each expansion.
Binomial Expression Expansion and Binomial Coefficients Table
| n | EXPRESSION | BINOMIAL EXPANSION | BINOMIAL COEFFICIENTS |
|---|---|---|---|
| 0 | (x + y)0 | 1 | 1 |
| 1 | (x + y)1 | 1*x1 +1*y1 | 1 1 |
| 2 | (x + y)2 | 1*x2 + 2*x1*y1 + 1*y2 | 1 2 1 |
| 3 | (x + y)3 | 1*x3 + 3*x2*y1 + 3*x1*y2 + 1*y3 | 1 3 3 1 |
| 4 | (x + y)4 | 1*x4 + 4*x3*y1 + 6*x2*y2 + 4*x1*y3 + 1*y4 | 1 4 6 4 1 |
| 5 | (x + y)5 | 1*x5 + 5*x4*y1 + 10*x3*y3 + 10*x2*y4 + 5*x1*y4 + 1*y5 | 1 5 10 10 5 1 |
Do You See a Pattern in Coefficients of Binomial Expansion
Let us see how the binomial expression looks like for various values of exponent and see if we can discover a pattern.
Let us look at the row in the above table, where the exponent n = 2. Examining the Binomial Expansion column in this row, we see that the exponents of each term in the expansion are
- either equal to 2 (like in x2 and y2) or
- the sum of exponents of the term is 2 as in term 2*x1*y1. Note that the exponents in the term are 1 and 1, which add up to 2 (red text).
If we examine the row with n = 3, we see that the exponent of each expansion term is
- either equal to 3 (like in x3 and y3 )
- or the sum of the exponents of the expansion term is 3 as in the term 3*x2*y1 and 3*x1*y2. The sum of exponents (red text) equals 3.
Now, if we examine the last column titled Binomial Coefficients, copied below, there is another pattern.
Here is the Pattern in Binomial Coefficients
| Row 0 | 1 |
| Row 1 | 1 1 |
| row 2 | 1 2 1 |
| Row 3 | 1 3 3 1 |
| Row 4 | 1 4 6 4 1 |
Here we see that the first number and the last number in each expansion row are always 1. All other numbers are the sum of two numbers in the row just above it. For example, in row 2, the number 2 is the sum of numbers 1 and 1 just above it (see red numbers). As another example, the number 6 in row 4 is the sum of numbers 3 and 3 just above it (see blue numbers). This pattern is valid for all numbers in Binomial Coefficients.
Binomial Expansion Coefficients and Pascal Triangle
The pattern explained above is called Pascal Triangle. We will discuss it in more detail in the next section.
Now let us look at the Binomial Coefficients from a different angle. In the previous section on Combinations, we learned that the number of possible combinations to select “r” objects out of “n” objects, is denoted by nCr. The expression for nCr is n! / ((n-r)! * r!).
To explain the relationship between nCr and the Binomial Coefficients, let us examine the case for n = 4 in the above table (x + y)4 = 1*x4 + 4*x3*y1 + 6*x2*y2 + 4*x1*y3 + 1*y4
The Binomial Coefficients in the above expansion of (x + y)4 are 1, 4, 6, 4, 1. In the table below, we list the Binomial coefficients and the expansion term position denoted by r.
For example, the first expansion term is x4 and its position is 0 corresponding to r = 0. The second expansion term is 4*x3*y1 and its position in the expansion is 1 corresponding to r = 1. As another example, the last term in the expansion is y4 and its position in the expansion is 4 corresponding to r = 4.
Binomial Coefficients Table
| EXPANSION TERM | 1*x4 | 4*x3*y1 | 6*x2*y2 | 4*x1*y3 | 1*y4 |
|---|---|---|---|---|---|
| Binomial Coefficient | 1 | 4 | 6 | 4 | 1 |
| Term # (r) | 0 | 1 | 2 | 3 | 4 |
| nCr | 4C0 | 4C1 | 4C2 | 4C3 | 4C4 |
| nCr | 4! / ((4-0)! * 0!) | 4! / ((4-1)! * 1!) | 4! / ((4-2)! * 2!) | 4! / ((4-3)! * 3!) | 4! / ((4-4)! * 4!) |
| nCr Value | = 1 | = 4 | = 6 | = 4 | = 1 |
From the above table, we see that the Binomial Coefficients 1, 4, 6, 4, 1 in the expansion of (x + y)4 are equivalent to nCr (4C0, 4C1, 4C2, 4C3, and 4C4).
So, the expression (x + y)4 = 1*x4 + 4*x3*y1 + 6*x2*y2 + 4*x1*y3 + 1*y4 is equivalent to:
(x + y)4 = 4C0*x4 + 4C1*x3*y1 + 4C2*x2*y2 + 4C3*x1*y3 + 4C4*y4
What we have learned from above is that the Binomial Coefficients are nothing but the nCr values, where n is the exponent of the expression (x + y)4 and r is the position of the term in the expansion starting from 0 (r = 0) for the first expansion term; r = 1 for the second expansion term; r = 2 for the third expansion term, and so on.
Summary of Binomial Coefficients:
- The number of expansion terms is one more than the exponent, n. For exponent n = 1, the number of expansion terms is 2; for n = 4, the number of expansion terms is 5, and so on.
- The first expansion term power of x is n and the power of y is 0. Example: x4*y0. The power of x of the next expansion term is (n-1) and the power of y is 1. In the next expansion term, the power of x is (n-2) and power of y is 2, and so on. This continues for each subsequent expansion term. In our example (x + y)4, the expansion term 6*x2*y2, the power of x = 2, and the power of y = 2, which adds up to 4. In the expansion term 4*x3*y1, the power of x = 3 and the power of y = 1, which again adds up to 4.
- In each expansion term, the sum of the exponents equals n (in our case, that is 4.)
- The coefficients of the first and last terms in each row are both 1.
PROGRAM EXAMPLE: CALCULATE BINOMIAL COEFFICIENTS
# PROGRAM TO CREATE A BINOMIAL COEFFICIENTS
# Define fctrl() procedure to calculate factorial of any number.
# fctrl() procedure is called by procedure nCr defined below
# to calculate number of combinations of r objects out of total of n objects.
def fctrl(n):
if n == 0:
return 1 # Factorial of number 1 is 1.
else:
return n * fctrl(n-1) # Make a recursive call to procedure fctrl(n)
# Define procedure nCr(n) to calculate the number of combinations
# of "r" items out of total of "n" items.
# Procedure nCr calls procedure fctrl(n) to calculate combinations.
# The number of combinations of r objects out of n are the
# Binomial Coefficients of the expansion of expression (x+y)^n
def nCr(n):
first = 1
print(first, end = " ")
for r in range(1, n+1):
print(fctrl(n)//(fctrl(r)*fctrl(n-r)), end = " ")
# MAIN PROGRAM
nCr(4) # Call the nCr() procedure passing an argument
The following is the program output.
Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 22:39:24) [MSC v.1916 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>>
======== RESTART: C:/Users/username/Python_scripts/factorial_nCr_Binomial.py =======
1 4 6 4 1
>>>
We will explore an interesting triangle called the Pascal Triangle in the next sections. You will find that there is a relationship between the Binomial Coefficients and the Pascal Triangle rows.
Pascal Triangle
Pascal’s Triangle is an arrangement of triangular number patterns that gives the coefficients in the expansion of any binomial expression.
The rows of the Pascal Triangle are numbered starting from top with n = 0. The entries in each row are numbered from 0 (r = 0). The Pascal Triangle has the following configuration.
On row 0, write only the number 1.
The next Pascal Triangle row corresponding to n = 1 has two numbers 1 and 1.
The third Pascal Triangle row corresponds to n = 2. To get the numbers in the third row, add the two numbers in the row above corresponding to n = 1. This is shown by the red numbers in rows 2 and row 3.
This process can be continued to any number of rows. This is illustrated in rows corresponding to n = 4 and n = 5, where the number 10 is obtained as a sum of 4 and 6 of the previous row. The following is an example of a Pascal Triangle for six rows (n = 0 to n = 5).
Pascal Triangle for n = 0 to 5
| ROW NUMBER n | PASCAL TRIANGLE COEFFICIENTS |
|---|---|
| 0 | 1 |
| 1 | 1 1 |
| 2 | 1 2 1 |
| 3 | 1 3 3 1 |
| 4 | 1 4 6 4 1 |
| 5 | 1 5 10 10 5 1 |
Below is a program that creates the Pascal Triangle for the first six rows. By changing the parameter in the Main Program in the statement nCr(6) to any other number like nCr(10), you can make a Pascal Triangle of any desired number of rows. The following program illustrates how to create a Pascal Triangle using Python.
PROGRAM EXAMPLE: CREATE PASCAL TRIANGLE USING PYTHON
Program Name: Pascal_def_Factorial_Parameter.py
# PROGRAM TO CREATE A PASCAL TRIANGLE #
# The fctrl(n) is a procedure to find factorial od=f any number.
# The procedure makes recursive call to procedure fctrl(n).
def fctrl(n):
if n == 0:
return 1
else:
return n * fctrl(n-1)
# nCr(n) is a procedure to calculate the number of combinations
# of "r" items out of total of "n" items.
def nCr(n):
for i in range(n):
for r in range(n-i+1):
print(end = " ") # Add a space on the left of Pascal Triangle.
for r in range(i+1):
print(fctrl(i)//(fctrl(r)*fctrl(i-r)), end = " ")
print() # Add a line feed after each row of Pascal Triangle is completed.
# MAIN PROGRAM
nCr(6) # Call the nCr() procedure passing an argument '6'.
Program’s output:
Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 22:39:24) [MSC v.1916 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>>
==== RESTART: C:/Users/username/Python_scripts/Pascal_def_Factorial_Parameter.py ===
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
>>>
The figure above shows the Pascal Triangle for the first 7 rows (n = 0 to n = 6) with all binomial coefficients. The last row (n = 6) shows the position of the expansion terms r = 0 to r = 6 in blue color. The row corresponding to n = 5 shows the position of the expansion terms r = 0 to r = 5 in red text.
About Circle and pi
The circle is a curve so that every point on the curve is the same fixed distance away from a point in the plane, called the center. This distance from the center to the curve is called the radius, denoted by ‘R’. The circle consists of all points that are a fixed distance from a center. This set of points is called the circumference
In the adjacent figure:
C = the circumference. It is the curve that defines the circle.
O is the center of the circle
D = Diameter (line passing through the center of the circle to the circumference)
R = radius (the line from the center to the circumference). Radius = half of diameter.
Definition and Value of pi
The pi, denoted by the Greek letter π, is a mathematical constant. It is defined as the ratio of a circle’s circumference to its diameter.
π = Circumference/Diameter = C/D.
π is an irrational number, that is, it cannot be expressed as the ratio of two natural numbers or as a common fraction. Its decimal representation of pi never ends, nor does it end in a repeating (recurring pattern). For quick calculations, it is approximated by fraction 22/7. Its value is approximately equal to 3.14159.
pi is also called Archimedes’ constant. In 250’s B.C., the Greek mathematician Archimedes figured out the value of pi accurate to two digits and determined it to be 3.14. In the 20th and 21st centuries, mathematicians and computer scientists discovered new computer algorithms that extended the decimal representation of π to many trillions of digits after the decimal point, but there is no accurate value of pi since it cannot be written as a fraction or a decimal number with terminating a number of digits.
Circumference of a Circle
Suppose you have a circular jogging track in your school that you jog on every day.
The diameter of the circular jogging track is 100 meters. How can you find out how much you jog each day?
The relationship between the diameter and the circumference of any circle is given by the equation below.
You can use this equation to figure out your jogging distance.
Circumference = π * Diameter
Or C = π * D
Or C = 2 * π * R, where R is the radius of the circle.
Area of a Circle
How about the area of the circle? If the school wants to put a lawn inside the jogging track, the school needs to determine the area of the circle so that the school can order enough grass rolls.
How would you answer this question if it is posed to your class?
The area of the circle is given by the following relationship between area and radius.
Area = π * (radius)**2
Or Area = π * R**2
