############################################################ # PDAV123: A Maple package accompanying the article: # "On the Asymptotic Statistics of the Number of Occurrences # of Multiple Permutation Patterns" # # This version: August 3, 2013 # # Written by Brian Nakamura, Rutgers University ############################################################ print(` This is PDAV123, a Maple package implementing the `): print(` enumeration algorithms described in the article: `): print(` "On the Asymptotic Statistics of the Number of Occurrences `): print(` of Multiple Permutation Patterns" `): print(` for patterns in a random permutation out of Sn(123). `): print(``): print(` Please report any bugs to: bnaka [at] math [dot] rutgers [dot] edu `): print(``): print(` For general help and a list of the main functions, type "Help();". `): print(` For help on a specific procedure, type "Help(procedure_name);". `): print(``): Help:=proc() if args=NULL then print(` PDAV123: A Maple package for refining the number `): print(` of permutations avoiding 123 by the number of `): print(` occurrences of a (fixed) pattern of length 3. `): print(): print(` The main procedures are: `): print(` FI3p132(n,t), FI3p312(n,t), FI3p321(n,t) `): print(): print(` For help on a specific procedure, type "Help(procedure_name);". `): print(): elif nops([args])=1 and op(1,[args])=FI3p132 then print(` FI3p132(n,t): inputs a positive integer n and variable t and `): print(` outputs the polynomial (in t) a_0 + a_1*t + a_2*t^2 + ..., `): print(` where a_k is the number of length n permutations avoiding 123 `): print(` with exactly k occurrences of 132. `): print(` For example, try "FI3p132(7,t);" `): print(): elif nops([args])=1 and op(1,[args])=FI3p312 then print(` FI3p312(n,t): inputs a positive integer n and variable t and `): print(` outputs the polynomial (in t) a_0 + a_1*t + a_2*t^2 + ..., `): print(` where a_k is the number of length n permutations avoiding 123 `): print(` with exactly k occurrences of 312. `): print(` For example, try "FI3p312(7,t);" `): print(): elif nops([args])=1 and op(1,[args])=FI3p321 then print(` FI3p321(n,t): inputs a positive integer n and variable t and `): print(` outputs the polynomial (in t) a_0 + a_1*t + a_2*t^2 + ..., `): print(` where a_k is the number of length n permutations avoiding 123 `): print(` with exactly k occurrences of 321. `): print(` For example, try "FI3p321(7,t);" `): print(): else print(` There is no procedure called`, args): print(` Please refer back to the main Help by typing "Help();" `): print(): fi: end: #################### # # Single length 3 pattern in 123-avoiders # #################### ### Pattern 132 # FI3p132recfull(L1,t2): main recursive procedure for FI3p132(n,t) FI3p132recfull:=proc(L1,t2) local n,i,j,fr,k1,k2,L1i: option remember: n:=nops(L1): fr:=0: if n=1 then RETURN(1): fi: for i from 1 to n do # Check for Pattern 123 avoidance k1:=L1[i]*(n-i): if k1=0 then # Pattern 123 L1i:=[op(1..i-1,L1), seq(L1[j]+1,j=i+1..n)]: # Pattern 132 k2:=add(L1[j],j=1..i-1): fr:=fr+t2^k2*FI3p132recfull(L1i,t2): fi: od: expand(fr): end: # FI3p132(n,t): weight-enumerates Sn(123) by t^(# of 132) FI3p132:=proc(n,t) FI3p132recfull([0$n],t): end: ### Pattern 312 # FI3p312recfull(L1,L5,t5): main recursive procedure for FI3p312(n,t) FI3p312recfull:=proc(L1,L5,t5) local n,i,j,fr,k1,k5,L1i,L5i: option remember: n:=nops(L1): fr:=0: if n=1 then RETURN(1): fi: for i from 1 to n do # Check for Pattern 123 avoidance k1:=L1[i]*(n-i): if k1=0 then # Pattern 123 L1i:=[op(1..i-1,L1), seq(L1[j]+1,j=i+1..n)]: # Pattern 312 k5:=add(L5[j],j=i+1..n): L5i:=[seq(L5[j]+1,j=1..i-1), op(i+1..n,L5)]: fr:=fr+t5^k5*FI3p312recfull(L1i,L5i,t5): fi: od: expand(fr): end: # FI3p312(n,t): weight-enumerates Sn(123) by t^(# of 312) FI3p312:=proc(n,t) FI3p312recfull([0$n],[0$n],t): end: ### Pattern 321 # FI3p321recfull(L1,L5,t6): main recursive procedure for FI3p321(n,t) FI3p321recfull:=proc(L1,L5,t6) local n,i,j,fr,k1,k6,L1i,L5i: option remember: n:=nops(L1): fr:=0: if n=1 then RETURN(1): fi: for i from 1 to n do # Check for Pattern 123 avoidance k1:=L1[i]*(n-i): if k1=0 then # Pattern 123 L1i:=[op(1..i-1,L1), seq(L1[j]+1,j=i+1..n)]: # Pattern 321 L5i:=[seq(L5[j]+1,j=1..i-1), op(i+1..n,L5)]: k6:=L5[i]*(i-1): fr:=fr+t6^k6*FI3p321recfull(L1i,L5i,t6): fi: od: expand(fr): end: # FI3p321(n,t): weight-enumerates Sn(123) by t^(# of 321) FI3p321:=proc(n,t) FI3p321recfull([0$n],[0$n],t): end: