Basic Counting Principles: The Product Rule • The Product Rule ○ A procedure can be broken down into a sequence of two tasks. ○ There are n_1 ways to do the first task and n_2 ways to do the second task. ○ Then there are n_1∙n_2 ways to do the procedure. • Example 1 ○ How many bit strings of length seven are there? ○ Since each of the seven bits is either a 0 or a 1, the answer is 2^7 = 128. • Example 2 ○ How many different license plates can be made if ○ each plate contains a sequence of 3 uppercase English letters followed by 3 digits? ○ There are 26 ∙ 26 ∙ 26 ∙ 10 ∙ 10 ∙ 10 = 17,576,000 different possible license plates. • Example 3: Counting Functions ○ How many functions are there from a set with m elements to a set with n elements? ○ A function represents a choice of one of the n elements of the codomain for each of the m elements in the domain ○ The product rule tells us that there are n⋅n⋯n = n^m such functions. • Example 4: Counting One-to-One Functions ○ How many 1-to-1 functions are there from a set with m elements to one with n elements? ○ Suppose the elements in the domain are a_1,a_2,…,a_m. ○ There are n ways to choose the value of a_1 and n−1 ways to choose a_2, etc. ○ The product rule tells us that there are n(n−1)(n−2)⋯(n−m+1) functions. • Example 5: Counting Subsets of a Finite Set ○ Show that the number of different subsets of a finite set S is 2^|S| ○ When the elements of S are listed in an arbitrary order ○ There is a one-to-one correspondence between subsets of S and bit strings of length |S|. ○ When the ith element is in the subset, the bit string has a 1 in the ith position and a 0 otherwise. ○ By the product rule, there are 2^|S| such bit strings, and therefore 2^|S| subsets. • Example 6: Product Rule in Terms of Sets ○ Let A_1,A_2,…,A_m be finite sets ○ The number of elements in the Cartesian product of these sets is the product of the number of elements of each set. ○ The task of choosing an element in the Cartesian product A_1×A_2×…×A_m is done by ○ choosing an element in A_1, an element in A_2 , …, and an element in A_m. ○ By the product rule, it follows that: |A_1×A_2×…×A_m |=|A_1 |⋅|A_2 |⋯|A_m | • Example 7: DNA and Genomes ○ A gene is a segment of a DNA molecule that encodes a particular protein and the entirety of genetic information of an organism is called its genome. ○ DNA molecules consist of two strands of blocks known as nucleotides. ○ Each nucleotide is composed of bases: adenine(A), cytosine(C), guanine(G), thymine(T). ○ The DNA of bacteria has between 〖10〗^5 and 〖10〗^7 links (one of the four bases). ○ Mammals have between 〖10〗^8 and 〖10〗^10 links. ○ So, by the product rule there are at least 4(〖10〗5 ) different sequences of bases in the DNA of bacteria and 4(〖10〗8 ) different sequences of bases in the DNA of mammals. ○ The human genome includes approximately 23,000 genes, each with 1,000 or more links. Basic Counting Principles: The Sum Rule • The Sum Rule ○ If a task can be done either in one of n_1 ways or in one of n_2, ○ where none of the set of n_1 ways is the same as any of the n_2 ways, ○ then there are n_1+n_2 ways to do the task. • Example ○ The mathematics department must choose either a student or a faculty member as a representative for a university committee. ○ How many choices are there for this representative if there are 37 members of the mathematics faculty and 83 mathematics majors and no one is both a faculty member and a student. ○ There are 37 + 83 = 120 possible ways to pick a representative. • The Sum Rule in terms of sets ○ The sum rule can be phrased in terms of sets. ○ |A ∪ B|= |A| + |B| as long as A and B are disjoint sets. ○ Or more generally, § |A_1∪A_2∪…∪A_m |=|A_1 |+|A_2 |+…+|A_m |, when A_i∩A_j=∅ for all i,j Combining the Sum and Product Rule • Example 1 ○ Suppose statement labels in a programming language can be either a single letter or a letter followed by a digit. ○ Find the number of possible labels. ○ Use the product rule: 26 + 26 ∙ 10 = 286 • Example 2: Counting Passwords ○ Each user on a computer system has a password ○ which is 6 to 8 characters long, where each character is an uppercase letter or a digit. ○ Each password must contain at least one digit. ○ How many possible passwords are there? ○ Let P be the total number of passwords ○ Let P_6, P_7, and P_8 be the passwords of length 6, 7, and 8. ○ By the sum rule P=P_6+P_7+P_8. ○ To find each of P_6, P_7, and P_8, we find the number of passwords of the specified length composed of letters and digits and subtract the number composed only of letters. ○ We find that: § P_6 = 〖36〗^6 − 〖26〗^6 = 2,176,782,336 − 308,915,776 =1,867,866,560 § P_7 = 〖36〗^7 − 〖26〗^7 = 78,364,164,096 − 8,031,810,176 = 70,332,353,920 § P_8 = 〖36〗^8 − 〖26〗^8 = 2,821,109,907,456 − 208,827,064,576 = 2,612,282,842,880 ○ Consequently, P=P_6+P_7+P_8 = 2,684,483,063,360. Basic Counting Principles: Subtraction Rule • The Subtraction Rule ○ If a task can be done either in one of n_1 ways or in one of n_2 ways ○ Then the total number of ways to do the task is n_1 + n_2 minus the number of ways to do the task that are common to the two different ways. ○ Also known as, the principle of inclusion-exclusion: ○ |A∪B|=|A|+|B|−|A∩B| • Example: Counting Bit Strings ○ How many bit strings of length eight either start with a 1 bit or end with the two bits 00? ○ Use the subtraction rule. ○ Number of bit strings of length eight that start with a 1 bit: 2^7 = 128 ○ Number of bit strings of length eight that end with bits 00: 2^6 = 64 ○ Number of bit strings of length eight that start with a 1 bit and end with bits 00: 2^5 = 32 ○ Hence, the number is 128 + 64 − 32 = 160. Basic Counting Principles: Division Rule • Division Rule ○ There are n/d ways to do a task if ○ it can be done using a procedure that can be carried out in n ways ○ and for every way w, exactly d of the n ways correspond to way w. • In terms of sets ○ If the finite set A is the union of n pairwise disjoint subsets each with d elements ○ then n = |A|/d. • In terms of functions ○ If f is a function from A to B, where both are finite sets, and for every value y ∈ B there are exactly d values x ∈ A such that f(x)=y, then |B|=|A|/d. • Example ○ How many ways are there to seat four people around a circular table, where two seatings are considered the same when each person has the same left and right neighbor? ○ Number the seats around the table from 1 to 4 proceeding clockwise. ○ There are four ways to select the person for seat 1, 3 for seat 2, 2, for seat 3, and one way for seat 4. ○ Thus there are 4! = 24 ways to order the four people. ○ But since two seatings are the same when each person has the same left and right neighbor, for every choice for seat 1, we get the same seating. ○ Therefore, by the division rule, there are 24/4 = 6 different seating arrangements. Tree Diagrams • Tree Diagrams ○ We can solve many counting problems through the use of tree diagrams, where a branch represents a possible choice and the leaves represent possible outcomes. • Example ○ Suppose that “I Love Discrete Math” T-shirts come in five different sizes: S, M, L, XL, XXL. ○ Each size comes in four colors (white, red, green, and black), except XL, which comes only in red, green, and black, and XXL, which comes only in green and black. ○ What is the minimum number of shirts that the campus book store needs to stock to have one of each size and color available? ○ Draw the tree diagram. The store must stock 17 T-shirts.
