Random partitions with non negative rth difference

arXiv:math/0110188v1[math.CO]17Oct2001RandomPartitionswithnonnegativerthdifferencesRodCanfielda,SylvieCorteelb,[e-mail],[e-mail],[e-mail]Science,UniversityofGeorgiaAthens,GA30602,USAbPRiSM,Universit´edeVersailles,45Av.desEtatsUnis,78035VERSAILLES,FrancecDepartmentofMathsandComputerScience,DrexelUniversity,Philadelphia,PA19104,USAFebruary1,2008AbstractLetPr(n)bethesetofpartitionsofnwithnonnegativerthdifferences.LetλbeapartitionofanintegernchosenuniformlyatrandomamongthesetPr(n)Letd(λ)beapositiverthdifferencechosenuniformlyatrandominλ.Theaimofthisworkistoshowthatforeverym≥1,theprobabilitythatd(λ)≥mapproachestheconstantm−1/rasn→∞Thisworkisageneralizationofaresultonintegerpartitions[7]andwasmotivatedbyarecentidentitybyAndrews,PauleandRiese’sOmegapackage[3].Toprovethisresultweusebijective,asymptotic/analyticandprobabilisticcombinatorics.1IntroductionLetusfirststartbyafewdefinitionsandnotations.Apartitionλofnisasequenceofintegersλ=(λ1,λ2,...,λk)withλ1≥λ2...≥λk≥1andkXj=1λj=n.1Thesamepartitionλcanalsobewritteninitsfrequentialnotation,thatis:λ=nmn(n−1)mn−1...1m1withmj=|{i|λi=j}|,1≤j≤n.Thenumbermjiscalledthemultiplicityofthepartjinλ.Inthesequelwewillusebothrepresentations.Wenowdefinetherthdifferences.Letλ=(λ1,λ2,...,λk)beapartitionofnandΔr(λ)=(Δr1(λ),...,Δrk(λ))beitsrthdifferences.Therthdifferencescanbecomputedbythefollowingrecurrence:Δri(λ)=λiifi=korr=0Δr−1i(λ)−Δr−1i+1(λ)otherwiseInthesequelwewillwriteΔri(λ):Δriforshort.LetPrbethesetofpartitionswithnonnegativerthdifferences,thatistosay,(λ1,λ2,...,λk)∈PrifandonlyifΔri≥0for1ik.LetPr(n)bethesetofpartitionsλ∈Prwith|λ|=nandletpr(n)=|Pr(n)|.Thisworkwasmotivatedbytwopreviousresults.Thefirstresultisanidentityonpartitionswithnonnegativerthdifferences.ItwasdiscoveredbyAndrews,PauleandRiese’sOmegapackage.Theorem1[2,3]Thereisaone-to-onecorrespondencebetweenthepartitionsinPr(n)andthepartitionsofnintopartsi+rr
,i≥0.Thesecondresultisonordinaryintegerpartitions(partitionswithnonnegative1stdifferences):Theorem2[7]Letλbeapartitionofanintegernchosenuniformlyatrandomamongthesetofallpartitionsofn.Letd(λ)beapartsizechosenuniformlyatrandomfromthesetofallpartsizesthatoccurinλ.Foreverym≥1,theprobabilitythatd(λ)≥mapproachestheconstant1/masn→∞.Notethatofr=1thereexistsaonetoonecorrespondencebetweenthenumberofpositive1stdifferencesinanygivenpartitionandthenumberpartsizesofitsconju-gate.OuraimisthereforetogeneralizetheresultofTheorem2byusingtheidentityofTheorem1.Letusnowstateourgeneralization:2Theorem3LetλbeapartitionofanintegernchosenuniformlyatrandomamongthesetPr(n)ofallpartitionsofnwithnonnegativerthdifferences.Letd(λ)beapositiverthdifferencechosenuniformlyatrandomfromthesetofallpositivediffer-encesthatoccurinλ.Foreverym≥1,theprobabilitythatd(λ)≥mapproachestheconstantm−1/rasn→∞.ThepurposeofthispaperistoproveTheorem3.Wenowpresenttheorganizationofthepaper.WewillfirstgiveinSection2asimplebijectionoftheidentityofTheorem1thatgivesseveralrefinementsoftheidentity.Thisbijectionwasadver-tised/announcedbyZeilbergerinhisveryownjournal[6].WethenpresentinSection3someasymptoticresultsonthenumberofpartitionsinPr(n)and,thankstothebijection,ontheaveragenumberofpositiverthdifferencesinthepartitionsinPr(n).WefinallyuseinSection4someprobabilisticargumentswhichgeneralizetheworksonordinarypartitions[8,7].Theassociationofthethreepartsgivesustheproofofourresult.WeconcludethepaperbypresentingsomefutureworkinSection5.2BijectiveCombinatoricsInthissectionwearegoingtopresentabijectionfbetweenthepartitionsinPr(n)andthepartitionsofnintopartsi+rr
,i≥0.Letλ=(λ1,λ2,...,λk)beapartitioninPr(n)thenitsimagebythebijectionfinitsfrequentialnotationis:f(λ)=k−1+rrΔrkk−2+rrΔrk−1...rrΔr1wheretheΔri(1≤i≤k)aretherthdifferencesofλ.Isisclearthatf(λ)isapartitionintopartsr+ir
withi≥0.Nowletusprovethatf(λ)isapartitionofn.¿FromthedefinitionofΔr(λ),itiseasytoseethatλi=kXj=ir+k−j−1r−1Δrj.Asr+i−1r
=Pi−1j=0r+j−1r−1
,wehave|f(λ)|=|λ|.WecanreconstructλfromΔr(λ).Thereversemappingf−1istheneasytodefine.Letμbeapartitionofnintopartsr+ir
withμ1=k+r−1r
.Letμ(i)bethemultiplicityoftheparti−1+rr
inμ,1≤i≤k.Thenf−1(μ)=kXj=1r+k−j−1r−1μ(j),kXj=2r+k−j−1r−1μ(j),...,r−1r−1μ(k)!.3Itistheneasytoseethatfisabijection.Notethatifr=1thenf(λ)=λ′,theconjugateofλ.Aswesaidintheintroduction,thisbijectiongivessomerefinementsoftheidentity.Letusnowpresenttheserefinements:Theorem4Thereisaone-to-onecorrespondencebetweenthepartitionsinPr(n)withkpartsandjpositiverthdifferencesandthepartitionsofnintopartsi+rr
,i≥0,whoselargestpartisk−1+rr
andwithjpartssizes.Proof.Straightforwardwiththebijection.2Letusnowillustratetherefinementsthankstogeneratingfunctionsandarecurrence.Letpr(n,k,m)bethenumberofpartitionsinPr(n)withkpartsandPki=1Δri=m.ThenXn,k≥0pr(n,k,m)qnykxm=1+Xk≥1ykxq(k−1+rr)(1−xq(rr))(1−xq(r+1r))...(1−xq(r+k−1r))Letpr,≤(n,k,m)bethenumberofpartitionsinPr(n)withatmostkpartsandPki=1Δri=m,thenXn≥0pr,≤(n,k,m)qnxm=kYi=0(1−xq(i+rr))−1.Letpr,≤(n,k)bethenumberofpartitionsinPr(n)withatmostkparts.Wecangetaneasyrecurrencetocomputethi