Page 455 - Discrete Mathematics and Its Applications

434 6 / Counting

repetition allowed from S, formed by subtracting c) the balls are unlabeled, but the boxes are labeled?
k − 1 from the kth element.] d) both the balls and boxes are unlabeled?
c) Conclude that there are C(n + r − 1,r) r- 60. Suppose that a basketball league has 32 teams, split into
combinationswithrepetitionallowedfromasetwithn two conferences of 16 teams each. Each conference is
elements. split into three divisions. Suppose that the North Central
50. How many ways are there to distribute five distinguish- Division has five teams. Each of the teams in the North
able objects into three indistinguishable boxes? Central Division plays four games against each of the
51. How many ways are there to distribute six distinguishable other teams in this division, three games against each of
objects into four indistinguishable boxes so that each of the 11 remaining teams in the conference, and two games
the boxes contains at least one object? against each of the 16 teams in the other conference. In
52. How many ways are there to put five temporary employ- how many different orders can the games of one of the
ees into four identical offices? teams in the North Central Division be scheduled?
53. How many ways are there to put six temporary employ- ∗ 61. Suppose that a weapons inspector must inspect each of
ees into four identical offices so that there is at least one five different sites twice, visiting one site per day. The
temporary employee in each of these four offices? inspector is free to select the order in which to visit these
54. How many ways are there to distribute five indistinguish- sites, but cannot visit site X, the most suspicious site, on
able objects into three indistinguishable boxes? two consecutive days. In how many different orders can
the inspector visit these sites?
55. How many ways are there to distribute six indistinguish-
able objects into four indistinguishable boxes so that each 62. How many different terms are there in the expansion of
n
of the boxes contains at least one object? (x 1 + x 2 + ··· + x m ) after all terms with identical sets
56. How many ways are there to pack eight identical DVDs of exponents are added?
into five indistinguishable boxes so that each box contains ∗ 63. Prove the Multinomial Theorem: If n is a positive inte-
at least one DVD? ger, then
57. How many ways are there to pack nine identical DVDs n
into three indistinguishable boxes so that each box con- (x 1 + x 2 + ··· + x m )
tains at least two DVDs? n 1 n 2
n m
= C(n; n 1 ,n 2 ,...,n m )x x ··· x m ,
58. How many ways are there to distribute five balls into 1 2
n 1 + n 2 + ··· + n m = n
seven boxes if each box must have at most one ball
in it if where
a) both the balls and boxes are labeled? n!
C(n; n 1 ,n 2 ,...,n m ) =
b) the balls are labeled, but the boxes are unlabeled? n 1 ! n 2 !··· n m !
c) the balls are unlabeled, but the boxes are labeled? is a multinomial coefficient.
d) both the balls and boxes are unlabeled? 4
64. Find the expansion of (x + y + z) .
59. How many ways are there to distribute five balls into three 65. Find the coefficient of x y z in (x + y + z) .
3 2 5
10
boxes if each box must have at least one ball in it if
66. How many terms are there in the expansion of
a) both the balls and boxes are labeled?
b) the balls are labeled, but the boxes are unlabeled? (x + y + z) 100 ?
6.6 Generating Permutations and Combinations

Introduction

Methods for counting various types of permutations and combinations were described in the
previous sections of this chapter, but sometimes permutations or combinations need to be gener-
ated, not just counted. Consider the following three problems. First, suppose that a salesperson
must visit six different cities. In which order should these cities be visited to minimize total
travel time? One way to determine the best order is to determine the travel time for each of the
6!= 720 different orders in which the cities can be visited and choose the one with the smallest
travel time. Second, suppose we are given a set of six positive integers and wish to find a subset
of them that has 100 as their sum, if such a subset exists. One way to find these numbers is to
6
generate all 2 = 64 subsets and check the sum of their elements. Third, suppose a laboratory
has 95 employees. A group of 12 of these employees with a particular set of 25 skills is needed
for a project. (Each employee can have one or more of these skills.) One way to find such a