CS206 -Discrete Mathematics II Instructor: Chitoor V.Srinivasan PROBLEM SET 3 SOLUTIONS
(a). Let be the number of
permutations of a set with
n elements. Clearly, . The first element can be
chosen
in n ways, and the remaining n-1 elements can be arranged in
ways. Thus, .
(b). .
Let be the number of ways of
getting stamps valued
n cents. The initial conditions are, , and
for all other i from 0 through 9. Stamps for n
cents may be made up by adding a 10 cent stamp to some stamp(s) totalling
(n-10) cents, a 6 cent stamp to some stamp(s) totalling (n-6) cents, or a 4
cent stamp to some stamp(s) totalling (n-4) cents. Thus, .
(a).
Since , ,
(b).
(c).
From the formula, .
There are 200 integers divisible by 5,
divisible by 7, and which are
divisible by both 5 and 7. The answer is 1,000 minus the number
of integers which are divisible by 5 or 7, which is 1000 - (200 + 142 - 28)
= 686.
The answer is the number that are divisible by 3 minus the number
that divisible by both 3 and 7 which is = 333,333
- 47,619 = 285,714
The largest integer n such that
is 31.
The largest integer m such that
is 10.
The number of integers less than 1000 which are both squares and cubes
is 3, since . Hence, the answer is
(31 + 10 - 3) = 38.
Consider fish and
rat as single tokens. The number of
permutations containing fish is (26 - 4 + 1)! = 23!,
the number
of permutations containing the token rat is similarly,
(26 - 3 +
1)! = 24!, and the number of permumations containing both
fish
and rat is (26 - 7 + 2)! = 21!.
The total number of permutations not containing fish or
rat is, the total number of permutations of the 26 letters
minus the number of permutations containing fish or
rat.
This is 26! - (23! + 24! - 21!).
Let for
be the seven sets.
There will be seven singleton terms, , C(7,2)
double terms , C(7,3) triples
, C(7,4) quadruples and C(7,5) quintuples. For
j > 5 all intersections of j sets will be empty. Hence, the
answer is .
This is minus the total number of bit strings that
do contain four consecutive 1's. The bit strings that do contain 4
consecutive ones are
Hence, the answer is .
Note that finding the number of length n bit strings not containing 4
consecutive 1s is in general hard to solve for arbitrary n 6.