1. COMBINATORIAL - 1.1.1. When rolling n dice, the probability tha...

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 2F5 8 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 4 30 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(1 3 7

• outcomes we exclude.

1.1.5. For n E N, the expression (n 5 -5n 3

• 4n)/120 is a integer. Since

n 5 -5n 3 +4n = n(n 2 -l)(n 2 -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 1 / 4

Section1.1:ClassicalModels2

ordertheremainingcards.Therearethen40waystoinserttheordered spadesuitamongtheothercards.Alternatively,condensethespadesuit toasingleitem,ordertheitemsin40!ways,andtheexpandthespade into13!orderingsofthespadesuit.

1.1.7.Theprobabilityofhavingatleastthreecardswiththesamerankin

asetoffiveordinarycardsisaw:Amongfivecards,onlyonerankcan

appearatleastthreetimes;pickitin13ways.Whenallfourcardsofthis rankappear,thereare48waystopicktheremainingcard.Whenonly threeappear,therearefourwaystopickthemissingsuitofthisrankand (4)waystopicktheothertwocards.Hencethereare13-48-(1+4-47/2) suitablesetsoffivecards.Thedesiredprobabilityistheratioofthisto (°*).Cancelingfactorsin434895120yieldstheclaimedprobability.

1.1.8.Fromastandard52-carddeck,Thereare13+-304setsofsixcards havingatleastonecardineverysuit.Wemayhavethreecardsinonesuit

andoneineachotherin4:(3138ways.Wemayhavetwocardsineach

oftwosuitsandonecardintheothertwoin(2)(23)°182ways.Theseare theonlychoices;wesumthem.

1.1.9.Thereare10:9-8-142integersfrom0to99,999inwhicheachdigit

appearsatmosttwice(countingleadingOsasappearances.Considercases byhowmanydifferentdigitsareused.Thereare10,5)integersusingfive digits.Thereare10(>)93)integersusingfourdigits;firstpickandplace therepeateddigit.Whenthreedigitsareused,twoareusedtwice;hence

thenumberofintegersofthistypeis10:5-9-(5)-8.Summingthethree

casesyieldstheanswer.

1.1.10.Thereare11()(*)distinguishablewaystoorderthelettersof“Mis- sissippi’.Choosingpositionsforthetypesoflettersinstages,alwaysthe numberofwaystodothenextstagedoesnotdependonhowtheprevious stagesweredone.Weplace“M”in11ways,thenchoosefourpositionsfor “i”amongtheremaining10in()ways,thenchoosefourpositionsfor “96ae) s”amongtheremaining6in(7)ways,theput“p”intheremainingtwo positions.Theruleofproductthenyieldstheanswer.

1.1.11.Fromfourcolorsofmarbles,thereare(3)distinguishablewaysto have12marbles.Thereare4!”waystohave12ofthemarblesinarow.For

distinguishableselectionswithrepetition,weusethemultisetformula:

(en*).Thenumberofwaystoarrangeamultisetdependsonthenum- berofelementsofeachtype.However,whenweputtheelementsinarow

wearejustmakingwords:eachpositionmayhaveoneofthefourtypes,

andallsuchwordsaredistinguishable. 2 / 4

3Chapter1:CombinatorialArguments

1.1.12.IfeachNewYorkCityresidenthasajarof100coinschosenfrom fivetypes,thensometworesidentshaveequivalentjars.Thenumberof distinguishablejarsofcoinsisthenumberofmultisetsofsize100from fivetypes.Usingtheformulaaryforselectionsofkelementsfromn types,thevalueison,whichequals4,598,126.Withoutbeingprecise, cancellingfactorsyields13-103-34-101,whichisclearlylessthan5-10°.SinceNewYorkCityhasmorethan7-10°residents,theclaimfollows.

1.1.13.Whenkiseven,thereare2*/2-!compositionsofkwitheverypart even(therearenonewhenkisodd).Halvingeachpartyieldsacomposition ofk/2,andthemapisreversible.Thereare2”!compositionsofn.

1.1.14.Familiesofsubsets.a)Thereare2”—2!"/2!subsetsof[n]thatcontainatleastoneoddnum- ber.Thereare2”subsetsof[n].Amongthese,2!”/2!subsetsarerestricted tothesetofevennumbers.Theremainderhaveatleastoneoddnumber.b)Thereare(”{*')k-elementsubsetsof[n]thathavenotwoconsecu- tiveintegers.Proof1.Whenchoosingkelements,theremainingn—kmustdis- tributeamongthemtohaveatleastonebetweeneachsuccessivepair ofchosenelements.Knowinghowmanygoineachslotdeterminesthe kelementsselected.Hencethelegalchoicescorrespondtosolutionsto

