Page 454 - Discrete Mathematics and Its Applications

6.5 Generalized Permutations and Combinations 433

25. How many positive integers less than 1,000,000 have the 41. How many ways are there to deal hands of seven cards to
sum of their digits equal to 19? each of five players from a standard deck of 52 cards?
26. How many positive integers less than 1,000,000 have ex- 42. In bridge, the 52 cards of a standard deck are dealt to four
actly one digit equal to 9 and have a sum of digits equal players. How many different ways are there to deal bridge
to 13? hands to four players?
43. How many ways are there to deal hands of five cards to
27. There are 10 questions on a discrete mathematics final
each of six players from a deck containing 48 different
exam. How many ways are there to assign scores to the
cards?
problems if the sum of the scores is 100 and each question
is worth at least 5 points? 44. In how many ways can a dozen books be placed on four
distinguishable shelves
28. Show that there are C(n + r − q 1 − q 2 − ··· − q r a) if the books are indistinguishable copies of the same
−1,n − q 1 − q 2 − ··· − q r ) different unordered selec-
title?
tions of n objects of r different types that include at b) if no two books are the same, and the positions of the
least q 1 objects of type one, q 2 objects of type two,..., books on the shelves matter? [Hint: Break this into
and q r objects of type r.
12 tasks, placing each book separately. Start with the
29. How many different bit strings can be transmitted if the sequence 1, 2, 3, 4 to represent the shelves. Repre-
string must begin with a 1 bit, must include three ad- sent the books by b i , i = 1, 2,..., 12. Place b 1 to the
ditional 1 bits (so that a total of four 1 bits is sent), right of one of the terms in 1, 2, 3, 4.Then successively
must include a total of 12 0 bits, and must have at least place b 2 ,b 3 ,..., and b 12 .]
two 0 bits following each 1 bit?
45. How many ways can n books be placed on k distinguish-
30. How many different strings can be made from the letters able shelves
in MISSISSIPPI, using all the letters? a) if the books are indistinguishable copies of the same
31. How many different strings can be made from the letters title?
in ABRACADABRA, using all the letters? b) if no two books are the same, and the positions of the
32. How many different strings can be made from the letters books on the shelves matter?
in AARDVARK, using all the letters, if all three As must 46. A shelf holds 12 books in a row. How many ways are
be consecutive? there to choose five books so that no two adjacent books
are chosen? [Hint: Represent the books that are chosen by
33. How many different strings can be made from the letters
bars and the books not chosen by stars. Count the number
in ORONO, using some or all of the letters?
of sequences of five bars and seven stars so that no two
34. How many strings with five or more characters can be bars are adjacent.]
formed from the letters in SEERESS?
∗ 47. Use the product rule to prove Theorem 4, by first placing
35. How many strings with seven or more characters can be objects in the first box, then placing objects in the second
formed from the letters in EVERGREEN? box, and so on.
36. How many different bit strings can be formed using ∗ 48. Prove Theorem 4 by first setting up a one-to-one cor-
six 1s and eight 0s? respondence between permutations of n objects with n i
37. A student has three mangos, two papayas, and two kiwi indistinguishable objects of type i, i = 1, 2, 3,...,k, and
fruits. If the student eats one piece of fruit each day, and the distributions of n objects in k boxes such that n i ob-
only the type of fruit matters, in how many different ways jects are placed in box i, i = 1, 2, 3,...,k and then ap-
can these fruits be consumed? plying Theorem 3.
∗ 49. In this exercise we will prove Theorem 2 by set-
38. A professor packs her collection of 40 issues of a mathe-
matics journal in four boxes with 10 issues per box. How ting up a one-to-one correspondence between the set
many ways can she distribute the journals if of r-combinations with repetition allowed of S =
{1, 2, 3,...,n} and the set of r-combinations of the set
a) each box is numbered, so that they are distinguish- T ={1, 2, 3,...,n + r − 1}.
able?
a) Arrange the elements in an r-combination, with rep-
b) the boxes are identical, so that they cannot be distin-
guished? etition allowed, of S into an increasing sequence
x 1 ≤ x 2 ≤ ··· ≤ x r . Show that the sequence formed
39. How many ways are there to travel in xyz space from the
by adding k − 1tothe kth term is strictly increasing.
origin (0, 0, 0) to the point (4, 3, 5) by taking steps one
Conclude that this sequence is made up of r distinct
unit in the positive x direction, one unit in the positive y
elements from T .
direction, or one unit in the positive z direction? (Moving b) Show that the procedure described in (a) defines
in the negative x, y,or z direction is prohibited, so that a one-to-one correspondence between the set of
no backtracking is allowed.) r-combinations, with repetition allowed, of S and
40. How many ways are there to travel in xyzw space from the r-combinations of T.[Hint: Show the corre-
the origin (0, 0, 0, 0) to the point (4, 3, 5, 4) by taking spondence can be reversed by associating to the r-
steps one unit in the positive x, positive y, positive z,or combination {x 1 ,x 2 ,...,x r } of T , with 1 ≤ x 1 <
positive w direction? x 2 < ··· <x r ≤ n + r − 1, the r-combination with