108 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6
Theorem 6.1: Suppose there areMkinds of objects. Then the number of combinations ofrsuch objects is
C(r+M− 1 ,r)=C(r+M− 1 ,M− 1 ).
EXAMPLE 6.1 Find the numbermof nonnegative integer solutions ofx+y+z=18.
We can view each solution, sayx=3,y=7,z=8, as a combination ofr=18 objects consisting of 3a’s,
7 b’s, and 8c’s, where there areM=3 kinds of objects,a’s,b’s, andc’s. By Theorem 6.1,
m=C(r+M− 1 ,M− 1 )=C( 20 , 2 )= 190.6.3Ordered and Unordered Partitions
Suppose a set has 7 elements. We want to find the numbermof ordered partitions ofSinto three cells, say
[A 1 ,A 2 ,A 3 ], so they contain 2, 3, and 2 elements, respectively.
SinceShas 7 elements, there areC(7, 2) ways of choosing the first two elements forA 1. Following this, there
areC(5, 3) ways of choosing the 3 elements forA 2. Lastly, there areC(2, 2) ways of choosing the 2 elements for
A 3 (or, the last 2 elements form the cellA 3 ). Thus:
m=C( 7 , 2 )C( 5 , 3 )C( 2 , 2 )=(
7
2)(
5
3)(
2
2)
=7 · 6
2 · 1·5 · 4 · 3
3 · 2 · 1·2 · 1
2 · 1= 210Observe that
m=(
7
2)(
5
3)(
2
2)
=7!
2! 5!·5!
3! 2!·2!
2! 0!=7!
2! 3! 2!since each numerator after the first is cancelled by a term in the denominator of the previous factor.
The above discussion can be shown to be true in general. Namely:
Theorem 6.2: The numbermof ordered partitions of a setSwithnelements intorcells[A 1 ,A 2 ,...,Ar]where,
for eachi,n(Ai)=ni, follows:
m=n!
n 1 !n 2 !...nr!Unordered Partitions
Frequently, we want to partition a setSinto cells[A 1 ,A 2 ,...,Ar]where the cells are now unordered. The
numbermof such unordered partitions is obtained from the numberm′of ordered partitions by dividingm′by
eachk!wherekof the cells have the same number of elements.
EXAMPLE 6.2 Find the numbermof ways to partition 10 students into four teams[A 1 ,A 2 ,A 3 ,A 4 ]so that
two teams contain 3 students and two teams contain 2 students.
By Theorem 6.2, there arem′= 10 !/( 3! 3! 2! 2 !)=25 200 such ordered partitions.
Since the teams form an unordered partition, we dividem′by 2! because of the two cells with 3 elements
each and 2! because of the two cells with 2 elements each.
Thusm=25 200/( 2! 2 !)=6300.
6.4Inclusion–Exclusion Principle Revisited
LetA 1 ,A 2 ,...,Arbe subsets of a universal setU. Suppose we letskdenote the sum of the cardinalities of
all possiblek-tuple intersections of the sets, that is, the sum of all of the cardinalities
n(Ai 1 ∩Ai 2 ∩···∩Aik)