3.2 The Multiplication Principle

Class: CSE 16 Subject: computer-science discrete-math Date: 2024-10-14 Teacher: Prof. Musacchio

Counting

Example 1

• For example, suppose we make a list of length three having the property that the first entry must be an element of the set {a, b, c}, the second entry must be in {5, 7} and the third entry must be in {a, x}. Thus (a, 5, a) and (b, 5, a) are two such lists. How many such lists are there all together?

Example 2

• A non-repetitive list of length 5 is to be made from the symbols A, B, C, D, E, F, G. The first entry must be either a B, C or D, and the last entry must be a vowel. How many such lists are possible?

Example 3

• Start with 0(A) or start with 1(B)
• Find $A\cup B$
  • For this example $A\cup B$ =\ $\varnothing$, $|A\cup B|$ = |A| + |B| = 24

Example 4

• How many 5 bit vectors start or end with zero?
  • A: sequence that starts with 0, |A| = 16
  • B: ” ” end with 0, |B| = 16
  • $A\cap B$ : sequences that start and end with 0, |$A\cap B$| = 8
  • |$A\cup B$| = |A| + |B| - |$A\cap B$ | = 16 + 16 - 8 = 24