Part I
Three counting problems
In how many ways can a photographer pose seven students in shoulder-to-shoulder alignment?
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 givnen 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).
The second fundamental counting principle is a multiplicative rule, hence it is called the product rule.
Example: 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, for each complexity book, put its title on a tag and place the tag in an 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 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.
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?
For the solution, follow this link.