A Counting Tutorial

Two of the seven students adamantly refuse to be photographed side-by-side. In how many ways can a photographer pose the seven students respecting the students' wishes?

The partners of a second couple announced they do not wish to be photographed side by side. If a photographer honors these two couples wishes, how many ways can the seven students be posed?

Prologue
This tutorial discusses the solution of three counting problems. The techniques discussed exposes secrets that are useful to solve many counting problems.

Are there formulas to remember? Yes! And they should be memorized!

But unlike your past mathematics experiences, substituting numbers into a formula is not the best method to solve counting problems.

A promising approach to solving counting problems is to break the given problem into simpler problems whose solutions lead to the solution of the more difficult given problem. Two fundamental counting principles are discussed. They are helpful in breaking a given problem into simpler problems for solution to the givne problem.

The first of the two fundamental principles is the addition rule.

The addition rule
If there are m tags in an urn and n tags in a second urn then the total number of ways of selecting a tag from the first urn or the second urn is (m+n).

Example: A surgical operation can be performed in 5 ways using one of the old techniques. If the same operation can be performed in 3 ways using modern techniques of lasers and modern imagining techniques then the total number of ways the operation can be performed using an old or a new technique is (5+3).

Another application of the addition rule:
A student must select one book from the library's collection of complexity theory or one book from l collection of Mozart's biographies. The library has 5 books in its complexity collection and it has 20 biographies of Mozart. The addition rule asserts there are (5+20) ways to select a book from one of these two library collections.

To apply the addition rule, one needs urns and tags. Let's consider the first example.
For each old technique, write its name on a tag and place the tag in an urn. Into a second urn, place a tag for each new operating technique bearing the name of a new operating technique. The addition rule says the total number of ways to perform the operation using either, an old or a new technique is (5+3).

To apply the addition rule in the second example, for each complexity book place the book's title on a tag and put the tag in a first urn. Into a second urn, place a tag containing the name of each biography. The addition rule asserts that the total number of ways to select a book from the first collection or the second collection is (5+20).

The addition rule can be used in a different way. Consider this example.

Mary registered her upcoming wedding with Stacy Department Store. Stacy's supplies 147 different plate designs of which 94 of the designs have non-circular plates. Mary likes only circular plates. How many choices does Mary have available through a Stacy's registration?

In this example a tag describes a plate featured at Stacy's. There are 94 tags identifying a non-circular plate. Denote by "n", the number of Stacy's circular plates. By the addition rule, 147=94+n. Hence, there are (147-94) circular plates available to Mary through a Stacy's registration. The two urns are those containing the tags of circular plate designs and containing the tags of non-circular plate designs.

The second fundamental counting principle is a multiplicative rule, hence it is called the product rule.

The product rule
If an urn contains m tags and a second urn contains n tags then there are m*n ways to form a list of two tags, where the first tag in the list comes from the first urn and the second tag in the list comes from the second urn.

A list is a presentation of objects along a line. Lists are ordered. They have a first object, a second object, etc.

Two lists are the same if they have the same names and the names are in the same order. Otherwise, two lists are different.

Example:
Urn 1 contains three tags, each tag bearing one of the digit 1, 2, or 3.
Urn 2 contains two tags. One of the tags is marked "a" and the other tag is marked "b" .

The product rule asserts that there are 3*2=6 two-tagged lists, where the first tag is from Urn 1 and the second tag is from Urn 2.
The six lists are: 1a, 2a, 3a, 1b, 2b, 3b, 1c, 2c, 3c .

A Reminder: The product rule prescribes order within the lists. The first tag of the list is from the Urn 1 and the second tag of the list is from Urn 2. This ordering must be honored.

The above reminder asserts that 1c and c1 are different in that two-tagged list. In fact, c1 cannot occur from the order imposed in the construction of the list.

The two counting rules can be extended to more than two conditions (urns).

Example
Given three urns U1 having three tags, U2 having 4 tags, and U3 having 6 tags. No two urns share a tag. The number of ways of selecting a tag from U1 or U2 or U3 is (3+4+6)=13.

