Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8 Teachers 
Basic Counting Techniques 







Here we conceptualize some counting strategies that culminate in extensive use and application of permutations and combinations. The questions raised all require that we count something, yet each involves a different approach.
If I order one vegetable from the menu at Blaise's Bistro, 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 an important counting 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. Necessary Condition: No 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? Try to write that modification.
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 
Take note of the enumeration process used in the table. How could you describe it in words?
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 another counting principle to describe this 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 n*m ways to complete the task. Necessary 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.
This above discussion exemplifies the concept of another basic counting strategy.
A linear arrangement of elements for which the order of the elements must be taken into account. 
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!.
A compact representation for the multiplication of consecutive integers. We use n! to reresent the product n(n1)(n2)...(2)(1), where n is some positive integer. 
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, or permutations, 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. The questions help illustrate the difference between a permutation and a combination.
A collection of elements whose order does not matter. 
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
If r elements are to be collected or arranged from a set of n elements, then the number of combinations of n elements taken r at a time, C(n,r), related to the number of permutations of n elements taken r at a time, P(n,r), according to the equation 
How many ways are there to arrange 5 children at a round table?
If we consider the case in a linear fashion,
we have P(5,5) = 5! arrangements. Now extend this to a circle:
Notice that in each of these cases, the same people are sitting next to each other. Although there has been a changea rotationabout the table, the five children are still in the same positions relative to each other. How many ways are there to rotate the unique linear relationship ABCDE ? There are five such ways, all pictured in the drawing.
Thus we have 5! unique linear arrangements of the children, but we can group those so each group has 5 arrangements that show the children in the same position relative to each other. Therefore, we have 5!/5 = 4! circular permutations of the five children.
What if we arrange in a circle an relement subset from an nelement set? Suppose we arrange 3 of the 5 children. In the linear case, there are P(5,3) = 60 arrangements, but we can group those so each group has 3 arrangements that show the children in the same position relative to each other. Therefore, we have P(5,3)/3 = 5!/(2!*3) circular permutations of the five children into 3children subsets.
In general,
A circular permutation is a circular arrangement of elements for which the order of the elements must be taken into account. In general:






