On the Basis Polynomials in the Theory of Permutat

arXiv:0801.0072v1[math.CO]30Dec2007ONTHEBASISPOLYNOMIALSINTHETHEORYOFPERMUTATIONSWITHPRESCRIBEDUP-DOWNSTRUCTUREVLADIMIRSHEVELEVAbstract.Westudythepolynomialswhichenumeratethepermuta-tionsπ=(π1,π2,...,πn)oftheelements1.2,...,nwiththeconditionπ1π2...πn−m(orπ1π2...πn−m)andprescribedup-downpointsn−m,n−m+1,...,n−1inviewofanimportantroleofthesepolynomialsintheoryofenumerationthepermutationswithprescribedup-downstructuresimilartotheroleofthebinomialcoeffi-cientsintheenumerationofthesubsetsofafinitesetsatisfyingsomerestrictions.1.IntroductionD.Andre[2]firstconsidered(1881)theproblemoftheenumeratingtheal-ternatingpermutationsπ=(π1,...πn)ofthenumbers1,2,...,nforwhichupsanddownsarealternating:π1π2π3...Thisproblemhasahighlyaestheticsolution:theexponentialgeneratingfunctionofsuchpermutationsisthesumoftangentandsecant.Butonlyafteracentury(1968)I.Niven[11]consideredageneralproblemoftheenu-meratingthepermutationswithgivenup-downstructure.Forpermutationπ=(π1,...,πn),thesequence(q1,q2,...,qn−1),where(1)qj=sign(πj+1−πj)=(1,ifπj+1πj−1,ifπj+1πj,iscalledaNiven’ssignature.Forexample,a=(2,1,5,4,3)hasthesigna-ture(−1,1,−1,−1).Denote[q1,q2,...,qn−1]thenumberofpermutationshavingtheNiven’ssignature(q1,q2,...,qn−1).Inviewofsymmetrywehave(2)[q1,q2,...,qn−1]=[−qn−1,−qn−2,...,−q1].Nivenobtainedthefollowingbasicresult.1991MathematicsSubjectClassification.05A15.ONTHEBASISPOLYNOMIALS2Theorem1.[11].Letinthesignature(q1,q2,...,qn−1)theindicesofthoseqiwhichare+1bek1k2...km(ifsuchqidonotexistthenassumem=0).Putinadditionk0=0,km+1=n.Then(3)[q1,q2,...,qn−1]=detN,whereN={nij}isthesquarematrixoforderm+1inwhich(4)nij=kikj−1,i,j=1,2,...,m+1.AfterthiscelebratedNiven’sresultanduntilnowtherehasbeenaseriesofarticlesbymanyauthors.Wementiononlytenpapersinchronologi-calorder:N.G.Bruijn,1970[5],H.O.Foulkes,1976[7],L.Carlitz,1978[6],G.Viennot,1979[17],C.L.MallowsandL.A.Shepp,1985[9],V.Arnold,1990[3],V.S.Shevelev,1996[14],G.Szpiro,2001[16],B.Shapiro,M.ShapiroandA.Vainshtein,2005[12],F.C.S.Brown,T.M.A.FinkandK.Willbrand,2007[4].AccordingtothedeBruijn-Viennotalgorithm[5],[17]thecalculatingof[q1,q2,...,qn−1]couldberealizedusingthefollowingnumericaltriangle.Atthetopofthetriangleput1.Write0totheright(left)ifqn−1is1(−1).Forexample,ifqn−1=1thenthefirsttwoelementsofthetriangleare:10.Summingtheseelementswewritethesumtotheleft:110.Nowthefollowing0wewritetotherightofthelastelement(totheleftofthefirstelement)ifqn−2is1(−1).Forexample,ifqn−2=1thenwehave1100.Nowthethirdrowisobtainedbysummingeachelementinthethirdrowfromtherighttotheleft,firstelementbeing0,withtheelementsleftandaboveitinthesecondrow:110100Incaseofqn−2=−1wehave1100andthethirdrowisobtainedbysummingeachelementinthethirdrowfromthelefttotheright,firstelementbeing0,withtheelementsrightandaboveitinthesecondrow:ONTHEBASISPOLYNOMIALS3110011Theprocesscontinuesuntilthen-throwwhichcorrespondstoq1.Nowthesumofelementsofthen-throwisequalto[q1,q2,...,qn−1].Example1..Forsignature(−1,1,1,−1,1)wehavethetriangle110011221053100058999.=Therefore,[−1,1,1,−1,1]=0+5+8+9+9+9=40.Inordertoobtainaweightgeneralizationletusconsideramatrixfunctionwhichwecall”alternant”(cf.[13]).Ifapermutationπhasthesignature(q1,q2,...,qn−1)thenwewriteπ∈(q1,q2,...,qn−1).Furthermore,ifπi=jthentothetwo-dimensionalpoint(i,j)assignthe”weight”aij.LetA=(aij)beann×nmatrix.Denote(5)alt(q1,...,qn−1)A=Xπ∈(q1,...,qn−1)nYi=1aiπi.LetA1j,j=1,...,n,be(n−1)×(n−1)matrixwhichisobtainedfromAbythedeletionofthefirstrowandthej-thcolumn.DenoteA(+1)1j(A(−1)1j)thematrixwhichisobtainedfromA1jbyreplacingthej−1first(then-jlast)elementsofitsfirstrowby0’s.ThenfromtheViennot’salgorithmwededucethefollowingexpansionofthealternantbythefirstrowofthematrix.Theorem2.(cf.[13])(6)alt(q1,...,qn−1)A=nXj=1a1jalt(q2,...,qn−1)A(q1)1j.NotethatifA=Jn−n×nmatrixcomposedof1’sonly,thenONTHEBASISPOLYNOMIALS4(7)alt(q1,...,qn−1)A=[q1,...,qn−1].Incaseofarbitrary(0,1)matrixA,Theorem2givesenumerationthepermutationshavingsignature(q1,...,qn−1)withrestrictiononpositions.Forexample,ifInis(n×n)identitymatrix,thenalt(q1,...,qn−1)(J−I)givesthenumberofsuchpermutationswithoutfixedpoints.Notethat,by(5)(8)alt(1)a11a12a21a22=a11a22,alt(−1)a11a12a21a22=a12a21.Example2..alt(1,−1,1)J4=alt(1,−1,1)1111111111111111=alt(−1,1)111111111++alt(−1,1)011111111+alt(−1,1)001111111+alt(−1,1)000111111==alt(1)0011+alt(1)1011+alt(1)1111++alt(1)1011+alt(1)1111+alt(1)1111=0+1+1+1+1+1=5,whilealt(1,−1,1)(J4−I)=alt(1,−1,1)0111101111011110=alt(−1,1)011101110+ONTHEBASISPOLYNOMIALS5+alt(−1,1)001111110+alt(−1,1)000110111==alt(1)1010+alt(1)1011+alt(1)1111=2.Notethatalternantisalsousefulforenumerationthepermutationswithsomeadditionalconditions.Forexample,ifitisnecessarytoenumeratethepermutationsπwithsignature(q1,q2,...,qn−1)forwhichπ1=l,πn=mthenweshouldcalculatealtJ(l,m)nwhereJ(l,m)nisobtainedfromJnbyreplacingall1’softhefirstandthelastrowsby0’sexceptthel-th1andthem-th1correspondingly.Forexample,thereareonly2suchpermutationsinthecaseofthesignature(−1,1,1,−1,1),n=6,l=2,m=6.Letusnowintro