Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8 Teachers Spring 1999 







Some Counting Methods


Review Session 1


Proof by Induction


Debrief Assignment #1 

Assignment #2 
During this session we will begin conceptualizing counting strategies that culminate in extensive use and application of permutations and combinations. Today, we refer again to the menu at Blaise's Bistro. The questions that follow all require that we count something, yet each involves a different approach.
+ Addition Principle
If I order one vegetable from the menu, how many vegetable choices does Blaise offer?
Here we select one item from a collection of items. Because there are no common items among the two sets Blaise has called Greens and Potatoes, we can pool the items into one large set. We use addition, here 4+5, to determine the total number of items to choose from.
This illustrates the Addition Principle:
If a choice from Group I can be made in n ways and a choice from Group II can be made in m ways, then the number of choices possible from Group I or Group II is n+m. Condition: None of the elements in Group I are the same as elements in Group II.
This can be generalized to a single selection from more than two groups, again with the condition that all groups, or sets, are disjoint, that is, have nothing in common.
Examples to illustrate the Addition Principle:
Here are three sets of letters, call them sets I, II, and III:
How many ways are there to choose one letter from among the sets I, II, or III? Note that the three sets are disjoint, or mutually exclusive: there are no common elements among the three sets.
Here are two sets of positive integers:
How many ways are there to choose one integer from among the sets A or B? Note that the two sets are not disjoint. What modification can we make to the Addition Principle to accommodate this case? Write that modification.
+ Multiplication Principle
A "meal" at the Bistro consists of one soup item, one meat item, one green vegetable, and one dessert item from the alakarte menu. If Blaise's friend Pierre always orders such a meal, how many different meals can be created?
We can enumerate the meals that are possible, preferably in some organized way to assure that we have considered all possibilities. Here is a sketch of one such enumeration, where {V,O}, {K,R}, {S,P,B,I}, and {L,A,C,F} represent the items to be chosen from the soup, meat, green vegetable, and dessert menus, respectively.
VKSL 
VKPL 
VKBL 
VKIL 

ORIL 
VKSA 
VKPA 
VKBA 
VKIA 
ORIA 

VKSC 
VKPC 
VKBC 
VKIC 
ORIC 

VKSF 
VKPF 
VKBF 
VKIF 
ORIF 
Note and be prepared to describe the enumeration process I have illustrated here.
How else could we complete the count without identifying all possible options? A map or tree to illustrate the enumeration process provides a bridge to such a method.
We have two ways to select a soup item, two ways to select a meat item, four green vegetables to choose from, and four desserts to choose from. The matching of one soup with each meat, then each of those pairs with each of four possible green vegetables, and each of those triples with each of four possible desserts leads to the use of multiplication as a quick way to count all the possible meals we could assemble at Blaise's.
This suggests we use the Multiplication Principle to describe this counting technique:
If a task involves two steps and the first step can be completed in n ways and the second step in m ways, then there are nm ways to complete the task. Condition: The ways each step can be completed are independent of each other.
This can be generalized to completing a task in more than two steps, as long as the condition holds.
Example to illustrate the Multiplication Principle:
Recall our three sets I, II, and III: {a,m,r}, {b,d,i,l,u}, and {c,e,n,t}. Determine the number of threeletter sets that can be created such that one letter is from set I, one letter in from set II, and one letter is from set III. Note that our choice in each set is independent of our choice in the other sets. If necessary, we could enumerate the possible threeletter, or threeelement, sets.
+ Permutations
In how many ways can the letters within just one set, from among I,
II, and III, be ordered? In set I, we have these possibilities:






