1.
State precisely the following rules. Be sure to set up any notation that is required.
-
Product Rule
-
Sum Rule
-
Principle of Inclusion-Exclusion
-
Division Rule
Exercises 4.1.6 Exercises
2.
How many bit strings of length eight contain exactly three 0s ? Hint: Think about choosing locations for the 0s.
3.
How many answer keys are possible for a twenty question multiple choice test, where each question has exactly six choices?
4.
Suppose there are \(350\) undergraduates in an auditorium. Of these, \(220\) are computer science majors, \(147\) are math majors, and \(51\) are double majoring in computer science and math. How many are neither computer science nor math majors?
5.
Let \(A=\{a, b, c, d\}\text{,}\) and let \(N = \{1, 2, 3, 4, 5, 6, 7\}\text{.}\)
-
How many functions are there from \(A\) to \(N\text{?}\) How many functions are there from \(N\) to \(A\text{?}\)
-
How many injective functions are there from \(A\) to \(N\text{?}\) How many injective functions are there from \(N\) to \(A\text{?}\)
-
How many surjective functions are there from \(A\) to \(N\text{?}\) It is a trickier problem to determine the number of surjective functions from \(N\) to \(A\text{.}\)
6.
Suppose a multiple choice exam consists of 20 questions, each with choices A, B, C, D.
-
How many possible answer keys are there?
-
In how many ways can a student answer the questions on the test, if the student answers every question?
-
In how many ways can a student answer the questions on the test, if the student student can leave answers blank?
7.
A particular brand of shirt comes in a variety of colors (red, green, blue, black, pink, orange, purple) and sizes (XS, S, M, L, XL). How many different types of shirts are there?
8.
How many license plates can be made using either three uppercase English letters (A--Z) followed by three digits (0--9) or four uppercase English letters (A--Z) followed by two digits (0--9)?
9.
In how many ways can Alice arrange six of her dolls in a row if she has twenty-three dolls?
10.
In how many ways can a photographer at a wedding arrange five people in a row from a group of twenty people, given that the bride must be in the picture?
11.
In how many ways can Alice arrange twelve of her fifty-four books on a shelf, given that she must include Strangers Have the Best Candy and The Joy of Chickens?
12.
Each user on a computer system has a password, where each character is an uppercase letter (A--Z) or a digit (0--9).
-
How many possible 8 character passwords are there?
-
How many possible 8 character passwords are there that do not use any digits?
-
How many possible 8 character passwords are there, if each password must contain at least one digit?
13.
14.
Let \(f\) be a bijection from the set of positive rational numbers \(\QQ_{>0}\) to the set of positive integers \(\NN=\ZZ_{>0}\text{.}\) Use \(f\) to construct a bijection from \(\QQ\) to \(\ZZ\text{.}\) Use this to fill in the gap in the proof in Theorem 4.1.1.6.
Hint: Extend the domain of \(f\) to be \(\QQ\text{:}\) For a positive rational number \(r\) you know \(f(r)\text{.}\) What is a reasonable choice to pick to define \(f(-r)\) ?
15.
Let \(A\) and \(B\) be sets and \(n\in\NN\cup\{0\}\text{.}\) Complete the definitions.
-
We say \(A\) is finite when …
-
We say \(A\) is infinite when …
-
We say \(A\) is countable and infinite when…
16.
Recall the Definition of Cartesian power.
-
Prove that the set \(\NN^2=\NN\times\NN=\{(a,b)\mid a\in\NN\land b\in\NN\}\) is countable.
