Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

πŸ”—

Section 20.3 Multiplication rule

πŸ”—

Worked Example 20.3.1. Counting a small Cartesian product.

πŸ”—
What is |AΓ—B| for A={0,1,2,3} and B={βˆ’1,0,1}?
Solution.
We can solve this by just writing out the elements of AΓ—B and counting them.
AΓ—B={(0,βˆ’1),(0,0),(0,1),(1,βˆ’1),(1,0),(1,1),={(2,βˆ’1),(2,0),(2,1),(3,βˆ’1),(3,0),(3,1)}
So |AΓ—B|=12.
πŸ”—

Worked Example 20.3.2. Counting a large Cartesian product.

πŸ”—
What is |CΓ—D| for C={a,b,c,…,z} and D={0,1,2,β‹―,99}?
Solution.
Writing out all the elements of CΓ—D and then counting them all seems like a lot of work. Instead, using our experience from Worked Example 20.3.1, notice that we usually perform the task of writing the elements of a Cartesian product in a pattern to make sure we get them all. One-by-one we pick a single element of the first set C, and pair it up with every element of the second set D. From this pattern we see that for each c∈C, there are |D| elements of CΓ—D with c as the first coordinate, and there are |C| such groupings of elements from CΓ—D. So we arrive at
|CΓ—D|=|C|β‹…|D|=26β‹…100=2600.
πŸ”—

Checkpoint 20.3.3.

πŸ”—
For sets X and Y, define an equivalence relation on XΓ—Y whose equivalence classes partition XΓ—Y in the manner described in the provided solution to Worked Example 20.3.2. Then describe how the number of classes and the number of objects in each class correspond to |X| and |Y|.
πŸ”—

Warning 20.3.5.

πŸ”—
The Multiplication Rule only applies to consecutive tasks S,T such that the number of ways of performing task T is independent of the choice made in performing task S.
πŸ”—

Example 20.3.6. Counting Cartesian product elements by constructing an arbitrary element.

πŸ”—
To create a specific example of an element from AΓ—B, we must first choose an element of A to be the first coordinate (task S), then choose an element of B to be the second coordinate (task T). There are m=|A| ways to perform task S and n=|B| ways to perform task T. Therefore, the Multiplication Rule says there are mn ways to construct an element of AΓ—B, which means |AΓ—B|=mn.
πŸ”—

Example 20.3.7. Choosing candidates.

πŸ”—
Suppose you are a casting director and need to select both a primary actor and an understudy for the lead role in a play. If n actors audition for the role, then there are n different ways to select the primary actor. Once this choice is made, there remain nβˆ’1 different ways to the select the understudy. Hence there are n(nβˆ’1) ways to cast the role.
πŸ”—
Now, the actual pool of candidates for understudy will differ based on which actor is offered the lead role. However, no matter who is chosen for the lead, the number of remaining candidates for understudy is the same.
πŸ”—

Example 20.3.9. Cardinality of Cartesian product of many sets.

πŸ”—
πŸ”—
If A1,A2,…,Am are finite sets with |Aj|=mj, then
|A1Γ—A2Γ—β‹―Γ—Aβ„“|=m1m2β‹―mβ„“.
πŸ”—

Worked Example 20.3.10. Words of a given length.

πŸ”—
Recall that, given alphabet Ξ£ and number n∈N, Ξ£nβˆ— is the set of words of length n. If |Ξ£|=m, what is |Ξ£nβˆ—|?
Solution.
To construct a specific example word w∈Σnβˆ—, there are:
  • m ways to choose the first letter,
  • m ways to choose the second letter,
  • …,
  • m ways to choose the nth letter.
So there are
mβ‹…mβ‹…mβ‹…β‹―β‹…m⏟n factors=mn
ways to construct w. We conclude |Ξ£nβˆ—|=mn.
πŸ”—

Worked Example 20.3.11. Words with no repeated letters.

πŸ”—
Suppose |Ξ£|=5. How many words in |Ξ£5βˆ—| have no repeated letters? (That is, in which no two letters are the same?)
Solution.
To construct a specific example word w∈Σ5βˆ— in which no two letters are the same, there are
  • 5 ways to choose the first letter,
  • 4 remaining ways to choose the second letter,
  • 3 remaining ways to choose the third letter,
  • 2 remaining ways to choose the fourth letter, and
  • only 1 remaining way to choose the last letter.
So there are
5β‹…4β‹…3β‹…2β‹…1=120
ways to construct w.
Similar to Example 20.3.7, while the actual pool of candidates for the next letter at each step will differ based on which letters have been chosen already, the number of remaining letters is always independent of which letters have actually been chosen so far. So the Multiplication Rule can be applied to this problem exactly as we have applied it.
πŸ”—

Worked Example 20.3.12. Palindromes.

πŸ”—
Let Ξ£={a,b,c,…,y,z}. How many palindromes w with 3≀|w|≀6 are there in Ξ£βˆ—?
Solution.
Break into cases based on the length of w.

Case |w|=3.

Once we choose the first letter, the last is chosen for us, but we are still free to choose the middle letter. So there are 262 palindromes of length 3.

Case |w|=4.

Once we choose the first two letters, the last two are chosen for us. So there are also 262 palindromes of length 4.

Case |w|=5.

Once we choose the first two letters, the last two are chosen for us, but we are still free to choose the middle letter. So there are 263 palindromes of length 5.

Case |w|=6.

Once we choose the first three letters, the last three are chosen for us. So there are also 263 palindromes of length 6.

Total.

Applying the Addition Rule to these non-overlapping cases, we obtain
262+262+263+263=262(1+1+26+26)=54β‹…262=36,504
as the number of palindromes length 3 to 6.
πŸ”—

Worked Example 20.3.13.

πŸ”—
Set A={a,b,c} and B={0,1,2,3,4}. How many functions A→B exist? How many of these are injections? How many are surjections?
Solution.

Number of functions.

A function f:A→B can be constructed in three steps: choose f(a), then choose f(b), then choose f(c). Each of the steps can be carried out in |B|=5 ways. So the number of functions is 53=125.

Number of injections.

An injection f:Aβ†ͺB can be constructed in three steps: choose f(a), then choose f(b) to be different from f(a), then choose f(c) to be different from both f(a) and f(b). First step has |B|=5 choices. Second step has |Bβˆ–{f(a)}|=4 choices. Third step has |Bβˆ–{f(a),f(b)}|=3 choices. So the number of injections is 5β‹…4β‹…3=60.

Number of surjections.

Suppose f:A→B. Since |A|=3, the largest that |f(A)| can be is 3, which occurs when f is injective. However, even in such a largest case it is still smaller then |B|, so no surjections exist. That is, the number of surjections is 0.
<Prev^TopNext>