We use the Multiplication Principle to describe our selection. We have three letters to choose from in filling the first position, two letters remain to fill the second position, and just one letter left for the last position: 3x2x1=6 different orders are possible. Likewise, for set II there are 120 different ways to order the five letters and there are 24 different ways to order the letters in set III.
+ Factorial Notation
This above discussion exemplifies the concept of a permutation
as an ordered arrangement of items. We also point out the
availability of factorial notation to compactly represent the
specific multiplication we just carried out: 3x2x1=3!, 5x4x3x2x1=5!,
and so on. So n(n1)(n2)...(2)(1)=n!.
Example to illustrate use of Permutations:
Almost every morning or evening on the news I hear about the State of Illinois DCFS, the Department of Children and Family Services. I get confused, because our mathematics department has a committee called the Department Faculty Status Committee, or DFSC. Can you see why I'm confused? How many different 4letter ordered arrangements exist for the set of letters {D, F, S, C}?
Thinking of four positions to fill, __ __ __ __ , we have 4 letters to choose from for the first position, 3 for the next, 2 letters for the next position, and 1 choice for the last position. Using the multiplication principle, there are 4x3x2x1=24 different 4letter ordered arrangements for the set of letters {D, F, S, C}.
We can extend this application to consider ordered arrangements of only some of the elements in a set. For example, returning to the beverages menu of Blaise's Bistro. If Blaise will post only four possible soda chocies, how many different ordered arrangements of the four sodas are there?
Thinking of four positions to fill, __ __ __ __, we have 6 sodas to choose from for the first position, 5 for the next, 4 sodas for the next, and 3 sodas for the last position. Using the multiplication principle, there are 6x5x4x3=360 different ways to select and order four of the six sodas on the menu.
In general, we use the notation P(n,r) to represent the number of ways to arrange r objects from a set of n objects. In the first problem above, we determined that P(4,4)=24, and in the second we calculated P(6,4)=360. The general value of P(n,r) is n(n1)(n2)...([n(r1)] or P(n,r)=n(n1)(n2)...(nr+1). Note that n can be any nonnegative integer. Are there any restrictions on the value of r?
There is a step of arithmetic we can apply to the general pattern for P(n,r) to help streamline permutation calculations. In the second line below, we have multiplied by, which is just the value 1 because the numerator and denominator are equal. In the fourth line below we see how the expression can be simplified using factorial notation.
Thus, we have P(6,2)=6!/4! And P(40,8)=40!/32!.
What about P(4,4)? The result above suggests P(4,4)=4!/0!. We already know that P(4,4)=4x3x2x1=4!, So we have 4!=4!/0!. For this to be true, it must be the case that 0!=1. As strange as that may appear, we need 0!=1 in order to maintain consistency within the calculations we wish to carry out.
+ Combinations
What is the distinction between asking these two questions?
(i) In how many ways can a 5card poker hand be dealt?(ii) How many different 5card poker hands exist?
The first question considers the order or arrangement of the cards as they are dealt. In the second question, the end result when dealt 2H,4D,JC,3S,10D in that order is the same as being dealt 4D,3S,JC,10D,2H in that order. In each case, the same 5card poker hand exists.
We found P(52,5) as the solution to the first problem. That is, we arranged 5 objects selected from among 52 cards. For the second question, there are many arrangements that yield the same 5card hand. We need to account for this. Let's consider a simpler problem.
How many ordered arrangements exist for the letters of the set {A,B,C,D,E}?
Using permutations, we have P(5,5) = 5! = 120 ways to arrange the five letters.
How many ordered arrangements are there of 3 items from the 5element set?
We have P(5,3) = 543 = 5!/2! = 60 arrangements. For example, for the three letters {A,B,C} we have these arrangements: ABC, ACB, BAC, BCA, CAB, CBA. This represents 6 of the 60 arrangements, yet each involves the same selection of three letters. Likewise for the three letters {A,C,E}: We have ACE, AEC, CAE, CEA, EAC, ECA.
It seems that for each 3letter subset of {A,B,C,D,E} there are 6 arrangements of the same three letters. This is a helpful observation in exploring the following question:
How many ways can we select three items from the 5element set {A,B,C,D,E} when the order of the three items is disregarded?
One way is to list the unique 3element subsets of {A,B,C,D,E}: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. There are 10 such 3element subsets.
Another way to consider the count is to use the fact that:
(i) there are P(5,3) = 60 ordered arrangements of the 5element set into 3element subsets, and
(ii) within the 60 ordered arrangements, there are 10 groups of 6 arrangements that use the same 3letter subset. That is, 60 ÷ 6 = 10 unique 3element subsets. Using combinatorics notation, we have
In general, we have a way to determine the number of combinations
of n items selected r at a time, where the order of selection or the
arrangement of the r items is not considered:
and we note that
+ Open Questions from Session 1
+ Review Questions
Consider these review questions:

We illustrate the process of proof by induction to show that


+ Process
Step 1: Verify that the desired result holds for n=1.
Here, when 1 is substituted for n in both the left and rightside expressions in (I) above, the result is 1. Specifically
. This completes step 1.
Step 2: Assume that the desired result holds for n=k.
In our example, this means that we assume the sum of the first k positive integers is . It will be helpful to show this as


Step 2 is complete.
Step 3: Use the assumption from step 2 to show that the result holds for n=(k+1).
That is, we want to show that. In other words, show that assuming the result for n=k implies the result for n=(k+1).
Here, we build on the equation presented in (II):
If , adding (k+1) to each side assures us that


The left side of (III) is just the expansion of the expression , that is, the sum of the first (k+1) positive integers.
We are left to show that the right side of (III) is equivalent to , what our formula tells us is the correct sum.
Rewrite the right side of (III) with a common denominator:


Now add numerators and express over the common denominator:


In the numerator of (V), k+1 is common to both terms, so we can factor the numerator, resulting in equivalent form:


Expression (VI) is just the result we sought.
Step 4: Summarize the results of your work.
We have shown by induction that the sum of the first n positive integers can be represented by the expression .
The equation,has practical application any time we seek sums of consecutive positive integers. For example, we can now use the result to conclude that . We can also use the result to show that, for example,.
+ Summary
The induction process relies on a domino effect. If we can show that a result is true from the kth to the (k+1)th case, and we can show it indeed is true for the first case (k=1), we can string together a chain of conclusions: Truth for k=1 implies truth for k=2, truth for k=2 implies truth for k=3, and so on. Pushing the first domino causes all of the remaining dominoes to fall in succession.
+ Practice
Here are practice problems to reinforce the induction process.
1. 
Show that. 
2. 
Show that. 
3. 
Explore patterns in the sumsand so on. Use proof by induction to justify your conjecture. 
4. 
Show that the sum of the first n odd positive integers is . 
With your completed Assignment #1 in hand, we will set aside class time for small groups to compare results and generate solutions to be shared among the class. The text problems in Assignment #1 ought to be straightforward. Note that most of the solutions appear in the back of the text. The solutions to the supplementary problems will be more involved and will likely require discussion. I will collect problems 8c and 16 from Problem Set #1 and all three of those in Supplementary Problem Set A.




