1. COMBINATORIAL
ARGUMENTS 1.1. CLASSICAL MODELS 1.1.1. When rolling n dice, the probability that the sum is even is 1/2. No matter what is rolled on the first n - 1 dice, the last die has three even values and three odd values, so in each case the probability of ending with an even total is 1/2. 1.1.2. There are (';)G) rectangles with positive area formed by segments in a grid of m horizontal lines and n vertical lines. Positive area requires two distinct horizontal boundaries and two distinct vertical boundaries. 1.1.3. There are (r;s)2F58 words consisting of r consonants and s vowels. There are (r;s) ways to allocate the positions to consonants and vowels and then 2F58 ways to fill those positions. 1.1.4. There are (3;) outcomes of an election with 30 voters and four candi
dates, (3;) - 4(1a7} with no candidate having more than half of the votes. If the votes are considered distinct, then there are 430 outcomes. However, votes go into a ballot box, so an outcome is determined just by the num
ber of votes for each candidate. Thus we want the number of nonnegative integer solutions to x1 + x2 + x3 + x4 = 30, which is (30;!;1 ). When one candidate receives at least 16 votes, the outcomes are the ways to distribute the remaining 14 votes arbitrarily, since votes are in
distinguishable. Only one candidate can have a majority, but that can be any one of the four, so there are 4(137) outcomes we exclude.
1.1.5. For n E N, the expression (n5 -5n3 + 4n)/120 is a integer. Since n5-5n3+4n = n(n2-l)(n2-4) = (n+2)(n+l)n(n-l)(n-2), the expression equals (n;2), which is the number of was to choose five objects from a set of size n + 2. This by definition is an integer. 1.1.6. 13!40! orderings of a deck of cards such that the spade suit appears
consecutively. There are 13! ways to order the spade suit and 39! ways to Combinatorial Mathematics, 1e Douglas B. West
Solution Manual, For Complete File, Download link at the end of this File Section 1.1: Classical Models 2
order the remaining cards. There are then 40ways to insert the ordered
spade suit among the other cards. Alternatively, condense the spade suit
toasingle item, order the items in40! ways, and the expand the spade
into 13!orderings ofthe spade suit.
1.1.7. The probability ofhaving atleast three cards with thesame rank in
asetoffive ordinary cards is aw: Among five cards, only one rank can
appear at least three times; pick itin13ways. When all four cards ofthis
rank appear, there are 48ways topick the remaining card. When only
three appear, there arefour ways to pick the missing suit ofthis rank and
(4)ways to pick the other two cards. Hence there are 13-48-(1+4-47/2)
suitable sets offive cards. The desired probability isthe ratio ofthis to
(°*). Canceling factors in434895120 yields theclaimed probability.
1.1.8. From astandard 52-card deck, There are 13+ -304 sets ofsixcards
having atleast one card inevery suit. Wemay have three cards in one suit
and one ineach other in 4:(3138 ways. Wemayhave two cards ineach
oftwosuits andonecard intheother twoin(2)(23)°182 ways. These are
the only choices; wesum them.
1.1.9. There are 10:9-8-142 integers from 0to99,999 inwhich each digit
appears atmost twice (counting leading Osasappearances. Consider cases
byhow many different digits are used. There are 10,5) integers using five
digits. There are 10(>)93)integers using four digits; first pick and place
the repeated digit. When three digits are used, two areused twice; hence
the number of integers ofthis type is10:5-9- (5)-8.Summing the three
cases yields the answer.
1.1.10. There are 11()(*)distinguishable ways toorder the letters of“Mis-
sissippi’. Choosing positions forthe types ofletters instages, always the
number ofways todothe next stage does not depend onhow the previous
stages were done. Weplace “M”in 11ways, then choose four positions for
“i”among the remaining 10in()ways, then choose four positions for
“9 6 ae)
s”among theremaining 6in (7)ways, theput “p”intheremaining two
positions. The rule ofproduct then yields the answer.
1.1.11. From four colors ofmarbles, there are (3) distinguishable ways to
have 12marbles. There are4!”ways tohave 12ofthemarbles inarow. For
distinguishable selections with repetition, weuse the multiset formula:
(en *).The number of ways toarrange amultiset depends onthe num-
ber ofelements ofeach type. However, when weput the elements inarow
wearejust making words: each position may have one ofthe four types,
and allsuch words are distinguishable. 3 Chapter 1:Combinatorial Arguments
1.1.12. Ifeach New York City resident has ajar of100 coins chosen from
five types, then some two residents have equivalent jars. The number of
distinguishable jars ofcoins isthe number of multisets ofsize 100 from
fivetypes. Using theformula ary forselections ofkelements from n
types, the value ison ,which equals 4,598,126. Without being precise,
cancelling factors yields 13-103-34-101, which is clearly less than 5-10°.
Since New York City has more than 7-10° residents, the claim follows.
1.1.13. When kiseven, there are2*/2-! compositions ofkwith every part
even (there arenone when kisodd). Halving each part yields acomposition
ofk/2, and the mapis reversible. There are 2”! compositions ofn.
1.1.14. Families ofsubsets.
a)There are 2”—2!"/2! subsets of[n]that contain atleast one odd num-
ber. There are 2”subsets of [n]. Among these, 2!”/2! subsets are restricted
tothe setofeven numbers. The remainder have atleast one odd number.
b)There are(”{*') k-element subsets of[n]that have notwoconsecu-
tive integers.
Proof 1.When choosing kelements, the remaining n—kmust dis-
tribute among them tohave atleast one between each successive pair
ofchosen elements. Knowing how many go ineach slot determines the
kelements selected. Hence the legal choices correspond tosolutions to
Xo$xXy +--+: +x, =n—k such that x,,...,x4_1 are positive and xo,xz
are nonnegative. Subtracting 1from the variables required tobeposi-
tive transforms these into nonnegative integer solutions ofyo+:::+y,% =
n—2k+1. Bythe selections with repetition model, the number of solu-
tionsis("7At1***1"1) which simplifies to(”"{*").
Proof 2.View the n—k unchosen integers asdots inarow. Wechoose
places forthe selected integers between thedots (and ontheends), but
avoidance ofconsecutive integers requires that nospace is selected twice.
Wehave n—k+1 allowable places and choose kofthem forbars. The bars
now mark thepositions ofkselected numbers.
c)There are n!choices ofsubsets Ag, A,...An of[n]such that ApC
A;C-:-C A,. There are (n+2)”choices such that ApGCAyC--: CAp.
When the sets have distinct sizes, wehave |A;| =7,since allthe sizes are
between 0and n.Hence Ag=@,and the elements of [n]are added one by
one insome order. The n!possible orders correspond tothe chains.
Todetermine achain ofthe second type, itsuffices tospecify foreach
x€[n]the index isuch that xfirst appears inthe chain atA;. Not ap-
pearing atallisalso anoption. Hence there are n+2choices available
foreach x,and the choice made forxisnot restricted bythe choices made
forother elements. Section 1.1: Classical Models 4
1.1.15. The exponent onaprime pintheprime factorization of(*”) isthe
number ofpowers p*ofpsuch that |2n/p*| isodd. Weusethe formula
‘ai Gry Inm!,|m/p| factors aredivisible byp.In|m/p?| ofthese,
wehave anextra factor ofp.In|m/p°|,wehave yet another factor of p,
and soon. Hence the highest power of pthat divides m!is}),., |m/p*|,
When |2n/p*|iseven, thenumber ofmultiples ofp*in[2n] istwice
thenumber in [n];forexample |10/2| =4,and |5/2|=2.When |2n/p* |
isodd, weget one extra: |6/2| =8,but |3/2| =1.The latter case occurs
ifand only iftheremainder ofnupon division byp*isatleast p*/2.
Since the factors ofpinthe factorization ofn!areused (twice) tocan-
celfactors ofpinthefactorization of(2n)!, wethus find that (2n)! keeps
anextra factor ofpforeach kwhere |2n/p*|isodd.
Prime factors of(‘5)and ({}). Aprime pwill beafactor if|2n/p*| is
odd forsome k.Wehave |18/2| =9and |20/4| =5,so2divides both.
Since |18/3| =|20/3] =6and|18/9| =|20/9| =2,3divides neither.
For higher primes, the squares are too big togive anonzero contri-
bution. Wehave |18/5| =3but |20/5| =4,so5divides ()butnot(79).
Since |18/7| =|20/7| =2,7divides neither. However, 11,13,and17
yield 1ineach case, asdoes 19inthe latter case. Hence the prime divisors
of(j)are{2,5,11, 13,17}, andthoseof(7) are{2,11,13,17, 19}.
1.1.16. Given v(a, b)=((,7,)- (3). (451)), there donot exist distinct pairs
(a,b)and (c,d)ofpositive integers such that v(c,d)isamultiple ofv(a,b).
Suppose u(c, d)=xv(a, b).Wehave (5)=x(%), and then
d c\_( ¢ \_,f @ )L, b a\| b c
c-d+1\d}) \d-1) “\b-1) “~“a-b+1\b) a-b+i1\d
c—df(c\ [ ec _,( 2 _2-6 a\a-b[c
d+1\d) \d+1) “\b+1) “b+1\b) b+1\d
Thus (a-—b+1)d =(c—d+1)b and (6+ 1)(c—d) =(d+1)(a— b).The
difference ofthese two equations yields d—a+b =b—c+d, and hence a=
c.Now,since (,°,) =#2(¢) and(,°,) =$4(5), andtheratios of($) to(5)
and (71) to(464) arethesame, wehave a”=a|Thus (d+1)(a —b)=
(6+ 1)(e—d) =(b+1)(a—d). Weobtain (a+1)(d —b)=0,soalsod =b.
1.1.17. There are(%;)(";") lists ofm1sand n0shaving krunsof1s.
Proof 1(case analysis). The number ofruns of0smay bek—1(start
and end with 1s), k+1(start and end with Os), ork(two cases, starting
with Osorwith 1s). Ineach ofthese four cases, forming compositions of
mand nwith the right number of parts completely specifies thelist.
