{VERSION 5 0 "IBM INTEL LINUX" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "" -1 256 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 257 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 0 "" }{TEXT 256 97 "Maple package to accompany\n\"A Co mbinatorial Proof of a Partition Identity of Andrews and Stanley\"" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 257 92 "In this package, \+ a 'partition' (as a Maple object) will mean a list of positive integer s in\n" }{TEXT 260 13 "nonincreasing" }{TEXT 261 123 " order. Note th at this differs from a 'partition' as defined in Maple's 'combinat' pa ckage, where the parts are listed in " }{TEXT 258 14 "nondecreasing " }{TEXT 259 125 "order. It is easy to switch from one format to the o ther using the 'Reverse' procedure in the standard package 'ListTools' ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 57 "To load the package, simply execute this execution group." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "with(combinat):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "with(ListToo ls):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 104 "Conjugate:=proc(pi) ;\n## \+ Returns the conjugate of the partition pi.\n Reverse(conjpart(Reverse( pi))) end:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 123 "AppendZeros:=proc(L, n) local i;\n## Input: a list L\n## Output: the list L with n zeros ap pended.\n[op(L), seq(0,i=1..n)]\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 268 "FindList:=proc(L,i)\n## Returns the position of the first occur ence of the element i in the list L\n## Returns 0 if i is not a member of L\nlocal j;\nif member(i,L) then\n for j from 1 to nops(L) do \+ \n if op(j,L) = i then RETURN(j) fi\n od\nelse RETURN(0)\nfi \nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 124 "RemoveFinalZeros:= proc( L) local i;\nif op(-1,L)=0 then RETURN( [seq(op(i,L), i=1..-1+FindList (L,0))]) else RETURN(L) fi end:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 276 "multiplicity:=proc(lambda,i) local count,j;\n## Input: a partition la mbda\n## Output: the multiplicity of i in lambda, i.e. the number of t imes\n## i appears as a part in lambda.\ncount:=0;\nfor j from 1 to n ops(lambda) do\n if op(j,lambda)=i then count:=count+1 fi\nod;\ncount \nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 819 "alphamap:=proc(kappa) lo cal lambda,mu,i,j;\n## Input: a partition kappa\n## Output: a list of \+ two partitions [lambda,mu], where\n## mu is the maximal partition co ntained in kappa such\n## that mu has only odd parts of even multipl icity (and no even parts),\n## and that lambda is the complement of \+ mu in kappa.\nlambda:=[];\nmu:=[];\ni:=1;\nwhile i<= nops(kappa) do\n \+ if op(i,kappa) mod 2 = 0 then \n lambda:=[op(lambda),op(i,kappa)]; \n i:= i + 1 \n elif multiplicity(kappa, op(i,kappa)) mod 2 = 0 th en\n mu:=[op(mu), seq( op(i,kappa), j=1..multiplicity(kappa, op(i,k appa)))];\n i:= i + multiplicity(kappa,op(i,kappa))\n else lambda: =[ op(lambda), op(i,kappa)];\n mu:=[op(mu), seq( op(i,kappa),j=1..- 1+multiplicity(kappa,op(i,kappa)))];\n i:= i + multiplicity(kappa,o p(i,kappa))\n fi\nod;\nRETURN(lambda,mu)\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 618 "betamap:=proc(lambda,mu) local i,zeta,xi;\n## Input: Two partitions lambda, mu of partitions such that\n## in lambda th e multiplicity of any odd part is at most one and\n## mu contains o nly odd parts of even multiplicity.\n## Output: Each part p of lambda \+ is split into two \n## parts floor((p+1)/2), floor(p/2), and\n## \+ mu is mapped to its conjugate.\n#lambda:=op(1,L);\n#mu:=op(2,L);\nzet a:=[];\nfor i from 1 to nops(lambda) do\n if op(i,lambda) =1 then zet a:=[op(zeta),1] else\n zeta:=[op(zeta), floor( (op(i,lambda)+1)/2 ), \+ floor(op(i,lambda)/2)] fi\nod;\nxi:= Reverse(conjpart(Reverse(mu))); \nRETURN(zeta,xi)\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 301 "Partiti onSum:=proc(zeta,xi) local i,N,xi1,zeta1;\n## Input: two partitions z eta,xi\n## Output: the term by term sum.\nN:=max( nops(zeta),nops(xi)) ;\nif nops(zeta)>nops(xi) then xi1:=AppendZeros(xi,N-nops(xi)); zeta1: =zeta else\n zeta1:=AppendZeros(zeta,N-nops(zeta)); xi1:=xi fi;\nRETU RN(zeta1 + xi1)\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "gammamap:= proc(A,B) PartitionSum(A,B) end:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 153 "PartitionUnion:= proc(lambda,mu)\n## Input: two partitions lambda , mu\n## Output: the \"union\" of the two partitions\nReverse(sort([op (lambda),op(mu)]))\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "themap: =proc(kappa)\ngammamap(betamap(alphamap(kappa)))\nend:" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 60 "alphainverse:=proc(lambda,mu) PartitionUnion(l ambda,mu) end:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 325 "beta1inverse:= p roc(zeta) local i,z;\n## Input: a partition zeta\n## Output: the parti tion obtained from zeta when the \n## first and second parts are add ed,\n## the third and fourth parts are added, etc.\nz:= zeta;\nif n ops(zeta) mod 2 = 1 then z:= AppendZeros(zeta,1) fi;\n[seq( op(2*i-1,z ) + op(2*i,z), i=1..nops(z)/2)]\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 91 "betainverse:= proc(zeta,xi)\nRETURN(beta1inverse(zeta), Reverse( conjpart(Reverse(xi))))\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 557 "g ammainverse_old:=proc(pi)\n## Input: any partition pi\n## Output: pi i s split into two partitions, zeta and xi where\n## the conjugate of \+ xi is a partition with only odd parts, \n## all of even multiplicity ,\n## and xi . . .\nlocal i,tmp,green;\ni:=2; tmp:=pi; green:=[];\nw hile i<= op(1,tmp) do\n if NumParts(tmp,i) mod 2 = 1 and not(member(i -1,tmp)) then\n green:= PartitionSum( green,[seq(2, j=1..NumParts(t mp,i))]);\n tmp:= shrink2(tmp,i);\n i:=1;\n fi;\n i:=i+1\nod;\n tmp:=RemoveFinalZeros(tmp);\ngreen:=RemoveFinalZeros(green);\nRETURN(t mp,green)\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 256 "shrink2:=proc(p i,i) local j,k;\n## Input: a partition pi and an integer i\n## Output: a new partition obtained from pi by subtracting two from \n## all it s parts greater than i\nk:=NumParts(pi,i);\n[seq(op(j,pi)-2, j=1..k), \+ seq(op(j,pi), j=k+1..nops(pi))]\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 224 "NumParts:=proc(pi,i) local j,c;\n## Input: a partition pi and a n integer i\n## Output: the number of parts of pi which are greater th an or equal to i\nc:=0;\nfor j from 1 to nops(pi) do\n if op(j,pi)>=i \+ then c:=c+1 fi\n od;\nc\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "th einvmap:= proc(pi) alphainverse(betainverse(gammainverse(pi))) end:" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 186 "TestItN:=proc(N)\nlocal P,j,p;\nP := partition(N);\nfor j from 1 to nops(P) do\n p:= Reverse(op(j,P)); \n if not (p = theinvmap(themap(p))) then print(`NO NO NO NO NO`,p) f i\nod;\nprint(N)\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 175 "NumOddPa rts:=proc(L)\nlocal i,s;\n### Input : a list L\n### Output: the number of odd entries in L\ns:=0;\nfor i from 1 to nops(L) do if op(i,L) mod 2 = 1 then s:=s+1 fi od;\ns\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 341 "NumOppPar:=proc(pi)\nlocal p,c,i;\n### Input : A partition pi= [p i[1], pi[2], pi[3], ...]\n### Output: The number of pairs pi[2*i-1],p i[2*i] for which one \n### is odd and the other even\nc:=0;\nif nops(p i) mod 2 = 1 then p:=[op(pi),0] else p:=pi fi;\nfor i from 1 to nops(p )/2 do\n if (op(2*i-1,p) + op(2*i,p)) mod 2 = 1 then c:=c+1 fi\nod;\n c\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 682 "gammainverse_alt:=proc( pi) local tmp,xi,i,s,t,zeta;\n### Input : a partition pi\n### Output: \+ two partitions zeta and xi such that the conjugate of xi has\n### al l odd parts of even multiplicity and \n### zeta = [zeta[1], zeta[2 ], zeta[3], . . .]\n### is such that zeta[2*i-1] - zeta[2*i] is al ways 0 or 1.\ntmp:=pi;\nzeta:=[NumOddParts(conjpart(Reverse(tmp)))-Num OppPar(tmp)];\ntmp:=RemoveHead(pi,2);\nwhile nops(tmp)>=1 do\n s:=Num OddParts(conjpart(Reverse(tmp)));\n t:=NumOppPar(tmp);\n zeta:=[op(z eta),s-t,s-t];\n tmp:=RemoveHead(tmp,2)\nod;\nif nops(zeta) " 0 "" {MPLTEXT 1 0 113 "RemoveHead:=proc(L,k) \n## returns the list L with t he first k entries removed\n[seq(op(i,L), i=k+1..nops(L))]\nend:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 742 "gammainverse:=proc(pi) local tmp,xi,i,j,s,t,Pi,zeta;\n### Input : a partition pi\n### Output: two partitions zeta and xi such that the \+ conjugate of xi has\n### all odd parts of even multiplicity and zeta = [zeta[1], zeta[2], zeta[3], . . .]\n### is such that zeta[2*i-1 ] - zeta[2*i] is always 0 or 1.\ns:=NumOddParts(conjpart(Reverse(pi))) ;\nt:=NumOppPar(pi);\nPi:=pi;\nxi:=[s-t];\nfor i from 1 to nops(pi)/2 \+ do\n tmp:= s - add( pi[2*j-1] - pi[2*j], j=1..i) \n - t + a dd( (pi[2*j-1] + pi[2*j]) mod 2, j=1..i); \n xi:=[op(xi), tmp, tmp] \nod;\nif nops(xi)nops(pi) then Pi:=AppendZeros(pi, nops(xi)-nops(pi) ) fi;\nRETURN(RemoveFinalZeros(Pi-xi),RemoveFinalZeros(xi))\nend:" }}} }{SECT 0 {PARA 3 "" 0 "" {TEXT -1 36 "Example from section 4 of the pa per:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "kappa:=[9,7,7,6,6,5,4,4,3,3,3,2,1,1,1,1,1];" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "alphamap(kappa);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "lambda:=alphamap(kappa)[1];" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "mu:=alphamap(kappa)[2];" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "betamap(lambda,mu);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "zeta:=betamap(lambda,mu)[1]; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "xi:=betamap(lambda,mu)[ 2];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "pi:=gammamap(zeta,xi );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "gammainverse(pi);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 15 "betainverse(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "alphainverse(%);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 73 "Or we can execute the composition gamma(beta(alpha( kappa))) all a t once:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "themap(kappa);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 22 "...or the the inverse:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "theinvmap(%);" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 14 "Other examples" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 278 "The standard Maple package 'combinat' includes a procedu re 'randpart (n)' which generates a random partition of the integer n. We can use that here to generate random partitions; but remeber to u se the 'Reverse' procedure to convert the partition into a nonincreasi ng sequence." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "N:=rand(1.. 150):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "n:=N();" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "Reverse(randpart(n));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "themap(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "theinvmap(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 0 "" }}}}{MARK "7" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }