Illinois State University Mathematics Department


MAT 305: Combinatorics Topics for K-8 Teachers



Basic Counting Techniques

The Addition Principle
The Multiplication Principle
Permutations
Combinations
Circular Permutations
Factorial Notation

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.

The Addition Principle

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.

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.

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.

The Multiplication Principle

A "meal" at the Bistro consists of one soup item, one meat item, one green vegetable, and one dessert item from the a-la-karte 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

...and so on to...

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.

The Multiplication Principle

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 three-letter 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 three-letter, or three-element, 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:

amr
arm
mar
mra
ram
rma

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.

Permutation

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(n-1)(n-2)...(2)(1)=n!.

Factorial Notation

A compact representation for the multiplication of consecutive integers. We use n! to reresent the product n(n-1)(n-2)...(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 4-letter 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 4-letter 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(n-1)(n-2)...([n-(r-1)] or P(n,r)=n(n-1)(n-2)...(n-r+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 5-card poker hand be dealt?

(ii) How many different 5-card 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 5-card poker hand exists. The questions help illustrate the difference between a permutation and a combination.

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 5-card 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 5-element 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 3-letter 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 5-element set {A,B,C,D,E} when the order of the three items is disregarded?

One way is to list the unique 3-element subsets of {A,B,C,D,E}: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. There are 10 such 3-element subsets.

Another way to consider the count is to use the fact that:

(i) there are P(5,3) = 60 ordered arrangements of the 5-element set into 3-element subsets, and
(ii) within the 60 ordered arrangements, there are 10 groups of 6 arrangements that use the same 3-letter subset. That is, 60 ÷ 6 = 10 unique 3-element 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

The Relationship Between Permutations and Combinations

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

.

Circular Permutations

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 change--a rotation--about 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 r-element subset from an n-element 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 3-children subsets.

In general,

Circular Permutation

A circular permutation is a circular arrangement of elements for which the order of the elements must be taken into account.

In general:

  • For n elements, there are (n-1)! circular permutations.
  • The number of circular permutations of r-elements taken from an n-element set is P(n,r)/r.


Syllabus
Grades & Grading
Content Notes
Session Outlines
Assignments and Problem Sets
Tests and Quizzes