CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 Counting Strings
(a) How many bit strings of length 10 contain at least five consecutive 0’s?
(b) How many different ways are there to rearrange the letters of DIAGONALIZATION (15 letters with 3 A’s, 3 I’s, 2 N’s, and 2 O’s) without the two N’s being adjacent?
2 Teams and Leaders
Prove the following identities using a combinatorial proof. 1. ∑n n2 = 2n
2. ∑n kn2 = n2n−1 k=1 k n−1
CS 70, Fall 2021, DIS 6B
3 CS70: The Musical
Edward, one of the previous head TA’s, has been hard at work on his latest project, CS70: The Musical. It’s now time for him to select a cast, crew, and directing team to help him make his dream a reality.
(a) First, Edward would like to select directors for his musical. He has received applications from 2n directors. Use this to provide a combinatorial argument that proves the following identity: 2n =
2n + n2 2
(b) Edward would now like to select a crew out of n people, Use this to provide a combinatorial argument
that proves the following identity: n = n−1 + n−1 (this is called Pascal’s Identity) k k−1 k
CS 70, Fall 2021, DIS 6B
(c) There are n actors lined up outside of Edward’s office, and they would like a role in the musical (in-
cluding a lead role). However, he is unsure of how many individuals he would like to cast. Use this to
provide a combinatorial argument that proves the following identity: ∑n kn = n2n−1 k=1 k
(d) Generalizing the previous part, provide a combinatorial argument that proves the following identity: ∑n nk = 2n− j n.
CS 70, Fall 2021, DIS 6B
4 Countability: True or False
(a) The set of all irrational numbers R\Q (i.e. real numbers that are not rational) is uncountable. (b) The set of integers x that solve the equation 3x ≡ 2 (mod 10) is countably infinite.
(c) The set of real solutions for the equation x + y = 1 is countable.
For any two functions f : Y → Z and g : X → Y , let their composition f ◦ g : X → Z be given by f ◦ g = f (g(x)) for all x ∈ X . Determine if the following statements are true or false.
(d) f and g are injective (one-to-one) =⇒ f ◦ g is injective (one-to-one). (e) f is surjective (onto) =⇒ f ◦ g is surjective (onto).
CS 70, Fall 2021, DIS 6B 4