Introduction to Combinations

Introduction to Combinations

In my Introduction to Permutations post, we have learned that the number of permutations (or arrangements) of n objects taken at n at a time written as P(n,n) is equal to n! = n(n-1)(n-2) \cdots (3)(2)(1), and we have also learned that the number of permutations of n objects taken k at a time written as P(n,k) is equal to \displaystyle\frac{n!}{(n - k)!}.

In Figure 1, shown are the permutations of 4 letters, A, B, C and D taken 4 at a time.  From the figure, we can see that there are indeed 4!= (4)(3)(2)(1) = 24 of such arrangement. In Figure 2, shown are the permutations of 4 letters taken 3 at a time, and we have shown that the number of permutations is equal to \displaystyle\frac{4!}{ (4 - 3)!} = \frac{4!}{1!} = (4)(3)(2)(1) = 24.  In Figure 3, we have again listed the permutations of 4 letters taken 2 at a time, and have shown that the number of permutations is equal to \displaystyle\frac{4!}{(4-2)!} =12.

Figure 1 – Permutations of ABCD, taken 4 at a time.

Figure 2 – Permutations of ABCD, taken 3 at a time.

Figure 3 – Permutations of ABCD, taken 2 at a time.

If we talk about combinations, however, the arrangement of objects does not matter. For example, if we want to buy a milk shake and we are allowed to choose to combine any 3 flavors from Apple, Banana, Cherry and Durian*, then the combination of Apple, Banana and Cherry is the same as the combination Cherry, Apple, Banana.

Try to list all the possible combinations of 3 flavors taken from 4 before proceeding.

