CS 70 Discrete Mathematics and Probability Theory Fall 2021
What is the number of strings you can construct given: (a) n ones, and m zeroes?
(b) n1 A¡¯s, n2 B¡¯s and n3 C¡¯s?
(c) n1,n2,…,nk respectively of k different letters?
2 The Count
(a) How many of the first 100 positive integers are divisible by 2, 3, or 5?
CS 70, Fall 2021, DIS 6A
(b) The Count is trying to choose his new 7-digit phone number. Since he is picky about his numbers, he wants it to have the property that the digits are non-increasing when read from left to right. For example, 9973220 is a valid phone number, but 9876545 is not. How many choices for a new phone number does he have?
(c) Now instead of non-increasing, they must be strictly decreasing. So 9983220 is no longer valid, while 9753210 is valid. How many choices for a new phone number does he have now?
CS 70, Fall 2021, DIS 6A 2
How many 7-digit numbers have no two adjacent digits equal?
How many 5-digit palindromes are there? (A palindrome is a number that reads the same way forwards and backwards. For example, 27872 and 48484 are palindromes, but 28389 and 12541 are not.)
Divisor Graph Colorings
Define G where we have V = {2,3,4,5,6,7,8,9}, and we add an edge between vertex i and vertex j if i divides j, or j divides i.
(a) Draw G.
(b) Explain why we cannot vertex-color G with only 2 colors. (c) How many ways can we vertex-color G with 3 colors?
CS 70, Fall 2021, DIS 6A 3