%auto-ignore # Delete this line and above line # The Number of Permutations With A Prescribed Number of 132 and 123 Patterns # # By # # Shalosh B. Ekhad, Aaron Robertson, Doron Zeilberger # # Temple University, Philadelphia, PA 19122, USA # [ekhad,aaron,zeilberg]@math.temple.edu # http://www.math.temple.edu/~[ekhad,aaron,zeilberg]/ # # and Herb Wilf # # University of Pennsylvania, Philadelphia, PA, 19104, USA # wilf@math.upenn.edu # http://www.cis.upenn.edu/~wilf/ # # ABSTRACT: Here we present the reasoning behind, and program # to find, the generating functions for the number # of permutations in the title. The article duals # as the "accompanying" Maple package. # # # # In a recent article: `Permutations Containing and Avoiding 123 # and 132 Patterns', one of us (AR) (see http://www.math.temple.edu/~aaron/) # obtained expressions for the number of permutations on n objects that have # exactly s 132 patterns and r 123 patterns for (0<=r,s<=1). # # The number of 132 (resp. 123) patterns of a permutation # pi of length n, #132(pi) (resp. #123(pi)), is the number of triples # 1<=i10) and # the largest element, n, is at the k^th position, i.e. pi[k]=n, by letting # pi1:=[op(1..k-1,pi)] and pi2:=[op(k+1..n,pi)], we have that every element in # convert(pi1,set) must be larger than every element of convert(pi2,set), # or else a 132 would be formed, with the n serving as the `3' of the 132. # Hence, convert(pi1,set)={seq(i,i=n-k+1..n-1)}, and convert(pi2,set)= # {seq(i,i=1..n-k)}. Furthermore, pi1 and pi2 are 132-avoiding on their # own right. Conversely, if pi1 and pi2 are 132-avoiding permutations on # {seq(i,i=n-k+1..n-1)} and {seq(i,i=1..n-k)} respectively, (for some k, # 1<=k<=n) then [op(pi1),n,op(pi2)] is a NON-EMPTY 132-avoiding permutation. # # We have: # # #123(pi) = #123(pi1) + #123(pi2) + #12(pi1), # # since a 123 pattern in pi=[op(pi1),n,op(pi2)] may either be totally immersed # in the pi1 part, or wholly immersed in the pi2 part, or may be due to the n # serving as the `3' of the 123, the number of which is the number of 12 # patterns in pi1. # # We also have # # #12(pi) = #12(pi1) + #12(pi2) + nops(pi1), # # and, of course # # nops(pi) = nops(pi1) + nops(pi2) + 1 # # Hence: Weight(pi)(q,z,t):=q^(#123(pi))*z^(nops(pi))*t^(#12(pi))= # q^(#123(pi1)+#123(pi2)+#12(pi1))*z^(nops(pi1)+nops(pi2)+1)* # t^(#12(pi1)+ #12(pi2)+nops(pi1))=z*(q^(#123(pi1))*(q*t)^(#12(pi1))* # (z*t)^(nops(pi1))* q^(#123(pi2))*t^(#12(pi2))*z^(nops(pi2))= # z*Weight(pi1)(q,z*t,t*q)*Weight(pi2)(q,z,t). # So we have, if nops(pi)>0, pi is 132-avoiding, and # pi=[op(pi1),max(op(pi)),op(pi2)], then pi1, pi2 are smaller # 132-avoiding permutations, and: # # Weight(pi)(q,z,t) = z*Weight(pi1)(q,z*t,t*q)*Weight(pi2)(q,z,t) # # Now sum over ALL possible 132-avoiding permutations pi, to get # # P(q,z,t) = 1 + z*P(q,z*t,t*q)*P(q,z,t) # # (the 1 corresponds to the empty permutation: []) # # # Now let Q(q,z,t) be the sum of all the weights of all permutations with # exactly ONE 132 pattern. By adapting the argument from Miklos Bona's paper # (Discrete Math 181 (1998), 267-274) we easily see that Q(q,z,t) satisfies: # # Q(q,z,t) = z*P(q,z*t,q*t)*Q(q,z,t) + z*Q(q,z*t,q*t)*P(q,z,t) + # t^2*z^2*P(q,z*t,q*t)*(P(q,z,t)-1) . # # This holds since our sole 132 pattern can either appear in the elements (1) # before n, (2) after n, or (3) with n as the `3' in the 132 pattern. # z*P(q,z*t,q*t)*Q(q,z,t) corresponds to (1), z*Q(q,z*t,q*t)*P(q,z,t) # corresponds to (2), and t^2*z^2*P(q,z*t,q*t)*(P(q,z,t)-1) corresponds to # (3). We see that case (3) follows since pi=[op(pi1),n-k,n,op(pi2)], where # convert(pi1,set)={seq(i,i=n-k+2..n-1)} and convert(pi2,set)= # {seq(i,i=1..n-k-1)} union {n-k+1}, AND k cannot be equal to n. # # The generating function (in z) for the sequence of cardinalities of 132- # avoiding permutations with exactly r 123-patterns is # subs(q=0,diff(P(q,z,1),q\$r))/r! , and the analogous quantity for # permutations with exactly ONE 132-pattern is # subs(q=0,diff(Q(q,z,1),q\$r))/r! . To find these, we take ALL partial # derivatives up to the order r, of the functional equations, then do ALL # substitutions of [0,z,1],[0,z,0],[0,0,0] for [q,z,t], solve the resulting # (huge) system of algebraic equations, and then extract the desired quantities. # Delving deeper into the structure of P(q,z,t), Herb Wilf showed that # confracform(P(q,z,1)) = 1 # ____________ # # 1 - z # ___________ # # 1 - z # _________ # # 1 - zq # ________ # # 1 - zq^3 # _________ # # . . . # # where the n^th numerator is z*q^(binomial(n,2)). This was found by # iterating the functional equation for P(q,z,t) in the form # P(q,z,t) = 1/(1 - z*P(q,z*t,q*t)). Using this beautiful result # we can compute AR(r,z) very efficiently. We can then in turn # use this to iterate the functional equation for Q(q,z,t) efficiently. # The amount of time required to calculate AR(r,z) and Aaron(r,z) using # this beautiful continued fraction result is very small compared to # the time required for the same result using the partial derivatives # approach. Hence, when using the partial derivatives to calculate # AR(r) and Aaron(r) we will call the procedures ARSlow(r,z) and # AaronSlow(r,z). # When the first author ran this program, it got the following output: # (We list only 0<=r<=5, larger r's can be obtained.) # AR(0) = (1-z)/(1-2*z) # AR(1) = z^3/(1-2*z)^2 # AR(2) = z^4*(1-z)/(1-2*z)^3 # AR(3) = z^5*(z-1)^2/(1-2*z)^4 # AR(4) = -z^4*(z^5-3*z^4+11*z^3-13*z^2+6*z-1)/(1-2*z)^5 # AR(5) = z^5*(z-1)*(z^5-3*z^4+19*z^3-25*z^2+12*z-2)/(1-2*z)^6 # Aaron(0) = z^3/(1-2*z)^2 # Aaron(1) = 2*z^5/(1-2*z)^3 # Aaron(2) = -z^4*(z^3-6*z^2+4*z-1)/(1-2*z)^4 # Aaron(3) = 2*z^5*(1-z)*(5*z^2-4*z+1)/(1-2*z)^5 # Aaron(4) = z^6*(z^5+12*z^4-55*z^3+65*z^2-30*z+5)/(1-2*z)^6 # Aaron(5) = -2*z^7*(z^6+6*z^5-40*z^4+80*z^3-69*z^2+27*z-4)/(1-2*z)^7 ##############END OF HUMAN INTERFACE/BEGINNING OF MAPLE PROGRAM################# print(`This is a Maple Package AND article`): print(`written by Shalosh B. Ekhad, Aaron Robertson, and Doron Zeilberger.`): lprint(``): print(`To find the generating function for the number of permutations with `): print(`0 132-patterns and exactly r 123-patterns, type: AR(r,z); .`): print(`To find the generating function for the number of permutations with `): print(`exactly 1 132-pattern and exactly r 123-patterns, type: Aaron(r,z);.`): lprint(`` ): print(`Contains procedures AR(r), Aaron(r), ARSlow(r,z), and AaronSlow(r,z)`): print(`Warning: ARSlow and AaronSlow do not work for Maple V ver. 5. `): # Ders(f,vars,r): Given a function f in the list of variables vars, and a # non-negative integer r finds all partial derivatives of order<=r. Ders:=proc(f,vars,r) local gu,mu,i,j:option remember: if r<0 then RETURN({}) elif r=0 then RETURN({f}): fi:mu:=Ders(f,vars,r-1): gu:={f}:for i from 1 to nops(mu) do for j from 1 to nops(vars) do gu:=gu union {D[j](mu[i])}:od:od:gu:end: # Subs(F,SU): Given a set of expressions F, and a set of # specializations, returns the set of substituted expressions. Subs:=proc(F,SU) local i,j,gu:gu:={}: for i from 1 to nops(F) do for j from 1 to nops(SU) do gu:=gu union {F[i](op(SU[j]))}:od:od:gu:end: # Ptor(SFE,SP,vars,SU,r): Given a set of functional equations SFE, phrased # in terms of the functions in the set of functions SP, in the variables vars, # and a set of specializations SU solves for the partial derivatives of the # functions of P up to r^th order at the given specializations. Ptor:=proc(SFE,SP,vars,SU,r) local s,lu, eq,var,i: eq:={}: for i from 1 to nops(SFE) do eq:=eq union Ders(SFE[i],vars,r): od: eq:=Subs(eq,SU): var:={}: for i from 1 to nops(SP) do var:=var union Ders(SP[i],vars,r): od: var:=Subs(var,SU):solve(eq,var): end: # ARSlow(r,z): The formal power series whose coeff. of z^n # equals the number of 132-avoiding permutations of length n with exactly r 123 ARSlow:=proc(r,z) local P,t,q,gu,s,lu: gu:=Ptor({((q,z,t)->P(q,z,t)-1- z*P(q,z*t,q*t)*P(q,z,t))}, {((q,z,t)->P(q,z,t))},[q,z,t],{[0,z,1],[0,z,0], [0,0,0]},r):lu:=(q,z,t)->P(q,z,t): for s from 1 to r do lu:=D[1](lu): od: lu:=lu(0,z,1): RETURN(factor(subs(gu,lu)/r!)): end: # AaronSlow(r,z): The formal power series whose coeff. of z^n equals the number # of permutations of length n with exactly 1 132 and exactly r 123 patterns AaronSlow:=proc(r,z) local P,t,q,gu,s,lu: gu:=Ptor([((q,z,t)->P(q,z,t)-1-z*P(q,z*t,q*t)*P(q,z,t)), ((q,z,t)->Q(q,z,t)-z*P(q,z*t,q*t)*Q(q,z,t)-z*Q(q,z*t,q*t)*P(q,z,t) -t^2*z^2*P(q,z*t,q*t)*(P(q,z,t)-1))], {((q,z,t)->P(q,z,t)),((q,z,t)->Q(q,z,t)) },[q,z,t],{[0,z,1],[0,z,0], [0,0,0]},r):lu:=(q,z,t)->Q(q,z,t):for s from 1 to r do lu:=D[1](lu): od:lu:=lu(0,z,1): RETURN(factor(subs(gu,lu)/r!)): end: # numrtr(m): Returns the numerator of the mth convergent to the continued # fraction P(q,z,1) numrtr:=proc(m) option remember;if m=0 then RETURN(1) elif m=1 then RETURN(1-z) else RETURN(expand(numrtr(m-1)-z*q^(binomial(m,2))*numrtr(m-2))) fi:end: # dnmntr(m): Returns the denominator of the mth convergent to the continued # fraction P(q,z,1) dnmntr:=proc(m) option remember; if m=0 then RETURN(1-z) elif m=1 then RETURN(1-2*z) else RETURN(expand(dnmntr(m-1)-z*q^(binomial(m,2))*dnmntr(m-2))) fi: end: #AR(r): Returns the function AR(r,z) AR:=proc(r) local yy,cc; yy:=series(numrtr(r+1)/dnmntr(r+1),q=0,r+1); cc:=simplify(coeff(yy,q,r)); RETURN(cc); end: P:=proc(r) local yy,cc,G,i; yy:=series(numrtr(r+1)/dnmntr(r+1),q=0,r+1); G:=(1-z)/(1-2*z); for i from 1 to r do G:=G+simplify(coeff(yy,q^i))*q^i;od:end: T:=proc(X,n) local R: if n=1 then RETURN((X-1)/(z*X)); else R:=(T(X,n-1)-1)/(z*t^(n-1)*q^(binomial(n-1,2))*T(X,n-1)):fi: simplify(R); end: #We now iterate the functional equation #Q(q,z,t)=zQ(q,zt,qt)[P(q,z,t)]^2 + t^2 z [P(q,z,t)-1)]^2, #which can easily be deduced from the equation given in the #RWZ paper then subs in t=1 where TP=P(q,zt,qt) Q:=proc(r) local i,m,Z,PP,tmp,ans,d,tmp2,dd,ans2,W: if r=0 then RETURN(`r must be positive`):fi: m:=max(3,r):Z[m+1]:=1; for i from m to 2 by -1 do W:=subs(t=1,T(PP,i)): Z[i]:=simplify(z*q^(binomial(i,2))*Z[i+1]*W^2+z*q^(2*i+binomial(i,2))*(W-1)^2); od: Z[1]:=simplify(z*Z[2]*subs(t=1,T(PP,1))^2+z*q^2*(subs(t=1,T(PP,1))-1)^2); Z[0]:=simplify(z*Z[1]*PP^2+z*(PP-1)^2); tmp:=simplify(subs(PP=P(r),Z[0])); d:=denom(tmp):tmp2:=collect(simplify(d*tmp),q):ans2:=factor(coeff(tmp2,q^r)); ans:=denom(simplify(d/ans2));dd:=numer(simplify(d/ans2));[ans,dd]:end: Aaron:=proc(r) option remember: local i,tmp,ans,d,c,G: if r=0 then RETURN(z^3/(1-2*z)^2): fi:tmp:=Q(r):d:=collect(expand(tmp[2]),q): c:=tcoeff(d,q):G:=0:for i from 0 to r-1 doG:=G+Aaron(i)*coeff(d,q^(r-i)):od: ans:=factor(simplify((1/c)*(tmp[1]-G)));end: ###################END OF MAPLE PROGRAM/END OF ARTICLE##########################