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

CHAPTER 6 Advanced Counting Techniques, Recursion

6.1Introduction

Here we consider more sophisticated counting techniques and problems. This includes problems involving

combinations with repetition, ordered and unordered partitions, and the Inclusion–Exclusion Principle and the

Pigeonhole Principle.

We also discuss recursion in this chapter.

6.2Combinations with Repetitions

Consider the following problem. A bakery makes onlyM=4 kinds of cookies: apple (a), banana (b),

carrot (c), dates (d). Find the number of ways a person can buyr=8 of the cookies.

Observe that order does not count. This is an example of combinations with repetitions. In particular, each

combination can be listed with thea’s first, then theb’s, then thec’s, and finally thed’s. Four such combinations

follow:

r 1 =aa, bb, cc, dd; r 2 =aaa, c, ddd; r 3 =bbbb, c, ddd; r 4 =aaaaa,ddd.

Counting the numbermof such combinations may not be easy.

Suppose we want to code the above combinations using only two symbols, say 0 and 1. This can be done by

letting 0 denote a cookie, and letting 1 denote a change from one kind of cookie to another. Then each combination

will requirer=8 zeros, one for each cookie, andM− 1 =3 ones, where the first one denotes the change from

atob, the second one frombtoc, and the third one fromctod. Thus the above four combinations will be coded

as follows:

r 1 = 00100100100 ,r 2 = 00001101000 ,r 3 = 10000101000 ,r 4 = 00000111000.

Counting the numbermof these “codewords” is easy. Each codeword containsR+M− 1 =11 digits where

r=8 are 0’s and henceM− 1 =3 are 1’s. Accordingly,

M=C( 11 , 8 )=C( 11 , 3 )=

11 · 10 · 9

3 · 2 · 1

= 165

A similar argument gives us the following theorem.

107

Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.