If we choose to shorten the name the fruits by selecting the first letter of their names, we only have 4 possible combinations for question above: ABC, ABD, ACD, and BCD. Notice that these are the only possible combinations. Also, observe that if we list the permutations of ABC, we have ACB, BAC,BCA, CAB and CBA.  This means that in permutations, we have counted each combination of 3 flavors from 4 flavors 6 times (or 3! times instead of one.

In other words, a combination is just like a subgroup of a group. For instance, if we want to find the number of subgroups containing 3 objects taken from 4 objects (or the combination of 4 objects taken 3 at a time), it is the same as asking  “how many possible groups of 3 objects can be taken from 4 objects?” In Figure 4, all the possible subgroups of 3 letters taken from 4 letters are displayed by the orange border. You also would have realized that the number of permutations is an overcounting of the number of combinations.

Figure 4 – The combinations of 4 objects taken 3 at a time is the same as the number of subgroups of 3 objects taken from 4 objects.

In Figure 2, ABC, ACB, BAC, BCA, CAB and CBA are permutations of Apples, Banana and Cherry. For each subgroup of 3, we realized that we counted 3! = 6 times. So, to get the number of combinations, we divide our number of permutations P(4,3) by the number of permutations of our subgroupP(3,3) = 3!. Therefore, we can say that the number of combinations of 4 objects taken 3 at a time is equal to

\displaystyle\frac{P(4,3)}{P(3,3)} = \frac{\frac{4!}{(4-3)!}}{3!} = \frac {4!}{(4-3)! 3!}

In general, to get the number of combinations of n objects taken k at a time, we have to divide the number of permutations of P(n,k) by the number of permutations of the subgroup P(k,k).

\displaystyle\frac{P(n,k)}{P(k,k)} = \frac{\frac{n!}{(n-k)!}}{n!} = \frac {n!}{(n-k)! k!}

The combinations of n objects taken k is usually denoted by C(n,k) or \displaystyle n \choose k

_____________________________________________________________

*Durian is a fruit which can be found in the Philippines. It looks like a jackfruit.

Derivation of the Quadratic Formula

When we discuss about functions, we usually talk about their roots, or geometrically where their graphs pass through the x-axis. For example, - 3, 1 and 3 are the roots of the graph of the function in Figure 1 because it passes through x = -3, x =1 and x=3.

Since we are looking for points on the x-axis, it means that all the points that we are looking for have y-coordinate 0. As a consequence, (i) if we want to find the root of a quadratic function we have set y = 0 and then solve for the values of x.

quadratic formula

Figure 1 – The x-axis and the line with equation y = 0 are basically the same line so all points on the x-axis have y-coordinate 0.

With the things above in mind, let us find the roots of two quadratic functions: (1) y = x^2 + 5x + 6 and (2) y = x^2 + 3x + 1.

Finding the root by Factoring

The roots of the function y = x^2 + 5x + 6 are easy to find. As we have said, to get the root of a function, we set y to 0 and then find the value the value of x. Solving by factoring, we have

x^2 + 5x + 6 = 0 \Rightarrow (x + 2)(x + 3) = 0

Now, (x + 2)(x + 3) = 0 if x + 2 = 0 or/and x + 3 = 0. Solving for the value of x on both equations, we have x= -2 and x = -3.

Thus, even though we have not seen the graph of the function yet y = x^2 + 5x + 6, we are sure that it will pass through x = -2 and x = -3. If you want to verify if the graph of the function y= x^2 + 5x + 6 indeed passes through the x-axis at x = -2 and x = -3, you can verify its graph using a graphing software or a graphing calculator.

Figure 2 – We are sure that the graph of $y = x^2 + 5x + 6$ will pass through the yellow points.

Factoring: Another Interpretation

Another possible interpretation of the expression x^2 + 5x + 6 can be the area of a rectangle with length x + 3 and width x+2. The distribution of the products of the terms of the expressions are represented by the four rectangles formed shown below.

Figure 3 – Another interpretation of the expression x^2 + 5x + 6.

Let us try another example: Let us find the roots of the quadratic function y = x^2 + 3x + 1. You will probably observe that there is no way that we can factor this expression. The last term is 1, but there are only two factors of 1: \{1,1\} and \{-1,-1\}, so this means that that the numerical coefficient ofx must be 2 or -2, but it is equal to 3. Hence, the expression is not factorable.

Since, the expression is not factorable, we cannot find the length and width of a rectangle with area x^2 + 3x + 1. The easiest way probably to find its length and width is to assume that it is a square.

Completing the Square

We have a quadratic expression which we assumed a perfect square so its factor must be of the form (x+b)(x+b) where b is a real number. Also, (x+b)^2 = x^2 + 2bx + b^2. If we consider x + b as a side of the square, then the product of the expressions will form two squares namely x^2 and b^2, and 2 congruent rectangles with each having an area of bx.

 

 

 

Figure 4 – A square with side x + b, where b is a constant.

If we want to use the product of x+ b above, first, we have to take off x^2 as one of the squares. Then we are left with a figure with area 3x which we will divide into two congruent rectangles. If we are going to follow the positions of the rectangles in Figure 4, then we will have an x^2 and two pieces of \frac{3}{2}x (see Figure 5).To construct a square, we extend one of the sides of each of the congruent rectangles.

 

Figure 5: Completing the square of x^2 + 3x + 1.

Since we have two small rectangles with area \frac{3}{2}x, and the longer side (in the diagram) is x, it follows that the other dimension is \frac{3}{2} which gives us a smaller square with area \frac{9}{4}.

 

Figure 6 – The area of the small formed is 9/4 and the side length of the big square formed is x + 3/2.

The biggest square formed in Figure 6 has area x^2 + \frac{3}{2}x +\frac{9}{4}, which is \frac{5}{4} more than our original quadratic expression, so we will deduct \frac{5}{4} to preserve the original expression. So our final expression is x^2 + \frac{3}{2}x +\frac{9}{4} - \frac{5}{4}

Algebraically, if we have the expression x^2 + bx + c, and we want to “compete its square”, we want to transform it to an expression of the form (x-h)^2 + k. For example, x^2 + 6x + 12 can be expressed as (x + 3)^2 + 3. Another example is that x^2 + 8x + 12 can be written as (x + 4)^2 - 4. Note that the coefficient of x^2 should be 1 so that we are sure that a square x by x is formed as shown in figures 4,5 and 6. In general, the possible steps that we are going to create using the general equation y = ax^2 + bx + c is to set y to 0 and then find the value of x.

In constructing the square in Figure 6, we went through the following processes:

(ii) We made sure that the numerical coefficient of x^2 is 1 to ensure that we have a square with factors (side length) x.

(iii) We isolated the constant term c = 1, and we just used the first x^2 and the second term 3x.

(iv) To get the area of the smaller square, we divided the numerical coefficient of the 3x by 2 then squared it to get \frac{9}{4}.

Shown in Figure 7 is the summary of the steps we did to get the roots of the quadratic function y = x^2 + 3x + 1. The rightmost column of the table shows the generalization of our steps, which is getting the roots of the quadratic function y = ax^2 + bx + c.

Figure 7 – A step-by-step derivation of the quadratic formula.

Quadratic Formula

The formula x = \displaystyle\frac{-b \pm \sqrt{b^2-4ac}}{2a} located at the bottom part of the rightmost column of the table in Figure 7 is called the quadratic formula. We have derived the quadratic formula from completing the square of a quadratic equation. From the formula, the roots o the quadratic function y = ax^2 + bx + c are \displaystyle\frac{-b + \sqrt{b^2-4ac}}{2a} and \displaystyle\frac{-b - \sqrt{b^2-4ac}}{2a}.

Introduction to Permutations

Problem: In how many ways can Anna, Brenda and Connie stand in a single line for picture taking?

Intuitively, we can count the number of ways by listing. We can list randomly as shown below.

Anna, Brenda, Connie

Brenda, Connie, Anna

Connie, Anna, Brenda

and so on.

Q1: Do you think that listing randomly is a good idea? What are its advantages and its disadvantages?

Listing randomly can solve our problem, if there are only a few things, or in our case persons, to be arranged; however, we can do better than that.  Learning mathematics has taught us to be organized, and has taught us to do things systematically.  Besides, if there are many persons to be arranged, it is hard to keep track if we have listed all possible arrangements. For example, what if David joins the group? Try to list randomly and determine how many possible arrangements are there.

Q2: Before proceeding, can you think of a way to come up with an organized way to list all the possible arrangements?

One possible strategy is to list in alphabetical order. Let us represent Anna, Brenda and Connie by the first letter of their names. If we choose A to occupy the leftmost position, then there are two possible choices for the middle position, namely B and C. That means have AB and AC as all possible arrangements if A is chosen to occupy the leftmost position. Now, in each of the cases, we only have one person left to occupy the rightmost position.  This gives as ABC and ACB as all possible arrangements of the three girls if A were to occupy the leftmost position.

We can also use a tree diagram as shown in Figure 1.  If we choose A to be the person in leftmost position, then the branches B and C mean our possible choices for the middle position. If we have chosen a person who will occupy the middle position, then we are left with only one person to occupy the rightmost position.  Hence, if we choose A to occupy the first position, the only possible arrangements for picture taking are ABC and ACB.

Figure 1- The tree diagram of all the possible arrangements of A, B and C.

But we know that we can also choose B or C as the person who will occupy the leftmost position. This means, that there are 3 possible choices for the first position, 2 possible choices  for the second position and 1 possible choice for the third position (see Figure 1). Hence, there are 3 x 2 x 1 possible arrangements for 3 persons in a single line.

We will denote 3 x 2 x 1 as 3! (3 factorial).  This implies that if we say 5!, we mean 5 x 4 x 3 x 2 x 1 = 120.  In general, n! means n(n-1)(n-2)…(3)(2)(1). Note that the ellipsis symbol … denotes that there are numbers in the sequence that are not shown.  For example, 100(99)(98)…(3)(2)(1), means the product of all integers from 100 all the way down to 1.

Q3: If David joins the group, how many possible arrangements are there?

You may want to solve this problem first before proceeding.

Figure 2 – The tree diagram of all possible arrangments of A, B, C and D.

Looking at the tree diagram, there are four possible choices to occupy the leftmost position, 3 possible choices to occupy the second position, 2 possible choices to occupy  the third position and 1 possible choice to occupy the rightmost position.  Hence there are 4! = 4 x 3 x 2 x 1 = 24 possible arrangements.

By now, you would have realized that the number of arrangements or the number of permutations of n persons on a single line for picture taking is n!. We will denote it as P(n,n) orthe permutations of n objects taken n at a time. We sayn objects taken n at a time because we have the choice to choose numbers less than n to be arranged.  For example, we can choose A and C from A, B, C and D .  This means that we a permutation of 4 objects taken 2 at a time. In general, we describe this type of permutation as permutations of n objects taken k at a time and write P(n,k).

Let us see what happens to our computation with P(4,2). Since there are 4 possible choices for the first choice, and 3 choices for the second position, therefore, there are 4 x 3 possible permutations.  This is the same as removing the smallest two factors by division. If we do this, we come up with the following computation:

If we list the elements of P(4,2), we have the following: AB, BA, AC, CA, AD, DA, BC, CB, BD, DB, CD, and DC. Indeed, we have 12 possible arrangements.

With our findings above, let us try to perform a few more computations and see if we can find a pattern.

Therefore, by looking at the pattern, we can conclude that the number of permutations of n things taken k at a time described by the formula

You may want to read  Introduction to Combinations, the continuation of this post.

1 28 29 30 31