Xo$xXy+--+:+x,=n—ksuchthatx,,...,x4_1arepositiveandxo,xz

arenonnegative.Subtracting1fromthevariablesrequiredtobeposi- tivetransformstheseintononnegativeintegersolutionsofyo+:::+y,%= n—2k+1. Bytheselectionswithrepetitionmodel,thenumberofsolu- tionsis("7At1***1"1)whichsimplifiesto(”"{*").Proof2.Viewthen—kunchosenintegersasdotsinarow.Wechoose placesfortheselectedintegersbetweenthedots(andontheends),but avoidanceofconsecutiveintegersrequiresthatnospaceisselectedtwice.Wehaven—k+1allowableplacesandchoosekofthemforbars.Thebars nowmarkthepositionsofkselectednumbers.c)Therearen!choicesofsubsetsAg,A,...Anof[n]suchthatApC A;C-:-CA,.Thereare(n+2)”choicessuchthatApGCAyC--:CAp.Whenthesetshavedistinctsizes,wehave|A;|=7,sinceallthesizesare between0andn.HenceAg=@,andtheelementsof[n]areaddedoneby oneinsomeorder.Then!possibleorderscorrespondtothechains.Todetermineachainofthesecondtype,itsufficestospecifyforeach x€[n]theindexisuchthatxfirstappearsinthechainatA;.Notap- pearingatallisalsoanoption.Hencetherearen+2choicesavailable foreachx,andthechoicemadeforxisnotrestrictedbythechoicesmade forotherelements. 3 / 4

Section1.1:ClassicalModels4

1.1.15.Theexponentonaprimepintheprimefactorizationof(*”)isthe numberofpowersp*ofpsuchthat|2n/p*|isodd.Weusetheformula ‘aiGryInm!,|m/p|factorsaredivisiblebyp.In|m/p?|ofthese, wehaveanextrafactorofp.In|m/p°|,wehaveyetanotherfactorofp, andsoon.Hencethehighestpowerofpthatdividesm!is}),.,|m/p*|, When|2n/p*|iseven,thenumberofmultiplesofp*in[2n]istwice thenumberin[n];forexample|10/2|=4,and|5/2|=2.When|2n/p*|

isodd,wegetoneextra:|6/2|=8,but|3/2|=1.Thelattercaseoccurs

ifandonlyiftheremainderofnupondivisionbyp*isatleastp*/2.Sincethefactorsofpinthefactorizationofn!areused(twice)tocan- celfactorsofpinthefactorizationof(2n)!,wethusfindthat(2n)!keeps anextrafactorofpforeachkwhere|2n/p*|isodd.Primefactorsof(‘5)and({}).Aprimepwillbeafactorif|2n/p*|is oddforsomek.Wehave|18/2|=9and|20/4|=5,so2dividesboth.Since|18/3|=|20/3]=6and|18/9|=|20/9|=2,3dividesneither.Forhigherprimes,thesquaresaretoobigtogiveanonzerocontri- bution.Wehave|18/5|=3but|20/5|=4,so5divides()butnot(79).Since|18/7|=|20/7|=2,7dividesneither.However,11,13,and17 yield1ineachcase,asdoes19inthelattercase.Hencetheprimedivisors of(j)are{2,5,11,13,17},andthoseof(7)are{2,11,13,17,19}.

1.1.16.Givenv(a,b)=((,7,)-(3).(451)),theredonotexistdistinctpairs (a,b)and(c,d)ofpositiveintegerssuchthatv(c,d)isamultipleofv(a,b).Supposeu(c,d)=xv(a,b).Wehave(5)=x(%),andthen 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-6a\a-b[c d+1\d)\d+1)“\b+1)“b+1\b)b+1\d Thus(a-—b+1)d=(c—d+1)band(6+1)(c—d)=(d+1)(a—b).The differenceofthesetwoequationsyieldsd—a+b=b—c+d,andhencea= c.Now,since(,°,)=#2(¢)and(,°,)=$4(5),andtheratiosof($)to(5) and(71)to(464)arethesame,wehavea”=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.Thereare(%;)(";")listsofm1sandn0shavingkrunsof1s.Proof1(caseanalysis).Thenumberofrunsof0smaybek—1(start andendwith1s),k+1(startandendwithOs),ork(twocases,starting withOsorwith1s).Ineachofthesefourcases,formingcompositionsof mandnwiththerightnumberofpartscompletelyspecifiesthelist.

• / 4