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 , 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— 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( 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