Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

118 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6

SolvedProblems

ADVANCED COUNTING TECHNIQUES, INCLUSION–EXCLUSION

6.1.A bagel shop sellsM=5 kinds of bagels. Find the numbermof ways a customer can buy: (a) 8 bagels;

(b) a dozen bagels.

Usem=C(r+M− 1 ,r)=C(r+M− 1 ,M− 1 ), that is, Theorem 6.1, since this problem concerns combinations

with repetitions.

(a) Herer=8, som=C( 8 + 4 , 4 )=C( 12 , 4 )=494.

(b) Herer=12, som=C( 12 + 4 , 4 )=C( 16 , 4 )=1820.

6.2. Find the numbermof nonnegative solutions tox+y+z=18 with the conditions thatx≥3,y≥2,z≥1.

Letx′=x−3,y′=y−2 andz′=z−1. Thenmis also the number of nonnegative solutions tox′+y′+z′=12.

As in Example 6.1, this second problem concerns combinations with repetitions withM=3 andr=12. Thus

m=C( 12 + 2 , 2 )=C( 14 , 2 )= 91.

6.3. LetEbe the equationx+y+z=18. Find the numbermof nonnegative solutions toEwith the conditions

thatx<7,y<8,z<9.

LetSbe the set of all nonnegative solutions ofE. LetAbe the set of solutions for whichx≥7, letBbe the set of

solutions for whichy≥8, and letCbe the set of solutions for whichz≥9. Then

m=|AC∩BC∩CC|

As in Problem 6.2, we obtain:

|A|=C( 11 + 2 , 2 )= 78 , |A∩B|=C( 3 + 2 , 2 )= 10

|B|=C( 10 + 2 , 2 )= 66 , |A∩C|=C( 2 + 2 , 2 )= 6

|C|=C( 9 + 2 , 2 )= 55 , |B∩C|=C( 1 + 2 , 2 )= 3

Also,|S|=C( 18 + 2 , 2 )=190 and|A∩B∩C|=0.By the Inclusion–Exclusion Principle,

m= 190 −( 78 + 66 + 55 )+( 10 + 6 + 3 )− 0 = 10

6.4. There are 9 students in a class. Find the numbermof ways: (a) the 9 students can take 3 different tests if

3 students are to take each test; (b) the 9 students can be partitioned into 3 teamsA,B,Cso that each team

contains 3 students,

(a) Method 1: We seek the numbermof partitions of the 9 students into cells containing 3 students.

By Theorem 6.2,m= 9 !/( 3! 3! 3 !)=5040.

Method 2: There areC(9, 3) to choose three students to take the first test; then there areC(6, 3)

ways to choose 3 students to take the second test; and the remaining students take the third test. Thus

m=C( 9 , 3 )C( 6 , 3 )=5040.

(b) Each partition {A,B,C} of the students can be arranged in 3!=6 ways as an ordered partition. By (a),

there are 5040 such ordered partitions. Hencem= 5040 / 6 =840.

6.5. Find the numberNof ways a company can assign 7 projects to 4 people so that each person gets at least

one project.

We want to find the numberNof onto functions from a set withm=7 elements onto a set withn=4 elements.

We use Theorem 6.4:

N= 42 −C( 4 , 1 )( 37 )+C( 4 , 2 )( 27 )−C( 4 , 3 )( 17 )

= 47 − 4 ( 37 )+ 6 ( 27 )− 4 ( 17 )=16 384− 8748 + 768 − 4 = 8400