# The Number of Permutations With A Prescribed Number of 132 and 123 Patterns # # By # # Shalosh B. Ekhad, Aaron Robertson and Doron Zeilberger # # Temple University, Philadelphia, PA 19122, USA # [ekhad,aaron,zeilberg]@math.temple.edu # http://www.math.temple.edu/~[ekhad,aaron,zeilberg]/ # # (March 29, 1999. Requires Maple V, ver. 4 or below.) # # # 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. # # Thus 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. # When the first author ran this program, it got the following output: # AR(0,z) = (1-z)/(1-2*z) # AR(1,z) = z^3/(1-2*z)^2 # AR(2,z) = z^4*(1-z)/(1-2*z)^3 # AR(3,z) = z^5*(z-1)^2/(1-2*z)^4 # AR(4,z) = -z^4*(z^5-3*z^4+11*z^3-13*z^2+6*z-1)/(1-2*z)^5 # AR(5,z) = 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) = z^3/(1-2*z)^2 # Aaron(1,z) = 2*z^5/(1-2*z)^3 # Aaron(2,z) = -z^4*(z^3-6*z^2+4*z-1)/(1-2*z)^4 # Aaron(3,z) = 2*z^5*(1-z)*(5*z^2-4*z+1)/(1-2*z)^5 # Aaron(4,z) = z^6*(z^5+12*z^4-55*z^3+65*z^2-30*z+5)/(1-2*z)^6 ##############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(`Warning: Does 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: # AR(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 AR:=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: # Aaron(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 Aaron:=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: ###################END OF MAPLE PROGRAM/END OF ARTICLE#######################