Homework Assignment

CS 171
Homework Assignment 4m
Given: February 08, 2010 Due: February 10, 2010
This assignment is due by the end of the class on the due date. Unless all problems
carry equal weight, the point value of each problem is shown in [ ]. To receive full credit all
your answers should be carefully justified. Each solution must be the student’s own work.
Assistance should be sought or accepted only from the course staff. Any violation of this
rule will be dealt with harshly.
1. Answer each of the following questions. You don’t need to show your work.
a. How many permutations are there of the word PEPPER?
b. A chess tournament has 10 competitors of which 4 are Russian, 3 are from the United
States, 2 from Britain, and 1 from Brazil. If the tournament result lists just the
nationalities of the players in the order in which they placed, how many outcomes are
possible?
c.
True or False? Ten dogs encounter 8 biscuits. Dogs do not share biscuits! Then
assuming that the dogs are distinguishable, but the biscuits are not, there are
17 8 
different ways that the biscuits can be consumed.
d.
True or False? In the above question if the dogs and the biscuits both are distinguishable then the answer is 108.
e.
True or False? In the above question if neither the dogs nor the biscuits are distinguishable then there is only 1 way in which the biscuits can be consumed.
f. How many non-empty subsets are there of the set
{1,2,… ,n}? Give your answer in
closed form.
g. How many ways are there to place 8 nonattacking identical rooks on a 8
×8 chessboard?
(In chess two rooks can attack one another if and only if they lie in the same row or
the same column of the chess board.)
h. Answer the above question if the rooks are distinguishable.
i. Answer the above question if there is 1 red, 3 blue, and 4 yellow rooks.
j. Consider a group of 50 people. If everyone shakes hand with everyone else, how many
handshakes take place? Your answer must be in a closed form.
k. A committee of 7, consisting of 2 Republicans, 2 Democrats, and 3 Independents, is
to be chosen from a group of 5 Republicans, 6 Democrats, and 4 Independents. How
many committees are possible?

2 Homework Assignment 4m February 08, 2010
l. A student has 3 mangoes, 2 papayas, and 2 kiwi fruits. If the student eats one piece
of fruit each day, and only the type of fruit matters, in how many different ways can
these fruits be consumed?
m. How many different strings can be made from the letters
AARDVARK, using all the
letters, if all three
A’s must be consecutive?
n. How many strings of 10 ternary digits (0
,1,2) are there that contain exactly two 0s,
three 1s, and five 2s?
o. We roll two dice. How many different outcomes are possible if the two dice are
distinct?
p. How many different outcomes are possible if the two dice are identical?
2. A professor packs her collection of 40 issues of a mathematics journal in four boxes
with 10 issues per box. How many ways can she distribute the journals if (a) each box is
numbered, so that they are distinguishable? (b) the boxes are identical?
3. How many 8-permutations are there of the 9 letters of the word addresses?