The Extended Addition Rule
Given k urns: U1, U2, ..., Uk. U1 contains n1 tags, U2 contains n2 tags, ..., and Uk contains nk tags such that no two urns share a tag then the total number of ways of selecting a tag from U1 or U2, ..., or Uk is (n1+n2+...+nk).

Here n1 is used to represent the number of tags in the first urn. n2, n3, etc. is similarly defined.

The Extended Product Rule
Given k urns: U1, U2, ..., Uk. U1 contains n1 tags, U2 contains n2 tags, ..., and Uk contains nk tags then the total number of lists of length k with the first tag from U1, the second tag from U2, ..., and the kth tag from Uk is the product n1*n2*...*nk.

Suggestion: Memorize the counting rules. A helpful strategy that aids memorizing the counting rules is to recite them to yourself each time you use them. They are the means through which a problem will be broken into smaller problems that leads to the solution to more complicated problems.

Problem 1: In how many ways can a photographer pose seven students in shoulder-to-shoulder alignment?

How will we find the number of poses of the seven students?

The Strategy:
We associate to each seven-student pose a list. The name of the person in the left most position in the pose is the first name in the list.
The name of the person next to the leftmost position is the second name of the list. Etc. .. and the name of the person in the right most position of the pose is in the seventh position of the list.

Each list gives rise to a pose of the seven students and each pose of the seven students gives rise to a list of seven. Thus to count the number of lists of seven students is the count of the number of poses of the seven students.

We will use the extended product rule to count the number of seven lists with seven names.

How?

Write the name of each student on a tag and place that tag in an urn.

Call the urn containing these seven tags, U1.

Now, select any tag from U1 and place it in the first position of a list. The urn now contains 6 tags. Call this reduced urn, U2.

Select anyone of the six tags from U2 and place it in the second position of the list. The urn now contains 5 tags. Call this reduced urn, U3.

Select any one of the 5 tags from U3 and place it in the third position of the list. The urn now contains 4 tags. Call this reduced urn, U4.

Select any one of the 4 tags from U4 and place it in the fourth position of the list. The urn now contains 3 tags. Call this reduced urn, U5.

Select any one of the 3 tags from U5 and place it in the fifth position of the list. The urn now contains 2 tags. Call this reduced urn, U6.

Select any one of the 2 tags from U6 and place it in the sixth position of the list. The urn now contains 1 tag. Call this reduced urn U7.

Finally place the final tag in U7 in the seventh position of the list.

We have the seven urns needed to apply the extended product rule.
U1 containing 7 tags;
U2 containing 6 tags;
U3 containing 5 tags;
U4 containing 4 tags;
U5 containing 3 tags;
U6 containing 2 tags; and
U7 containing 1 tag.

The extended product rule asserts that the total number of lists of length seven is the product of the number of tags in each urn at the time of the selection. That is, 7*6*5*4*3*2*1 = 5, 040. Hence the total number of possible poses of the seven students is 5040.

Products like 7*6*5*4*3*2*1 occur so often in counting problems, they have been named. They are called factorials. Our answer is 7 - factorial. It is denoted by 7!.

Some others factorials:

2! = 2*1
3! = 3*2* 1 = 6
4! = 4*3*3*1=24
5! = 5*4*3*3*1=120
6! = 6*5*4*3*1=720
7! = 7*6*5*4*3*1=5,040
8! = 8*7*6*5*4*3*1=40,320
9! = 9*8*7*6*5*4*3*1=362,880
10!=10*9*8*7*6*5*4*3*2*1 = 3,628,800.

By convention 1! =1 and 0! - 1.

These numbers grow extremely fast.

The above analysis asserts that there are n! arrangements of n distinguishable objects in a line(a list).

In mathematics, an arrangement of objects in a line is called a permutation.

RECAP: There are n! permutations of n distinguishable objects in a line.

Now let's solve Problem 2.
Two of the seven students adamantly refuse to be photographed side-by-side. In how many ways can a photographer pose the seven students respecting the students' wishes?

To solve this problem, we use the addition rule and the extended product rule. Let' s see how.

Let's agree to call these two students a couple, obviously a warring couple. Each pose of the seven students will be one of two types. The first type shows the couple standing side-by-side. The second type shows the couple standing apart from each other.

How will we find the number of poses showing the requesting students apart?

The Strategy: Subtract the total number of poses showing the couple in the side-by-side alignment from the total number of all the poses, 7! = 5040. (the addition rule)

We use the extended product rule to compute the number of poses in which the partners in the couple are side-by-side.

How do we do this?
Replace the tags of the couple with a blue tag( or a color that is different from all the other tags). This tag represents the position of the couple in a side-by-side alignment within the seven-person pose.

An arrangement of these six tags along a line gives an arrangement of the five students and the couple in a pose. Each one of these arrangements represents two poses of the seven students with the partners in the couple standing side-by-side.

One of these poses shows the female to the right of the male within the couple's position while the other pose shows the male to the right of the female.

There are 6! arrangements of 6 tags in a line. Each arrangement of the six tags represents two poses in which the partners in the couple are interchanged. Thus there are 2* 6! poses in which the warring partners stand side-by-side.
To clarify this statement, consider this six-tag arrangement: P, Q, R, S, T, Blue. where P,Q,R,S,T are students. And Blue represents the couple in a side-by-side alignment. This arrangement represents the two poses:
P, Q, R, S, T, Blue female, Blue male
P, Q, R, S, T, Blue male, Blue female

Therefore there are 7! - 2*6! = 3600 poses showing the warring partners standing apart in the pose.

Remark: Requiring that a couple stands side-by-side is a called a special condition. When solving counting problems having special conditions, attend to the special conditions first.

Let's solve Problem 3.
A second couple announced they do not wish to be photographed side by side. If the photographer honor the two couples wishes, how many ways can the seven students be posed?

This problem has two special conditions; both couples do not wish to be photographed in a side-by-side alignment.

The Strategy: As before, we will use the addition rule to subtract from the total number of unrestricted poses the number of ways the warring couples can be photographed in a side-by-side alignment. Then adjust this difference to get the total number of ways the warring partners can be photographed separately.

There are 2*6! =1440 poses showing the first couple standing side-by-side (see problem 2). Similarly there are 2*6! poses showing the second couple stand side-by-side. This is a total of 4*6! = 2880 poses. But some of these poses are counted twice. How is that possible?

The Adjustment: The condition that the partners in the first couple must stand together does not impose any restrictions upon the second couple. So, within the collection of poses showing the first couple standing together, we find poses in which the partners of the second couple stand together and we find poses in which the partners of the second couple stand apart.

Also, within the collection of poses showing the second couple standing together, we find poses in which the partners of the first couple stand together and poses in which the partners of the first couple stand apart.

Thus the poses in which both couples standing together are counted twice in the 4*6! poses. We must subtract one of the double counts containing.

Now to determine the number of ways both warring couples can be simultaneously photographed in a side-side alignment:

The Strategy: From the urn containing the seven tags, remove the four tags that represent the names of the warring partners. Insert a red tag to represent one of the couples and a blue tag to represent the other couple.

There are now 5 tags in the urn. They can be arranged along a line in 5! = 120 ways. This gives 120 poses containing the couples in a side-by-side alignment with the other three students.

Each one of these arrangements represents 4 different poses in which the couple's partners are interchanged.

For instance, consider the arrangement: P, Blue, Q, Red, R. where P, Q and R are the tags belonging to the three other students and Blue represent the blue tag. That arrangement represents:

P, Blue female, Blue male, Q, Red male, Red female, R
P, Blue male, Blue female, Q, Red male, Red female, R
P, Blue male, Blue female, Q, Red female, Red male, R
P, Blue female, Blue male, Q, Red female, Red male, R

Thus there are 4*5! = 480 poses showing the warring partners standing side-by-side.

But there are 2*6! + 2*6! - 4*5! = 2400 poses containing partners standing side by side. Note the subtraction of the double count..

Hence there are 5040 - 2400= 2640 poses in which the warring partners are standing apart.

Epilogue: The techniques in this tutorial are standard in elementary counting. The reader should practice these ideas. To aid your understanding of these methods reread the analysis, and write it in your own words.

Mozart did not master the piano without learning to the play the scales and practicing them. So it will be with you. Only after studying these techniques and practicing them will you be learn to break a counting problem into smaller problems, and solve the smaller problems to arrive at the result you seek.