##################################################################
##CONTAIN: Save this file as  CONTAIN                                #
## To use it, stay in the                                            #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read CONTAIN<Enter>                                #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Rutgers University ,                  #
#zeilberg at math dot rutgers dot edu                                #
######################################################################
 
#Created: May-June 2015
 
print(`Created:  May-June 2015`):
print(` This is CONTAIN `):
print(`It is one of the packages that accompany the article `):
print(`Enumerating Fixed-Codimension Wilf Classes`):
print(`by Shalosh B. Ekhad, Nathaniel Shar and Doron Zeilberger`):

print(`and also available from Zeilberger's website`):
print(``):
print(`Please report bugs to zeilberg at math dot rutgers dot edu`):
print(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://www.math.rutgers.edu/~zeilberg/  .`):


print(`---------------------------------------`):
 print(`For a list of the  MAIN procedures about INCREASING patterns type ezraI();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

print(`---------------------------------------`):
 print(`For a list of the  SUPPORTING procedures about INCREASING patterns type ezraI1();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

print(`---------------------------------------`):
 print(`For a list of the Supporting procedures type ezra1();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

print(`---------------------------------------`):
 print(`For a list of the MAIN procedures type ezra();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

with(combinat):

ezra1:=proc()

if args=NULL then
 print(` The supporting procedures are:  BGslow, BreakUp, BreakUpR, Des, Dif1, Etree, Etree1, FindPrev0g, GuessPol, GuessTreePol , ImpliedM, INSERT, `):
 print(` Insert, Insert1 `):
 print(` IsLeaf, IsTree, IV, Kabets, KickOut, Kids, KidsC, KidsOri, KidsP, KidsPP, Mekomot, Merge1, Nake, Prepend, Prepend1, redu, Redu, RNuP, RPerms, SpellOut, `):
 print(` SpellOut1kS, SODg, SubWords, Targem, UIpats, WtE `):
 print(``):

else
ezra(args):
fi:

end:

ezraI1:=proc()

if args=NULL then
 print(` The  SUPPORTING procedures about the increasing patters are : `):
 print(`  Akri, AreComp, BeHead, Bkri, BCkri, CheckCD1,  CheckCD2, CheckCDr, Ckri, FindPrev0,  FindFTs1  `):
 print(``):

else
ezra(args):
fi:

end:

ezraI:=proc()

if args=NULL then
 print(` The  MAIN procedures about the increasing patters are : `):
 print(` Akr, BGpolI,  EvalTree, EvalTreeK, FindFT, FindFTs, NuAkr, SipurI, SOD  `):
 print(``):

else
ezra(args):
fi:

end:


ezra:=proc()

if args=NULL then
 print(`The main procedures are:  DesPat, DesPats, AEtrees, BG, BGbu, BGd, Crimes, FindFTg, NuBG, PolyExp   `):
 print(` `):






elif nops([args])=1 and op(1,[args])=AEtrees then
print(`AEtrees(k,r,d): all trees of depth d for co-dimension r patterns of length k. Try:`):
print(`AEtrees(5,2,1);` ): 

elif nops([args])=1 and op(1,[args])=Akr then
print(`Akr(k,r): the set of permutations of {1,...,k+r} containing at least one pattern 1...k, try:`):
print(`Akr(4,2); `):

elif nops([args])=1 and op(1,[args])=Akri then
print(`Akri(k,r,i): the set of permutations of {1,...,k+r} containing at least one pattern 1...k, and that start with i. Try:`):
print(`Akri(4,2,2); `):

elif nops([args])=1 and op(1,[args])=AreComp then
print(`AreComp(T1,T2): are the family trees T1 and T2 compatible?. Try:`):
print(`AreComp(FindFT(5,1,[],2),FindFT(6,1,[],2));`):

elif nops([args])=1 and op(1,[args])=BeHead then
print(`BeHead(S): inputs a set of permutations S, outputs the set obtained by choping the`):
print(`first entry and reducting. Try:`):
print(`BeHead(convert(permute(4),set)):`):

elif nops([args])=1 and op(1,[args])=BG then
print(`BG(sig,r): Inputs a permutation, sig, and a non-negative  integer r, outputs the set of permutations`):
print(`of length |sig|+r that contain at least one occurence of the pattern sig. Try:`):
print(`BG([1,3,2],2);`):

elif nops([args])=1 and op(1,[args])=BGbu then
print(`BGbu(sig,r): Same input as BG(sig,r) (q.v.), but the output is broken up to a pair (let k be the size of sig)`):
print(`[Set of Bad Guys where k+r is not needed, i.e. it still contains the pattern sig after removing the largest entry k+r,`):
print(` [" where they are needed, but broken-up according to the location of k+r]. Try `):
print(` BGbu([1,3,2],2);   `):

elif nops([args])=1 and op(1,[args])=BGd then
print(`BGd(sig,r): Like BG(sig,r) (q.v), but broken up into a list, where the i-th item is`):
print(`the set of permutations that have exactly i crimes. Try: `):
print(` BGd([1,3,2],2);   `):

elif nops([args])=1 and op(1,[args])=BGpolI then
print(`BGpolI(k,d,Dep,Deg): the first d polynomials expressions in k, for  the number of permutations of length d+k `):
print(`that contain an increasing subsequence of length k, by finding trees of depth <=Dep. Try`):
print(`BGpolI(k,2,2,2);`):
print(`BGpolI(k,3,4,4);`):

elif nops([args])=1 and op(1,[args])=BGslow then
print(`BGslow(sig,r): A much slower way for doing BG(sig,r) (q.v), FOR CHECKING purposes only! Try`):
print(`BGslow([1,3,2],2);`):

elif nops([args])=1 and op(1,[args])=Bkri then
print(`Bkri(k,r,i): the set of permutations of {1,...,k+r} obtained by prepending i to Akr(k,r-1). Try: `):
print(`Bkri(4,2,2); `):

elif nops([args])=1 and op(1,[args])=BCkri then
print(`BCkri(k,r,i): Bkri(k,r,i) intersect Ckri(k,r,i). Try: `):
print(`BCkri(4,2,3); `):

elif nops([args])=1 and op(1,[args])=BreakUp then
print(`BreakUp(S,n): the break up of a set of permutations S, of {1, .., n}, according to its first element.`):
print(`Try: `):
print(` BreakUp(permute(3),3); `):

elif nops([args])=1 and op(1,[args])=BreakUpR then
print(`BreakUpR(S,n): the reduced break up of a set of permutations S, of {1,...,n},  according to its first element, after that first element`):
print(`is deleted and the rest reduced. `):
print(`Try: `):
print(` BreakUpR(permute(3),3); `):


elif nops([args])=1 and op(1,[args])=CheckCD1 then
print(`CheckCD1(k1): checks the scheme for codimension one bad guys containing the`):
print(`increasing pattern 1..k1. Try: `):
print(` CheckCD1(3); `):


elif nops([args])=1 and op(1,[args])=CheckCD2 then
print(`CheckCD2(k1): checks the scheme for codimension two bad guys containing the`):
print(`increasing pattern 1..k1. Try: `):
print(` CheckCD2(3); `):

elif nops([args])=1 and op(1,[args])=CheckCDr then
print(`CheckCDr(k1,r): checks the scheme for codimension-r permutations of {1,..., k1+r}, i.e. `):
print(`permutations of {1, ..., k1+r} CONTAINTING an increasing sunsequence of lengtk .`):
print(`Try CheckCDr(3,2);`):

elif nops([args])=1 and op(1,[args])=Ckri then
print(`Ckri(k,r,i): the subset of Akri(k,r,i) obtained by taking Akr(k,r-i) inserting {1,..,i-1} every which way`):
print(`and prepending i. Try:`):
print(`Ckri(4,2,2); `):


elif nops([args])=1 and op(1,[args])=Crimes then
print(`Crimes(pi,sig): The set of occurrences of the pattern sig in pi.`):
print(`Try: Crimes([1,3,2,4],[1,2,3]);`):

elif nops([args])=1 and op(1,[args])=Des then
print(`Des(T,L): inputs a pair [T,SetOfMistakes] and a list of integers L such that L[1]<=n,L[2]<=n-1 etc.`):
print(`finds the L[1]'s son and then the L[2]'s son of the latter all the way to L[nops(L)]. Try:`):
print(`Des([4,SpellOut([2,1,3],4)],[3,2]);`):


elif nops([args])=1 and op(1,[args])=DesPat then
print(`DesPat(T,L): inputs a pair [T,SetOfMistakes] where T=[n,sig], and sig is a pattern`):
print(`and a list of integers L such that L[1]<=n,L[2]<=n-1 etc.`):
print(`finds the L[1]'s son and then the L[2]'s son of the latter all the way to L[nops(L)]`):
print(`of SpellOut(sig,n). Try:`):
print(`DesPat([5,[2,1,3]],[3,2]);`):

elif nops([args])=1 and op(1,[args])=DesPats then
print(`DesPats(T,L): inputs a pair [T,SetOfMistakes] where T=[n,S], and S  is a set of patterns`):
print(`and a list of integers L such that L[1]<=n,L[2]<=n-1 etc.`):
print(`finds the L[1]'s son and then the L[2]'s son of the latter all the way to L[nops(L)]`):
print(`of the union of SpellOut(sig,n) over all sig in S. Try:`):
print(`DesPats([5,{[2,1,3],[1,2,3]}],[3,2]);`):

elif nops([args])=1 and op(1,[args])=Dif1 then
print(`Dif1(L,r): the r-th difference of the sequence L, try:`):
print(`Dif1([seq(i1^2,i1=1..10)],2);`):

elif nops([args])=1 and op(1,[args])=Etree then
print(`Etree(n,S,d): Inputs a positive inetger n, and a set of words in {1,..n} with distinct letters,`):
print(`and a positive integer d, finds the depth d tree. Try`):
print(`Etree(4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]},2);`):


elif nops([args])=1 and op(1,[args])=Etree1 then
print(` Etree1(n,S): Inputs a positive inetger n, and a set of words in {1,..n} with distinct letters, `):
print(` outputs a list of length n, such that the i-ith item is the number of such permutations that `):
print(` start with i. Try: `):
print(`Etree1(4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]});`):

elif nops([args])=1 and op(1,[args])=EvalTree then
print(`EvalTree(T,V): inputs a weighted tree, and a symbol V, outputs the evaluation of the tree`):
print(`using the symbol V for function evaluation. The leaves [a,b] get assigned V(b)(a), and`):
print(`the rest is recursive. Try:`):
print(`EvalTree(FindFTs(k,1,1,2),V);`):

elif nops([args])=1 and op(1,[args])=EvalTreeK then
print(`EvalTreeK(T,V,k,K): inputs a weighted tree, T, phrased in terms of the variable k,`):
print(`and  symbols V, k, and K , outputs the evaluation of the tree`):
print(`using the symbol V for function evaluation. The leaves [a,b] get assigned K^(a-k)V(b), and `):
print(` the rest is recursive. Try: `):
print(` EvalTreeK(FindFTs(k,1,1,2),V,k,K); `):

elif nops([args])=1 and op(1,[args])=FindPrev0 then
print(`FindPrev0(S,k,r): inputs a set S of forbidden words, finds a k1 and r1 with k1<=k, r1<=r `):
print(`such that it equals SOD(k1,r1,[]). For example, try:`):
print(`FindPrev0(SOD(5,2,[1]),5,2);`):

elif nops([args])=1 and op(1,[args])=FindPrev0g then
print(`FindPrev0g(S,k,r): inputs a set S of forbidden words, finds a pattern sig1, with nops(sig1)<=k  and r1 with r1<=r `):
print(`such that it equals SODg(sig1,r1,[]). For example, try:`):
print(`FindPrev0g(SODg([1,2,3,4,5],2,[1]),5,2); `):

elif nops([args])=1 and op(1,[args])=FindFT then
print(`FindFT(k,r,L,De): Inputs positive integers k and r, a list L, and a positive integer De`):
print(`tries to find a family tree, for SOD(k,r,L) ,of depth <=De, for`):
print(`If it fails, it returns FAIL. Try:`):
print(`FindFT(5,1,[],2);`):


elif nops([args])=1 and op(1,[args])=FindFTg then
print(`FindFTg(sig,r,L,De): Inputs a pattern, sig, of size  k, say, a non-neg. integer, r, a list L, and a positive integer De`):
print(` tries to find a family tree, for SODg(sig,r,L) ,of depth <=De, for `):
print(` the set of restrictions S. It it fails, it returns FAIL. Try: `):
print(` FindFTg([1,2,3,4,5],1,[],2); `):

elif nops([args])=1 and op(1,[args])=FindFTs then
print(`FindFTs(k,d,Deg,Dep): Inputs a symbol k and a codimension d , a list L, and  positive integers Deg and Dep`):
print(`outputs a polynomial scheme of degree<=Deg and depth<=Dep for enumerating permutations of {1, ..., k+d} that contain at least one`):
print(`increasing subsequence of length k. Try:`):
print(`FindFTs(k,1,1,2);`): 

elif nops([args])=1 and op(1,[args])=FindFTs1 then
print(`FindFTs1(k,d,Deg,Dep): Inputs a symbol k and a codimension d , a list L, and  positive integers Deg and Dep`):
print(`outputs a polynomial scheme, of degree Deg and depth Dep, for enumerating permutations of {1, ..., k+d} that contain at least one`):
print(`increasing subsequence of length k. Try:`):
print(`FindFTs1(k,1,1,2);`): 

elif nops([args])=1 and op(1,[args])=GuessPol then
print(`GuessPol(L,n,s0): guesses a polynomial of degree d in n for `):
print(`  the list L, such that L[i]=P[i] for i>=s0 for example, try:  `):
print(` GuessPol([(seq(i,i=1..10),n,1); `):


elif nops([args])=1 and op(1,[args])=GuessTreePol then
print(`GuessTreePol(L,k,Deg,k0): given a list of concrete trees, starting at k0, a symbol k, and a degree Deg, finds a symbolic `):
print(` weighted tree, with polynomial weigte,such that`):
print(`if you plug in k=k0, ..., k=k0+nops(L), you would get L, try:`):
print(`GuessTreePol([seq([k1,0],k1=3..10)],k,1,3);`):
print(`GuessTreePol([seq([[k1,[k1,0]]],k1=3..20)],k,1,3);`):
print(`GuessTreePol([seq([ [k1,[k1,0]],[k1^2,[k1+2,1]] ],k1=3..10)],k,2,3);`):

elif nops([args])=1 and op(1,[args])=ImpliedM then
print(`ImplliedM(i,S,n): Given a set of mistakes , S, that permutations of {1, ...,n}, may not contain, outputs the set of mistakes`):
print(`that the the permutations obtained by chopping the first entry, if it is i, and then reducing every`):
print(`entry larger than i by 1. Try: `):
print(` ImpliedM(2,{[1,2,4],[2,3,4]},n); `):


elif nops([args])=1 and op(1,[args])=Insert then
print(`Insert(i,pi): inputs a positive  integer i, and a permutation pi`):
print(` and  outputs the set of permutations`):
print(`and a permutation pi of {1, ...,n}, and 1<=i,p<=n+1, outputs`):
print(`of {1,...,n+1} where i can be anywhere, and deleting i, reduces to a permutation that is pi`):
print(`Try: `):
print(`Insert(3,[1,3,2]); `):


elif nops([args])=1 and op(1,[args])=INSERT then
print(`INSERT(i,S): inputs a positive  integer i, and  a set of permutations, S`):
print(` outputs the set of permutations`):
print(`obtained by inserting i anywhere possible to all the members of S. `):
print(`Try: `):
print(`INSERT(3,permute(3)); `):

elif nops([args])=1 and op(1,[args])=Insert1 then
print(`Insert1(i,p,pi): inputs  positive  integers, i, p, and a permutation pi of {1, ...,n}, say,`):
print(`and 1<=i,p<=n+1, outputs`):
print(`the permutation of {1,...,n+1} whose p-th entry is i and such that the permutation `):
print(`obtained by deleting i (that must be in the p-th place, of course)`):
print(` is pi. Try: `):
print(` Insert1(3,1,[1,3,2]); `):

elif nops([args])=1 and op(1,[args])=IsLeaf then
print(`IsLeaf(L): is L a weighted-leaf? Try: `):
print(` IsLeaf([3,1]); `):

elif nops([args])=1 and op(1,[args])=IsTree then
print(`IsTree(T): is T a weighted-tree? Try:`):
print(`IsTree([[4,[3,1]],[3,[2,1]]]);`):

elif nops([args])=1 and op(1,[args])=IV then
print(`IV(n,k): The set of all  increasing sequences [i1,...,ik] such that 1<=i1<i2<...<ik<=n, Try:`):
print(`IV(5,3);`):

elif nops([args])=1 and op(1,[args])=Kabets then
print(`Kabets(S): inputs a set of pairs {[perm,Set]} collects them under the first component.`):
print(` Try: `):
print(` Kabets({[[1,2],{1}],[[1,2],{2}],[[1,2,3],{c}]}); `):

elif nops([args])=1 and op(1,[args])=KickOut then
print(`KickOut(pi,i): inputs a permutation pi and an entry i, outputs  the pair [location, reduced form of the `):
print(`permutation obtained by deleting i. Try:`):
print(`KickOut([3,1,2,4,5],2); `):


elif nops([args])=1 and op(1,[args])=Kids then
print(`Kids(T): Like KidsP(T) (q.v.) but using complementary notation. Try:  `):
print(`Kids([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]);`):

elif nops([args])=1 and op(1,[args])=KidsC then
print(`KidsC(T): Like KidOriP(T) (q.v.) but the output is in complementary notation. Try:`):
print(` KidsC([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]); `):

elif nops([args])=1 and op(1,[args])=KidsP then
print(`KidsP(T): Inputs a state T=[n,S] where S is a set of actual patterns and we are interested`):
print(`in permutations of {1,...,n} avoiding the patterns in S, outputs its children state`):
print(`fulfillied by chopping the first letter (and reducing) if it is i=1, ...,n, so the`):
print(`output is a list of pairs [coeff, state], states of length n whose first component is n-1. and the coeff is the`):
print(`multiplicity Try:`):
print(`KidsP([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]);`):

elif nops([args])=1 and op(1,[args])=KidsOri then
print(`KidsOri(T): Inputs a state T=[n,S] where S is a set of actual patterns and we are interested`):
print(`in permutations of {1,...,n} avoiding the patterns in S, outputs its children state`):
print(`fulfillied by chopping the first letter (and reducing) if it is i=1, ...,n, so the`):
print(`output is a list of sets of mistakes, for the children. Try: `):
print(`KidsOri([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]);`):

elif nops([args])=1 and op(1,[args])=KidsPP then
print(`KidsPP(T):  A condensed version of KidsP(T) (q.v) where the younger childen are lumped together if`) :
print(` they are identical, leading to (in the case of 1...k containing) finitely many children. Try: `):
print(` KidsPP([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]); `):

elif nops([args])=1 and op(1,[args])=Mekomot then
print(`Mekomot(pi,tau): the set of COMPLEMENT of places where the pattern tau occurns in the permutation pi`):
print(`Try: `):
print(`Mekomot([1,2,3,4],[1,2,3]);`):

elif nops([args])=1 and op(1,[args])=Merge1 then
print(`Merge1(sig1,sig2,S1): inputs two words, sig1, sig2, with distinct letters, such that their union is {1, ...,n}`):
print(` where n=|sig1|+|sig2| and S1 a subset of{1,..,n}, creates a permutation of {1,...,n} such `):
print(` that the members of sig1 go to the slots of S1 and the rest to sig2, in that order. Try `):
print(` Merge1([1,3,2],[5,4],[1,3,5]); `):


elif nops([args])=1 and op(1,[args])=Nake then
print(`Nake(n,S): inputs a positive integer n, and a set of words in {1,...,n} `):
print(` outputs a pair `):
print(` [coeff,[k,S1]] where k<=n and S1 is hopefully simpler than S and such that `):
print(` NuP(n,S)=coeff*NuP(k,S1). Try: `):
print(` Nake(3,{[2,3]}); `):

elif nops([args])=1 and op(1,[args])=NewKids then
print(`NewKids(T): Like KidsP(T) (q.v.) but the output is in complementary notation. Try: `):
print(` NewKidsOld([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]); `):

elif nops([args])=1 and op(1,[args])=NuAkr then
print(`NuAkr(k,r): the NUMBER of permutations of {1,...,k+r} containing at least one pattern 1...k, try:`):
print(`NuAkr(4,2); `):

elif nops([args])=1 and op(1,[args])=NuBG then
print(`NuBG(sig,r): Inputs a permutation, sig, and a non-negative  integer r, outputs the NUMBER of permutations`):
print(`of length |sig|+r that contain at least one occurence of the pattern sig. Try:`):
print(`NuBG([1,3,2],2);`):


elif nops([args])=1 and op(1,[args])=PolyExp then
print(`PolyExp(T,k,r,k0,k1): inputs a procedure T that outputs a sequence of patterns of length k, finds a polynomial expression for`):
print(`the number of permutations containing at least one occurence of that pattern of length k+r, as a polynomial in k`):
print(`starting at k0, and trying out until k=k1, otherwise it returns FAIL. Try:`):
print(`T1:=proc(k) local i: [seq(i,i=1..k)]:end: PolyExp(T1,k,1,1,6);`):
print(`T1:=proc(k) local i: [seq(i,i=1..k)]:end: PolyExp(T1,k,3,2,11);`):
print(`T1:=proc(k) local i: [seq(op([2*i,2*i-1]),i=1..k)]:end: PolyExp(T1,k,2,1,8);`):
print(`  T1:=proc(k) local i: [5,1,3,2,4,seq(i,i=6..k)]:end: PolyExp(T1,k,2,6,13); `):

elif nops([args])=1 and op(1,[args])=Prepend then
print(`Prepend(i,S): inputs a positive  integer, i,  and a set of permutation pi of {1, ...,n}, and 1<=i<=n, outputs`):
print(`the set of permutations of {1,...,n+1} whose first entry is i and such that the reduction of the 2nd through n+1 entries`):
print(` is the set S Try: `):
print(` Prepend(3,{[1,3,2],[2,1,3]}); `):

elif nops([args])=1 and op(1,[args])=Prepend1 then
print(`Prepend1(i,pi): inputs a positive  integer, i,  and a permutation pi of {1, ...,n}, say,`):
print(`and 1<=i<=n+1, outputs`):
print(`the permutation of {1,...,n+1} whose first entry is i and such that the reduction of the 2nd through n+1 entries`):
print(` is pi. Try: `):
print(` Prepend1(3,[1,3,2]); `):

elif nops([args])=1 and op(1,[args])=redu then
print(`redu(pi): the reduction of the permutation pi, try: `):
print(` redu([2,6,3]); `):

elif nops([args])=1 and op(1,[args])=Redu then
print(`Redu(S): the set of reduction of the set of permutation S, try: `):
print(` Redu({[2,6,3]}); `):

elif nops([args])=1 and op(1,[args])=RNuP then
print(`RNuP(n,S): Inputs a positive inetger n, and a set of words in {1,..n} with distinct letters,`):
print(`outputs the NUMBER of n-permutations that DO contain, as subwords one the members of S. Try:`):
print(`RNuP(4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]});`):

elif nops([args])=1 and op(1,[args])=RPerms then
print(`RPerms(n,S): Inputs a positive inetger n, and a set of words in {1,..n} with distinct letters,`):
print(`outputs the set of n-permutations that DO CONTAION, as subwords, one of the members of S. Try:`):
print(`RPerms(4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]});`):

elif nops([args])=1 and op(1,[args])=SipurI then
print(`SipurI(k,d,Deg,Dep,V): inputs a symbol k, a positive integer d, and positive integers Deg and Dep`):
print(` and a symbol V `):
print(` outputs an article with rigorously proved polynomial expressions for the `):
print(` number of permutations of length k+i containing an increasing subsequence of length i for i from 1 to d `):
print(` Deg is the maximum degree and Dep the maximum depth of the trees. If these are not big enough, it may `):
print(` not go all the way to d. Try: `):
print(` SipurI(k,2,2,2,V); `):

elif nops([args])=1 and op(1,[args])=SOD then
print(`SOD(k,r,L): inputs positive integers k and r, and a list L of positive integers `):
print(` outputs the descendant of SpellOut([1...k],k+r) given by the list L,  `):
print(` accodring to KidsPP (q.v). i.e.first you go to the L[1]'s child, then to the latters's L[2] child. etc. `):
print(` it returns FAIL if you encounter something undefined on the route `):
print(`Try: `):
print(` SOD(4,2,[1]); `):

elif nops([args])=1 and op(1,[args])=SODg then
print(`SODg(sig,r,L): inputs a pattern sig, of length k, say and a non-neg. integer r, and a list L of positive integers `):
print(` outputs the descendant of SpellOut(sig,k+r) given by the list L,  `):
print(` accodring to KidsPP (q.v). i.e.first you go to the L[1]'s child, then to the latters's L[2] child. etc. `):
print(` it returns FAIL if you encounter something undefined on the route `):
print(`Try: `):
print(` SODg([1,2,3,4],2,[1]); `):

elif nops([args])=1 and op(1,[args])=SpellOut then
print(`SpellOut(tau,n): inputs a pattern tau  and a positive integer n outputs the set of all manifestations of tau.`):
print(`Try:`):
print(`SpellOut([2,1,3],4);`):

elif nops([args])=1 and op(1,[args])=SpellOut1kS then
print(`SpellOut1kS(k,S): all the ordered vectors of  length k missing the set S. Try:`):
print(`SpellOut1kS(5,{1,2});`):

elif nops([args])=1 and op(1,[args])=SubWords then
print(`SubWords(w,k): all the subwords of w of length k. Try:`):
print(`SubWords([1,4,3],2);`):


elif nops([args])=1 and op(1,[args])=Targem then
print(`Targem(n,w), inputs a positive integer n and a partial permutation w, outputs the reduction of w followed by the`):
print(`complement of the entries of w with respect to {1, ...,n} . Try:`):
print(` Targem(5,[1,5,3]); `):

elif nops([args])=1 and op(1,[args])=UIpats then
print(`UIpats(k,j): the set of ultimately increasing patterns of length k where the last k-j entries are increasing.`):
print(`Try: `):
print(`UIpats(5,2); `):

elif nops([args])=1 and op(1,[args])=WtE then
print(`WtE(S,tau,t): given a set of permutations S, outputs the weight enumerator according to the`):
print(`weight t^NumberOfOccurencesOfPattern. Try: `):
print(`WtE(permute(4),[1,2,3],t); `):

print(``):


else
print(`There is no ezra for`,args):
fi:
 
end:

with(combinat):


#SubWords(w,k): all the subwords of w of length k. Try:
#SubWords([1,4,3],2);
SubWords:=proc(w,k) local gu,gu1,i1:
option remember:

if k>nops(w) then
 RETURN({});
 
elif k=nops(w) then

 RETURN({w});

else
gu:=IV(nops(w),k):

RETURN({seq([seq(w[gu1[i1]],i1=1..k)],gu1 in gu)}):

fi:
end:

###from AVOID



#CleanUpP(n,S): cleans up the set of words S such that none is a subword of another word
CleanUpP:=proc(n,S) local S1,T,ma,i,w,j:

ma:=max(seq(nops(w), w in S)):

for i from 1 to ma do
 T[i]:={}:
od:

for w in S do
 T[nops(w)]:=T[nops(w)] union {w}:
od:

S1:=S:
for i from 1 to ma do
 for w in T[i] do
   for j from 1 to i-1 do
     if SubWords(w,j) intersect T[j]<>{} then
       S1:=S1 minus {w}:
     fi:
   od:
 od:
od:

Nake(n,S1):

end:

#RPerms(n,S): Inputs a positive inetger n, and a set of words in {1,..n} with distinct letters,
#outputs the set of n-permutations that DO Contain, as subwords the members of S. Try:
#RPerms(4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]});
RPerms:=proc(n,S) local gu,i,mu,S1,j,mu1:
option remember:

if n=0 then
 if member([],S) then
   RETURN({[]}):
 else
  RETURN({}):
fi:
fi:

gu:={}:

for i from 1 to n do

 S1:=ImpliedM(i,S,n):

  mu:=RPerms(n-1,S1):

  mu:=subs({seq(j=j+1,j=i..n-1)},mu):
  mu:={seq([i,op(mu1)],mu1 in mu)}:
  gu:=gu union mu:

od:

gu:

end:


#RNuP(n,S): Inputs a positive inetger n, and a set of words in {1,..n} with distinct letters,
#outputs the number of n-permutations that do not contain, as subwords the members of S. Try:
#RNuP(4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]});
RNuP:=proc(n,S) local Y,i:
option remember:

if n=0 then
 if member([],S) then
   RETURN(1):
 else
  RETURN(0):
fi:
fi:


Y:=KidsP([n,S]):


add(Y[i][1]*RNuP(op(Y[i][2])),i=1..nops(Y)):

end:


#KidsP(T): Inputs a state T=[n,S] where S is a set of actual patterns and we are interested
#in permutations of {1,...,n} avoiding the patterns in S, outputs its children state
#fulfillied by chopping the first letter (and reducing) if it is i=1, ...,n, so the
#output is a list of states of length n whose first component is n-1. Try:
#KidsP([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]);
KidsP:=proc(T) local i,n,S:
option remember:

n:=T[1]:
S:=T[2]:

[seq(CleanUpP(n-1,ImpliedM(i,S,n)),i=1..n)]:

end:

#ImplliedM(i,S,n): Given a set of mistakes that permutations of length n may not contain, outputs the set of mistakes
#that the the permutations obtained by chopping the first entry, i, and then reducing it to from {1,..,i-1,i+1, ..n}
#to {1, ..., n-1}. Try:
#ImpliedM(2,{[1,2,4],[2,3,4]},4);

ImpliedM:=proc(i,S,n) local S1,w,j:

S1:={}:

for w in S do

 if not member(i,w) then
   S1:= S1 union {w}:
 elif w[1]=i then
   S1:=S1 union {[op(2..nops(w),w)]}:
 fi:
od:

subs({seq(j=j-1,j=i+1..n)},S1):

end:


#Nake(n,S): inputs a positive integer n, and a set of words in {1,...,n}
#outputs a pair
#[coeff,[k,S1]] where k<=n and S1 is hopefully simpler than S and such that
# NuP(n,S)=coeff*NuP(k,S1). Try
#Nake(3,{[2,3]});
Nake:=proc(n,S) local Mish,i,k,s1,T:
Mish:={seq(op(s1),s1 in S)}:
if nops(Mish)=n then
 RETURN([1,[n,S]]):
fi:

k:=nops(Mish):
Mish:=sort(convert(Mish,list)):
T:=subs({seq(Mish[i]=i,i=1..k)},S):
[binomial(n,k)*(n-k)!,[k,T]]:
end:

###end from AVOID

#########start from GuessPol
#GuessPol1(L,d,n,s0): guesses a polynomial of degree d in n for
# the list L, such that L[i]=P[i] for i>=s0 for example, try: 
#GuessPol1([(seq(i,i=1..10),1,n,1);
GuessPol1:=proc(L,d,n,s0) local P,i,a,eq,var:
if s0+d+1>nops(L) then
 ERROR(`the list is too small`):
fi:

P:=add(a[i]*n^i,i=0..d):
var:={seq(a[i],i=0..d)}:
eq:={seq(subs(n=i,P)-L[i],i=s0..s0+d+1)}:

var:=solve(eq,var):

if var=NULL then
 RETURN(FAIL):
fi:

subs(var,P):

end:



#GuessPol(L,n,s0): guesses a polynomial of degree d in n for
# the list L, such that L[i]=P[i] for i>=s0 for example, try: 
#GuessPol([(seq(i,i=1..10),n,1);
GuessPol:=proc(L,n,s0) local d,gu:

for d from 0 to nops(L)-s0-2 do
 gu:=GuessPol1(L,d,n,s0):
 if gu<>FAIL then
    RETURN(gu):
 fi:
od:

FAIL:

end:

#GuessPol1T(L,d,n,s0): guesses a polynomial of degree d in n for
# the list L, such that L[i]=P[i] for i>=s0 for example, try: 
#GuessPol1T([(seq(i,i=1..10),1,n,1);
GuessPol1T:=proc(L,d,n,s0) local P,i,a,eq,var:
if d>=nops(L)-s0-1 then
 ERROR(`the list is too small`):
fi:

P:=add(a[i]*n^i,i=0..d):
var:={seq(a[i],i=0..d)}:
eq:={seq(subs(n=i,P)-L[i],i=s0..s0+d+1)}:

var:=solve(eq,var):

if var=NULL then
 RETURN(FAIL):
fi:

subs(var,P):

end:



#GuessPolT(L,n,s0): guesses a polynomial of degree d in n for
# the list L, such that L[i]=P[i] for i>=s0 for example, try: 
#GuessPolT([(seq(i,i=1..10),n,1);
GuessPolT:=proc(L,n,s0) local d,gu:

for d from 0 to nops(L)-s0-3 do
 gu:=GuessPol1T(L,d,n,s0):
 if gu<>FAIL then
    RETURN(gu):
 fi:
od:

FAIL:

end:
#########end from GuessPol


#redu(pi): the reduction of the permutation pi, try:
#redu([2,6,3]);
redu:=proc(pi) local k,pi1,i,T:
k:=nops(pi):
pi1:=sort(pi):

for i from 1 to k do
T[pi1[i]]:=i:
od:

[seq(T[pi[i]],i=1..k)]:

end:

#IV(n,k): The set of all  increasing sequences [i1,...,ik] such that 1<=i1<i2<...<ik<=n, Try:
#IV(5,3);
IV:=proc(n,k) local lu,j,lu1:
option remember:
if k=0 then
 RETURN({[]}):
fi:

if k=1 then
 RETURN({seq([j],j=1..n)}):
fi:

lu:=IV(n,k-1):


{seq(seq([op(lu1),j],j=lu1[k-1]+1..n),lu1 in lu)}:


end:

#SpellOut(tau,n): inputs a pattern tau  and a positive integer n outputs the set of all manifestations of tau.
#Try:
#SpellOut([2,1,3],4);
SpellOut:=proc(tau,n) local k,gu,i,gu1:

k:=nops(tau):
if k>n then
 RETURN({}):
fi:

gu:=IV(n,k):

{seq(subs({seq(i=gu1[i], i=1..k)},tau),gu1 in gu)}:

end:

#Merge1(sig1,sig2,S1): inputs two words, sig1, sig2, with distinct letters, such that their union is {1, ...,n}
#where n=|sig1|+|sig2| and S1 a subset of{1,..,n}, creates a permutation of {1,...,n} such
#that the members of sig1 go to the slots of S1 and the rest to sig2, in that order. Try
#Merge1([1,3,2],[5,4],[1,3,5]);
Merge1:=proc(sig1,sig2,S1) local n,gu,sig1a,sig2a,i:
n:=nops(sig1)+nops(sig2):



gu:=[]:

sig1a:=sig1:
sig2a:=sig2:

for i from 1 to n do
 if member(i,S1) then
  gu:=[op(gu),sig1a[1]]:
  sig1a:=[op(2..nops(sig1a),sig1a)]:
 else
  gu:=[op(gu),sig2a[1]]:
  sig2a:=[op(2..nops(sig2a),sig2a)]:
fi:
od:
gu:
end:



#BGslow(sig,r): Inputs a permutation, sig, and a non-negative  integer r, outputs the set of permutations
#of length |sig|+r that contain at least one occurence of the pattern sig. Try:
#BGslow([1,3,2],2);  Does it slowly, the old way,
BGslow:=proc(sig,r) local n,mu,lu,gu,vu,S,i,mu1,lu1,vu1:
option remember:
n:=nops(sig)+r:

S:={seq(i,i=1..n)}:

mu:=SpellOut(sig,n):
lu:=IV(n,r):

gu:={}:

for mu1 in mu do
vu:=permute(S minus convert(mu1,set)):
gu:=gu union {seq(seq(Merge1(vu1,mu1,lu1),vu1 in vu),lu1 in lu)}:
od:

gu:

end:


#BG(sig,r): Inputs a permutation, sig, and a non-negative  integer r, outputs the set of permutations
#of length |sig|+r that contain at least one occurence of the pattern sig. Try:
#BG([1,3,2],2);  
BG:=proc(sig,r)  local k:
option remember:
k:=nops(sig):
RPerms(k+r,SpellOut(sig,k+r)):
end:



#BreakUp(S): the break up of a set of permutations S according to its first element
#try:
#BreakUp(permute(3),3);
BreakUp:=proc(S,n) local i,T,s:
for i from 1 to n do
 T[i]:={}:
od:

for s in S do
T[s[1]]:=T[s[1]] union {s}:
od:

[seq(T[i],i=1..n)]:

end:







#Mekomot(pi,tau): the set of COMPLEMENT of places where the pattern tau occurns in the permutation pi
#Try
#Mekomot([1,2,3,4],[1,2,3]);
Mekomot:=proc(pi,tau) local n,i,S,k,mu,gu,mu1,i1:
n:=nops(pi):
S:={seq(i,i=1..n)}:
k:=nops(tau):
if k>n then
 RETURN({}):
fi:

mu:=IV(n,k):

gu:={}:


for mu1 in mu do

if redu([seq(pi[mu1[i1]],i1=1..k)])=tau then
  gu:=gu union{ sort( convert(S minus convert(mu1,set),list))}:
fi:
od:

gu:

end:


#WtE(S,tau,t): given a set of permutations S, outputs the weight enumerator according to the
#weight t^NumberOfOccurencesOfPattern, try
#WtE(permute(4),[1,2,3],t);
WtE:=proc(S,tau,t) local pi:

add(t^nops(Mekomot(pi,tau)), pi in S):
end:

#Prepend1(i,pi): inputs a positive  integer i and a permutation pi of {1, ...,n}, and 1<=i<=n, outputs
#the permutation of {1,...,n+1} whose first entry is i and such that the reduction of the 2nd through n+1 entries
#is pi. Try:
#Prepend1(3,[1,3,2]);
Prepend1:=proc(i,pi) local n,j:
n:=nops(pi):

[i,op(subs({seq(j=j+1,j=i..n)},pi))]:
end:


#Prepend(i,s): inputs a positive  integer  and a set, S,  of permutation of {1, ...,n}, and 1<=i<=n, outputs
#the set of permutation of {1,...,n+1} whose first entry is i and such that the reduction of the 2nd through n+1 entries
#is pi. Try:
#Prepend(3,{[1,3,2]});
Prepend:=proc(i,S) local pi:
{seq(Prepend1(i,pi), pi in S)}:
end:




#Insert1(i,p,pi): inputs a positive  integer i, and a positive integer p
#and a permutation pi of {1, ...,n}, and 1<=i,p<=n+1, outputs
#the permutation of {1,...,n+1} whose p-th entry is i 
#and such that the reduction of the permutation obtained by deleting i (that is
#of course in the p-th place)
#is pi. Try:
#Insert1(3,1,[1,3,2]);
Insert1:=proc(i,p,pi) local n,j,lu:
n:=nops(pi):

lu:=[op(subs({seq(j=j+1,j=i..n)},pi))]:

[op(1..p-1,lu),i,op(p..n,lu)]:
end:



#Insert(i,pi): inputs a positive  integer i, and  outputs the set of permutations
#and a permutation pi of {1, ...,n}, and 1<=i,p<=n+1, outputs
#of {1,...,n+1} where i can be anywhere, and deleting i, reduces to a permutation that is pi
#Try:
#Insert(3,[1,3,2]);
Insert:=proc(i,pi) local n,p:
n:=nops(pi):
{seq(Insert1(i,p,pi),p=1..n+1)}:

end:

#INSERT(i,S): inputs a set of permutations all of the same lengths, n, say,
#outputs the set Insert(i,pi) over all the permutations of pi, try:
#INSERT(1,permute(3));
INSERT:=proc(i,S) local pi:
{seq(op(Insert(i,pi)), pi in S)}:
end:


#CheckCD1(k1): checks the scheme for codimension one bad guys containing the
#increasing pattern
#Try CheckCD1(3);
CheckCD1:=proc(k1) local i1,gu,lu11,lu10,lu20,lu21,t0,i2:
t0:=time():

print(`An empirical check for the scheme for generating Co-Dimension 1 permutations`):
print(`for permutations of length`, k1+1 ):
print(`Containing an increasing pattern of length`, k1):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):


gu:=BreakUp(BG([seq(i1,i1=1..k1)],1),k1+1):

print(`-----------------------------------`):
print(`If the first entry is`, 1):
print(``):
print(`The set with codimension 0 of length one less, namely of length`, k1 ):
print(` with 1 prepended is`):
lu10:=Prepend(1,BG([seq(i1,i1=1..k1)],0)):
print(lu10):
print(`The set with codimension 1 with length one less with 1 prepended is`):
lu11:=Prepend(1,BG([seq(i1,i1=1..k1-1)],1)):

print(lu11):

if lu10 minus lu11={} then
 print(`the former is a subset of the latter`):
fi:

if gu[1]=lu11 then
 print(`The set of permutations of length`, k1+1, `starting with 1, `):
 print(` containing an increasing subsequence of length`, k1):
 print(`is the same as the latter`):
fi:

print():
print(`---------------------------------------------`):
print():

print(`If the first entry is`, 2):
print(``):

print(`The set with codimension 0 of length one less with 2 prepended is`):
lu20:=Prepend(2,BG([seq(i1,i1=1..k1)],0)):
print(lu20):
print(`The set with codimension 0 of length two less, with 1 inserted and 2 prepended is`):
lu21:=Prepend(2,INSERT(1,BG([seq(i1,i1=1..k1-1)],0))):
print(lu21):

if lu20 minus lu21={} then
 print(`the former is a subset of the latter`):
fi:


if gu[2]=lu21 then
 print(`The set of permutations of length`, k1+1, `starting with 2, `):
 print(` containing an increasing subsequence of length`, k1):
 print(`is the same as the latter`):
fi:

print():
print(`---------------------------------------------`):
print():



for i2 from 3 to k1+1 do
print(`If the first entry is`, i2):
print(``):

print(`The set with codimension 0 of length one less with`,  i2,  ` prepended is`):
lu20:=Prepend(i2,BG([seq(i1,i1=1..k1)],0)):

print(lu20):


if gu[i2]=lu20 then
 print(`The set of permutations of length`, k1+1, `starting with`, i2):
 print(` containing an increasing subsequence of length`, k1):
 print(`is the same as the latter`):
fi:

print():
print(`---------------------------------------------`):
print():
od:	

print(`This ends this check that took`, time()-t0, `seconds. `):

end:




#CheckCD2(k1): checks the scheme for codimension two bad guys containing the
#increasing pattern
#Try CheckCD2(3);
CheckCD2:=proc(k1) local i1,gu,lu11,lu10,lu20,lu21,t0,i2:
t0:=time():

print(`An empirical check for the scheme for generating Co-Dimension 2 permutations`):
print(`for permutations of length`, k1+2 ):
print(`Containing an increasing pattern of length`, k1):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):


gu:=BreakUp(BG([seq(i1,i1=1..k1)],2),k1+2):

print(`-----------------------------------`):
print(`If the first entry is`, 1):
print(``):
print(`The set with codimension 1 of length one less with 1 prepended is`):
lu10:=Prepend(1,BG([seq(i1,i1=1..k1)],1)):
print(lu10):
print(`The set with codimension 2 with length one less with 1 prepended is`):
lu11:=Prepend(1,BG([seq(i1,i1=1..k1-1)],2)):

print(lu11):

if lu10 minus lu11={} then
 print(`the former is a subset of the latter`):
fi:


if gu[1]=lu11 then
 print(`The set of permutations of length`, k1+2, `starting with 1, `):
 print(` containing an increasing subsequence of length`, k1):
 print(`is the same as the latter`):
fi:

print():
print(`---------------------------------------------`):
print():

print(`If the first entry is`, 2):
print(``):

print(`The set with codimension 1 of length one less with 2 prepended is`):
lu20:=Prepend(2,BG([seq(i1,i1=1..k1)],1)):
print(lu20):
print(`The set with codimension 1 of length two less, with 1 inserted and 2 prepended is`):
lu21:=Prepend(2,INSERT(1,BG([seq(i1,i1=1..k1-1)],1))):
print(lu21):

if lu20 minus lu21={} then
 print(`the former is a subset of the latter`):
fi:


if gu[2]=lu21 then
 print(`The set of permutations of length`, k1+1, `starting with 2, `):
 print(` containing an increasing subsequence of length`, k1):
 print(`is the same as the latter`):
fi:

print():
print(`---------------------------------------------`):
print():
	

####testing i1=3

print(`If the first entry is`, 3):
print(``):

print(`The set with codimension 1 of length one less with 3 prepended is`):
lu20:=Prepend(3,BG([seq(i1,i1=1..k1)],1)):
print(lu20):
print(`The set with codimension 0 of length two less, with 1 and 2 inserted and 3 prepended is`):
lu21:=Prepend(3, INSERT(2,INSERT(1,BG([seq(i1,i1=1..k1-1)],0)))):
print(lu21):

if lu20 minus lu21={} then
 print(`the former is a subset of the latter`):
 print(`The following belong to both `):

  print(lu21 intersect lu20):

 print(`the number that belong to both is`):
  print(nops(lu21 intersect lu20)):

else
 print(`the former is not a subset of the latter`):
 print(`The following belong to lu20 but not to lu21`):

 print(lu20 minus lu21):

 print(`The following belong to lu21 but not to lu20`):

  print(lu21 minus lu20):

 print(`The following belong to both `):

  print(lu21 intersect lu20):

 print(`the number that belong to both is`):
  print(nops(lu21 intersect lu20)):

fi:

 print(`The set of permutations of length`, k1+2, `starting with 3, `):
 print(` containing an increasing subsequence of length`, k1, ` is `):
 print(gu[3]):

if lu21 union lu20=gu[3] then
 print(`This is the same as the union of lu20 and lu21`):
fi:

print():
print(`---------------------------------------------`):
print():


##end testing i1=3

for i2 from 4 to k1+2 do
print(`If the first entry is`, i2):
print(``):

print(`The set with codimension 1 of length one less with`,  i2,  ` prepended is`):
lu20:=Prepend(i2,BG([seq(i1,i1=1..k1)],1)):

print(lu20):


if gu[i2]=lu20 then
 print(`The set of permutations of length`, k1+2, `starting with`, i2):
 print(` containing an increasing subsequence of length`, k1):
 print(`is the same as the latter`):
fi:

print():
print(`---------------------------------------------`):
print():
od:	

print(`This ends this check that took`, time()-t0, `seconds. `):

end:


#Akr(k,r): the set of permutations of {1,...,k+r} containing at least one pattern 1...k, try:
#Akr(4,2);
Akr:=proc(k,r) local i:
option remember:

BG([seq(i,i=1..k)],r):

end:

#NuAkr(k,r): the NUMBER of permutations of {1,...,k+r} containing at least one pattern 1...k, try:
#NuAkr(4,2);
NuAkr:=proc(k,r) local i:
option remember:

NuBG([seq(i,i=1..k)],r):

end:



#Akri(k,r,i): the set of permutations of {1,...,k+r} containing at least one pattern 1...k, and start with i.Try:
#Akri(4,2,2);
Akri:=proc(k,r,i)
option remember:
BreakUp(Akr(k,r),k+r)[i]:
end:

#Bkri(k,r,i): the subset of Akri(k,r,i) obtained by taking Akr(k,r-1) and prepending i, try
#Bkri(k,r,i)
Bkri:=proc(k,r,i) 
option remember:
Prepend(i,Akr(k,r-1)):
end:


#Ckri(k,r,i): the subset of Akri(k,r,i) obtained by taking Akr(k,r-i) inserting {1,..,i-1} every which way
#and prepending i. Try:
#Ckri(4,2,2);
Ckri:=proc(k,r,i)  local gu,j:
option remember:

if i>r+1 then
 RETURN({}):
fi:

gu:=Akr(k-1,r+1-i):

for j from 1 to i-1 do
 gu:=INSERT(j,gu):
od:

Prepend(i,gu):
end:


#BCkri(k,r,i): Bkri(k,r,i) interesect Ckri(k,r,i)
#and prepending i. Try:
#BCkri(4,2,2);
BCkri:=proc(k,r,i)  option remember:
Bkri(k,r,i) intersect Ckri(k,r,i):
end:



#Dif1(L,r): the r-th difference of the sequence L, try:
#Dif1([seq(i1^2,i1=1..10)],2);
Dif1:=proc(L,r) local i1,j1,gu:
gu:=L:

for j1 from 1 to r do
 gu:=[seq(gu[i1+1]-gu[i1],i1=1..nops(gu)-1)]:
od:

gu:
end:

Redu:=proc(S) local pi: {seq(redu(pi),pi in S)}:end:

#BeHead(S): inputs a set of permutations S, outputs the set obtained by choping the
#first entry and reducting. Try:
#BeHead(convert(permute(4),set)):
BeHead:=proc(S) local pi:
{seq(redu([op(2..nops(pi),pi)]), pi in S)}:
end:




#CheckCDr(k1,r): checks the scheme for codimension-r permutations of {1,..., k1+r}, i.e.
#permutations of {1, ..., k1+r} CONTAINTING an increasing sunsequence of lengtk .
#Try CheckCDr(3,2);
CheckCDr:=proc(k1,r) local i,gu, gu1,gu2,t0:
t0:=time():


print(`An empirical investigation for the scheme for generating Co-Dimension`, r,  ` permutations `):
print(`for permutations of length`, k1+r ):
print(`Containing an increasing pattern of length`, k1):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):


for i from 1 to k1+r do

gu:=Akri(k1,r,i):

gu1:=Bkri(k1,r,i):
gu2:=Ckri(k1,r,i):

print():
print(`-------------------------------------------------`):
print():
print(`If the first entry is`, i):

if gu=gu1 union gu2 then
 print(`It is indeed a union of B and C `):
 print(`Number of elements in B:`, nops(gu1)):
 print(`Number of elements in C:`, nops(gu2)):
 print(`Number of common elements:`, nops(gu1 intersect gu2)):
fi:

od:

print(`This took`,  time()-t0, `seconds. `):
end:





#BreakUpR(S,n): the reduced break up of a set of permutations S according to its first element
#try:
#BreakUpR(permute(3),3);
BreakUpR:=proc(S,n) local gu,i:
gu:=BreakUp(S,n):

[seq(Redu(BeHead(gu[i])),i=1..nops(gu))]:
end:





#NuBG(sig,r): Inputs a permutation, sig, and a non-negative  integer r, outputs the NUMBER of permutations
#of length |sig|+r that contain at least one occurence of the pattern sig. Try:
#NuBG([1,3,2],2);  
NuBG:=proc(sig,r)  local k:
option remember:
k:=nops(sig):
RNuP(k+r,SpellOut(sig,k+r)):
end:







#KidsPP(T):  A condensed version of KidsP(T) (q.v) where the younger childen are lumped together if
#they are identical, leading to (in the case of 1...k containing) finitely many children. Try:
#KidsPP([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]);
KidsPP:=proc(T) local gu,j,mu:
option remember:

gu:=KidsP(T):

for j from nops(gu)-1 by -1 while gu[j]=gu[nops(gu)] do od:

mu:=gu[j+1]:

[op(1..j,gu) , [mu[1]*(nops(gu)-j),mu[2]]  ]:

end:





#SOD(k,r,L): inputs positive integers k and r, and a list L of positive integers
#outputs the descendant of SpellOut([1...k],k+r) given by the list L, 
#accodring to KidsPP (q.v). i.e.first you go to the L[1]'s child, then to the latters's L[2] child. etc.
#it returns FAIL if you encounter something undefined on the route
#Try:
#SOD(4,2,[1]);
SOD:=proc(k,r,L) local i1,gu,L1:
option remember:
if not ( type(k,integer) and type(r,integer) and k>0 and r>=0 and type(L,list)) then
 print(`Bad input`):
 RETURN(FAIL):
fi:


if L=[] then
 RETURN([k+r,SpellOut([seq(i1,i1=1..k)],k+r)]):
fi:

L1:=[op(1..nops(L)-1,L)]:

gu:=SOD(k,r,L1):

if gu=FAIL then
   RETURN(FAIL):
fi:

gu:=KidsPP(gu):

if L[nops(L)]>nops(gu) then
  RETURN(FAIL):
fi:

gu[L[nops(L)]][2]:

end:



#FindPrev0(S,k,r): inputs a set S of forbidden words, finds a k1 and r1 with k1<=k, r1<=r 
#such that it equals SOD(k1,r1,[]). For example, try:
#FindPrev0(SOD(5,2,[1]),5,2);
FindPrev0:=proc(S,k,r) local k1,r1:
option remember:

for k1 from 1 to k do
 for r1 from 0 to r do
  if SOD(k1,r1,[])=S then
    RETURN([k1,r1]):
  fi:
 od:
od:

FAIL:

end:

#FindFT(k,r,L,De): Inputs positive integers k and r, a list L, and a positive integer De
#tries to find a family tree, for SOD(k,r,L) ,of depth <=De, for
#the set of restrictions S. It it fails, it returns FAIL. Try:
#FindFT(5,1,[],2);
FindFT:=proc(k,r,L,De) local mu,gu,i,gu1,lu,Yel, coe:

if De<0 then
 RETURN(FAIL):
fi:

mu:=SOD(k,r,L):

if mu=FAIL then
  RETURN(FAIL):
fi:

lu:=FindPrev0(mu,k,r):



if L<>[] and lu<>FAIL then
 RETURN(lu):
fi:


gu:=[]:

Yel:=KidsPP(mu):

for i from 1 to nops(Yel) do:

 coe:=Yel[i][1]:

if Yel[i][2]<>[0,{}] then
 gu1:=FindFT(k,r,[op(L),i],De-1):

  if gu1=FAIL then
      RETURN(FAIL):
  else

     gu:=[op(gu),[coe,gu1]]:

  fi:
fi:

od:

gu:

end:

 




#Crimes(pi,sig): The set of occurrences of the pattern sig in pi.
#Try: Crimes([1,3,2,4],[1,2,3]);
Crimes:=proc(pi,sig) local n,k,gu,lu1,i1,lu:
n:=nops(pi):
k:=nops(sig):

lu:=IV(n,k):

gu:={}:
for lu1 in lu do

if redu([seq(pi[lu1[i1]],i1=1..k)])=sig then

  gu:=gu union {lu1}:

fi:

od:

gu:

end:



#BGd(sig,r): Like BG(sig,r) (q.v), but broken up into a list, where the i-th item is
#the set of permutations that have exactly i crimes. Try:
#BGd([1,3,2],2);  
BGd:=proc(sig,r)  local gu,M,i,mc,gu1,kama,i1,T:
gu:=BG(sig,r):

M:=binomial(nops(sig)+r,nops(sig)):

for i from 1 to M do
T[i]:={}:
od:

mc:=1:

for gu1 in gu do
kama:=nops(Crimes(gu1,sig)):
T[kama]:=T[kama] union {gu1}:

if kama>mc then
 mc:=kama:
fi:

od:

[seq(T[i1],i1=1..mc)]:

end:







#IsLeaf(L): is L a weighted-leaf? Try:
#IsLeaf([3,1]);
IsLeaf:=proc(L) :

if nops(L)=2 and type(L[1],integer) and type(L[2],integer) then
 RETURN(true):
else
 RETURN(false):
fi:

end:

#IsTree(T): is T a weighted-tree? Try:
#IsTree([[4,[3,1]],[3,[2,1]]]);

IsTree:=proc(T) local i:

if not type(T,list) then
 RETURN(false):
fi:

if IsLeaf(T) then
 RETURN(true):
fi:

for i from 1 to nops(T) do
 if not type(T[i][1],integer) then
  RETURN(false):
 fi:

   if not IsTree(T[i][2]) then
     RETURN(false):
   fi:
od:

true:

end:


#AreComp(T1,T2): are the family trees T1 and T2 compatible?. Try:
#AreComp(FindFT(5,1,2),FindFT(6,1,2));
AreComp:=proc(T1,T2) local i:

if IsLeaf(T1) then  
  if IsLeaf(T2) and T1[2]=T2[2] then
    RETURN(true):
   else
    RETURN(false):
  fi:
fi:


if not IsTree(T1) or not IsTree(T2) then
  RETURN(false):
fi:

if nops(T1)<>nops(T2) then
   RETURN(false):
fi:

for i from 1 to nops(T1) do
 if not AreComp(T1[i][2],T2[i][2]) then
   RETURN(false):
 fi:
od:

true:
  

end:


#GuessTreePol(L,k,Deg, k0): given a list of concrete trees, starting at k0, finds a symbolic tree such that
#if you plug in k=k0, ..., k=k0+nops(L), you would get L, try:
#GuessTreePol([seq([k1,0],k1=3..10)],k,2,3);
#GuessTreePol([seq([[k1,[k1,0]]],k1=3..10)],k,3);
GuessTreePol:=proc(L,k,Deg,k0) local i,j,gu1,gu2,T:

if Deg>=nops(L)-2 then
 ERROR(`the list is too small`):
fi:

if not type(L,list) then
   RETURN(FAIL):
fi:

for i from 1 to nops(L) do
 if not IsTree(L[i]) then
   RETURN(FAIL):
 fi:
od:



for i from 2 to nops(L) do
 if not AreComp(L[1],L[i]) then
  RETURN(FAIL):
 fi:
od:





		    
if IsLeaf(L[1]) then
 gu2:={seq(L[i][2],i=1..nops(L))}:
 if nops(gu2)<>1 then
    RETURN(FAIL):
  else
   gu2:=gu2[1]:
  fi:


gu1:=[0$(k0-1),seq(L[i][1],i=1..nops(L))]:

gu1:=GuessPol1(gu1,1,k,k0):

RETURN([gu1,gu2]):
fi:


T:=[]:
for i from 1 to nops(L[1]) do

gu1:=[0$(k0-1),seq(L[j][i][1],j=1..nops(L))]:


gu1:=GuessPol(gu1,k,k0):

if gu1=FAIL then
  RETURN(FAIL):
fi:

gu2:=GuessTreePol([seq(L[j][i][2],j=1..nops(L) )],k,Deg,k0):

if gu2=FAIL then
  RETURN(FAIL):
else
 T:=[op(T),[gu1,gu2]]:
fi:

od:

T:

end:


#FindFTs1(k,d,Deg,Dep): Inputs a symbol k and a codimension d , a list L, and  positive integers Deg and Dep
#outputs a poynomial scheme for enumerating permutations of {1, ..., k+d} that contain at least one
#increasing subsequence of length k. Try:
#FindFTs1(k,1,1,2);
FindFTs1:=proc(k,d,Deg,Dep) local L,k0:

L:=[seq(FindFT(k0,d,[],Dep),k0=d+1..d+1+Deg+4)]:

GuessTreePol(L,k,Deg,d+1):

end:

#FindFTs(k,d,Deg,Dep): Inputs a symbol k and a codimension d , a list L, and  positive integers Deg and Dep
#outputs a polynomial scheme for enumerating permutations of {1, ..., k+d} that contain at least one
#increasing subsequence of length k. Try:
#FindFTs(k,1,1,2);
FindFTs:=proc(k,d,Deg,Dep) local Deg1,Dep1,gu:
option remember:
for Deg1 from d to Deg do
 for Dep1 from d to Dep do
  gu:=FindFTs1(k,d,Deg1,Dep1):
   if gu<>FAIL then
    RETURN(gu):
   fi:
 od:
od:

FAIL:

end:



#EvalTree(T,V): inputs a weighted tree, and a symbol V, outputs the evaluation of the tree
#using the symbol V for function evaluation. The leaves [a,b] get assigned V(a,b), and
#the rest is recursive. Try:
#EvalTree(FindFTs(k,1,1,2),V):
EvalTree:=proc(T,V) local i,gu:


if nops(T)=2 and type(T[2],integer) then
 RETURN(V(T[2])(T[1])):
fi:

gu:=0:

for i from 1 to nops(T) do
 gu:=expand(gu+T[i][1]*EvalTree(T[i][2],V)):
od:

gu:

end:



#EvalTreeK(T,V,k,K): inputs a weighted tree, T, phrased in terms of the variable k,
#and  symbols V, k, and K , outputs the evaluation of the tree
#using the symbol V for function evaluation. The leaves [a,b] get assigned K^(a-k)V(b), and
#the rest is recursive. Try:
#EvalTreeK(FindFTs(k,1,1,2),V,k,K):
EvalTreeK:=proc(T,V,k,K) local i,gu:


if nops(T)=2 and type(T[2],integer) then
 RETURN(K^(T[1]-k)*V(T[2])):
fi:

gu:=0:

for i from 1 to nops(T) do
 gu:=expand(gu+T[i][1]*EvalTreeK(T[i][2],V,k,K)):
od:

gu:

end:

#BGpolI(k,d,Dep): the first d polynomials expressions in k, for  the number of permutations of length d+k
#that contain an increasing subsequence of length k, by finding trees of depth <=Dep. Try
#BGpolI(k,2,2,2);
BGpolI:=proc(k,d,Deg,Dep) local T,V,i,gu,lu,lu1,K,j1,j2,ku,coe,i1,n:
gu:=[]:

for i from 1 to d do
 T:=FindFTs(k,i,Deg,Dep):
 if T=FAIL then
   RETURN(gu):
 fi:



lu:=EvalTreeK(T,V,k,K):

	  
lu:=expand(lu-K^(-1)*V(i)):

ku:=subs(K=1,coeff(lu,V(0),1)):

for j1 from 1 to i-1 do
lu1:=coeff(lu,V(j1),1):

for j2 from 0 to -ldegree(lu1,K) do
 ku:=expand(ku+coeff(lu1,K,-j2)*subs(k=k-j2,gu[j1])):
od:


od:

ku:=expand(subs(n=k,sum(ku,k=1..n))):


coe:=NuBG([seq(i1,i1=1..2*i)],i):


ku:=expand(ku+coe-subs(k=2*i,ku)):


gu:=[op(gu),ku]:

od:

gu:

end:


#SipurI(k,d,Deg,Dep,V): inputs a symbol k, a positive integer d, and positive integers Deg and Dep
#and a symbol V
#outputs an article with rigorously proved polynomial expressions for the
#number of permutations of length k+i containing an increasing subsequence of length i for i from 1 to d
#Deg is the maximum degree and Dep the maximum depth of the trees. If these are not big enough, it may
#not go all the way to d. Try:
#SipurI(k,2,2,2,V);
SipurI:=proc(k,d,Deg,Dep,V) local gu,i,T,t0:

t0:=time():

gu:=BGpolI(k,d,Deg,Dep):

print(``):
print(`Explicit Polynomial Expressions in`, k, `for the Number of Permutations of length k+i, Containing an`):
print(`increasing sequence of length k for i from 1 to`, nops(gu)):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):

print(`Theorem Number`, 0, ` Let `, V(0)(k), `be the number of permutations of length`, k, `that include at least one increasing subsequence of`):
print(` length `, k, `then `):
print(``):
print(V(0)(k)=1):
print(`Proof: trivial (you do it!)`):
print(``):

for i from 1 to nops(gu) do

print(`Theorem Number`, i, ` Let `, V(i)(k), `be the number of permutations of length`, k+i, `that include at least one increasing subsequence of`):
print(` length `, k, `then `):
print(``):
print(V(i)(k)=gu[i]):

print(``):
print(`and in Maple notation:`):
print(``):
lprint(V(i)(k)=gu[i]):
print(``):
T:=FindFTs(k,i,Deg,Dep):
print(`Proof: The family tree  of our class of permutation can be seen to be`):
print(``):
print(T):
print(``):
print(`This implies the recurrence `):
print(V(i)(k)=EvalTree(T,V)):
print(``):
print(`and the statement follows by induction. QED `):

od:

print(`This ends this article, that took`, time()-t0, `seconds to generate. `):

end:



#SODg(sig,r,L): inputs a pattern sig, of length k, say, and a non-negative integer r, and a list L of positive integers
#outputs the descendant of SpellOut(sig,k+r) given by the list L, 
#accodring to KidsPP (q.v). i.e.first you go to the L[1]'s child, then to the latters's L[2] child. etc.
#it returns FAIL if you encounter something undefined on the route
#Try:
#SODg([1,2,3,4],2,[1]);
SODg:=proc(sig,r,L) local k,gu,L1:
option remember:

if not ( type(sig,list) and type(r,integer) and r>=0 and type(L,list)) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

k:=nops(sig):

if L=[] then
 RETURN([k+r,SpellOut(sig,k+r)]):
fi:

L1:=[op(1..nops(L)-1,L)]:

gu:=SODg(sig,r,L1):

if gu=FAIL then
   RETURN(FAIL):
fi:

gu:=KidsPP(gu):

if L[nops(L)]>nops(gu) then
  RETURN(FAIL):
fi:

gu[L[nops(L)]][2]:

end:



#FindPrev0g(S,k,r): inputs a set S of forbidden words, finds a pattern sig1, with nops(sig1)<=k  and r1 with r1<=r 
#such that it equals SODg(sig1,r1,[]). For example, try:
#FindPrev0g(SODg([1,2,3,4,5],2,[1]),5,2);
FindPrev0g:=proc(S,k,r) local k1,lu,r1,i1:
option remember:

for k1 from 1 to k do
lu:=permute(k1):

 for i1 from 1 to nops(lu) do

 for r1 from 0 to r do
  if SODg(lu[i1],r1,[])=S then
    RETURN([lu[i1],r1]):
  fi:
 od:
 od:
od:

FAIL:

end:


#FindFTg(sig,r,L,De): Inputs a pattern, sig, of size  k, say, a non-neg. integer, r, a list L, and a positive integer De
#tries to find a family tree, for SODg(sig,r,L) ,of depth <=De, for
#the set of restrictions S. It it fails, it returns FAIL. Try:
#FindFTg([1,2,3,4,5],1,[],2);
FindFTg:=proc(sig,r,L,De) local k,mu,gu,i,gu1,lu,Yel, coe:

k:=nops(sig):

if De<0 then
 RETURN(FAIL):
fi:

mu:=SODg(sig,r,L):

if mu=FAIL then
  RETURN(FAIL):
fi:

lu:=FindPrev0g(mu,k,r):



if L<>[] and lu<>FAIL then
 RETURN(lu):
fi:


gu:=[]:

Yel:=KidsPP(mu):

for i from 1 to nops(Yel) do:

 coe:=Yel[i][1]:

if Yel[i][2]<>[0,{}] then
 gu1:=FindFTg(sig,r,[op(L),i],De-1):

  if gu1=FAIL then
      RETURN(FAIL):
  else

     gu:=[op(gu),[coe,gu1]]:

  fi:
fi:

od:

gu:

end:




#KickOut(pi,i): inputs a permutation pi and an entry i, outputs  the pair [location, reduced form of the 
#permutation obtained by deleting i. Try:
#KickOut([3,1,2,4,5],2);
KickOut:=proc(pi,i) local n,j:

n:=nops(pi):

for j from 1 to nops(pi) while pi[j]<>i do od:

if j=n+1 then
  RETURN(FAIL):
fi:

[redu([op(1..j-1,pi),op(j+1..n,pi)]),j]:

end:



#BGbu(sig,r): Same input as BG(sig,r) (q.v.), but the output is broken up to a pair (let k be the size of sig)
#[Set of Bad Guys where k+r is not needed, i.e. it still contains the pattern sig after removing the largest entry k+r,
#[" where they are needed, but broken-up according to the location of k+r]. Try
#BGbu([1,3,2],2);  
BGbu:=proc(sig,r)  local k,gu, gu1,gu2,pi,lu,mu:
k:=nops(sig):
gu:=BG(sig,r):
mu:=BG(sig,r-1):
gu1:={}:

gu2:={}:

for pi in gu do

lu:=KickOut(pi,k+r):

if member(lu[1],mu) then
 gu1:=gu1 union {lu}:
else
 gu2:=gu2 union {lu}:
fi:

od:

[gu1,gu2]:

end:

#Targem(n,w), inputs a positive integer n and a partial permutation w, outputs the reduction of w followed by the
#complement of the entries of w with respect to {1, ...,n} . Try:
# Targem(5,[1,5,3]);
Targem:=proc(n,w) local gu,pi,i:
pi:=redu(w):
gu:={seq(i,i=1..n)} minus {op(w)}:
[pi,gu]:
end:



#Kids(T): Like KidsP(T) (q.v.) but the output is in complementary notation. Try:
#Kids([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]);
Kids:=proc(T) local mu,mu1,gu,i,coe,j:
mu:=KidsP(T):

gu:=[]:

for i from 1 to nops(mu) do
mu1:=mu[i]:
coe:=mu1[1]:
mu1:=mu1[2]:
gu:=[op(gu), [coe,  {seq(Targem(mu1[1],mu1[2][j]),j=1..nops(mu1[2]))}]]:

od:
gu:

end:






#Etree1(n,S): Inputs a positive inetger n, and a set of words in {1,..n} with distinct letters,
#outputs a list of length n, such that the i-ith item is the number of such permutations that
#start with i. Try:
#Etree1(4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]});
Etree1:=proc(n,S) local Y,i:
option remember:

if n=0 then
 if member([],S) then
   RETURN([1]):
 else
  RETURN([0]):
fi:
fi:


Y:=KidsP([n,S]):


[seq( Y[i][1]*RNuP(op(Y[i][2])),i=1..nops(Y))]:

end:


#Etree(n,S,d): Inputs a positive inetger n, and a set of words in {1,..n} with distinct letters,
#and a positive integer d, finds the depth d tree. Try
#Etree(4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]},2);
Etree:=proc(n,S,d) local Y,i,gu:
option remember:

if d=0 then
 RETURN([RNuP(n,S)]):
end:

if n<d then
 RETURN(FAIL):
fi:

if d=1 then
 RETURN(Etree1(n,S)):
fi:

Y:=KidsP([n,S]):

gu:=[]:

for i from 1 to nops(Y) do

gu:=[op(gu), Y[i][1]*Etree(op(Y[i][2]),d-1) ]:

od:

end:

#AEtrees(k,r,d): all trees of depth d for co-dimension r patterns of length k. Try:
#AEtrees(5,2,1);
AEtrees:=proc(k,r,d) local gu,i:
gu:=permute(k):

{seq(Etree(k+r,SpellOut(gu[i],k+r),d) ,i=1..nops(gu))}:

end:





#CleanUp(S): cleans up the set of words S such that none is a subword of another word
CleanUp:=proc(S) local S1,T,ma,i,w,j:

ma:=max(seq(nops(w), w in S)):

for i from 1 to ma do
 T[i]:={}:
od:

for w in S do
 T[nops(w)]:=T[nops(w)] union {w}:
od:

S1:=S:
for i from 1 to ma do
 for w in T[i] do
   for j from 1 to i-1 do
     if SubWords(w,j) intersect T[j]<>{} then
       S1:=S1 minus {w}:
     fi:
   od:
 od:
od:

S1:
end:

#KidsOri(T): Inputs a state T=[n,S] where S is a set of actual patterns and we are interested
#in permutations of {1,...,n} avoiding the patterns in S, outputs its children state
#fulfillied by chopping the first letter (and reducing) if it is i=1, ...,n, so the
#output is a list of states of length n whose first component is n-1. Try:
#KidsOri([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]);
KidsOri:=proc(T) local i,n,S:
option remember:

n:=T[1]:
S:=T[2]:


[seq(CleanUp(ImpliedM(i,S,n)),i=1..n)]:

end:


#KidsC(T): Like KidOriP(T) (q.v.) but the output is in complementary notation. Try:
#KidsC([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]);
KidsC:=proc(T) local n,mu,gu,i,j:
n:=T[1]:
mu:=KidsOri(T):

gu:=[]:

for i from 1 to nops(mu) do

gu:=[op(gu),{seq(Targem(n,mu[i][j]),j=1..nops(mu[i]))}]:

od:

gu:

end:

#Des(T,L): inputs a pair [T,SetOfMistakes] and a list of integers L such that L[1]<=n,L[2]<=n-1 etc.
#finds the L[1]'s son and then the L[2]'s son of the latter all the way to L[nops(L)]. Try:
#Des([4,SpellOut([2,1,3],4)],[3,2]);
Des:=proc(T,L) local gu,i1,n,L1:
option remember:


if not (type(T,list) and nops(T)=2) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

if not type(L,list) then
 print(`Bad input`):
 RETURN(FAIL):
fi:


if L=[] then
 RETURN(T):
fi:

n:=T[1]:

if not ( type(L,list) and nops(L)<=n and min(seq(n-i1+1-L[i1],i1=1..nops(L)))>=0 ) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

L1:=[op(2..nops(L),L)]:

gu:=[n-1,KidsOri(T)[L[1]]]:
Des(gu,L1) :

end:


#DesPat(T,L): inputs a pair [T,SetOfMistakes] where T=[n,sig], and sig is a pattern
#and a list of integers L such that L[1]<=n,L[2]<=n-1 etc.
#finds the L[1]'s son and then the L[2]'s son of the latter all the way to L[nops(L)]
#of SpellOut(sig,n). Try:
#DesPat([5,[2,1,3]],[3,2]);
DesPat:=proc(T,L) local n,sig,gu:
option remember:
n:=T[1]:

sig:=T[2]:

gu:=SpellOut(sig,n):


Des([n,gu],L):

end:


#DesPats(T,L): inputs a pair [T,SetOfMistakes] where T=[n,S], and S  is a set of patterns
#and a list of integers L such that L[1]<=n,L[2]<=n-1 etc.
#finds the L[1]'s son and then the L[2]'s son of the latter all the way to L[nops(L)]
#of the union of SpellOut(sig,n) over all sig in S. Try:
#DesPats([5,{[2,1,3],[1,2,3]}],[3,2]);
DesPats:=proc(T,L) local n,S,gu,sig:
option remember:
n:=T[1]:

S:=T[2]:

gu:={seq(op(SpellOut(sig,n)),sig in S)}:


Des([n,gu],L):

end:






#Kabets(S): inputs a set of pairs {[perm,Set]} collects them under the first component.
#Try:
#Kabets({[[1,2],{1}],[[1,2],{2}],[[1,2,3],{c}]});
Kabets:=proc(S) local ku,T,ku1,s,i1:

ku:={seq(S[i1][1],i1=1..nops(S))}:

for ku1 in ku do
 T[ku1]:={}:
od:

for s in S do
 T[s[1]]:=T[s[1]] union {s[2]}:
od:

{seq([ku1,T[ku1]],ku1 in ku)}:
end:


#NewKidsOld(T): Like KidsP(T) (q.v.) but the output is in complementary notation. Try:
#NewKidsOld([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]);
NewKidsOld:=proc(T) local mu,mu1,gu,i,coe,j,ku,i1:
mu:=KidsP(T):

gu:=[]:

for i from 1 to nops(mu) do
mu1:=mu[i]:
coe:=mu1[1]:
mu1:=mu1[2]:
ku:={seq(Targem(mu1[1],mu1[2][j]),j=1..nops(mu1[2]))}:

if nops({seq(ku[i1][1],i1=1..nops(ku))})<>1 then
  RETURN(FAIL):
else

gu:=[op(gu), [coe,ku[1][1],{seq(ku[i1][2],i1=1..nops(ku))}  ]]:

fi:
od:
gu:

end:

#NewKids(T): Like KidsP(T) (q.v.) but the output is in complementary notation. Try:
#NewKids([4,{[1,2,3],[1,2,4],[1,3,4],[2,3,4]}]);
NewKids:=proc(T) local mu,mu1,gu,i,coe,j,ku:
mu:=KidsP(T):

gu:=[]:

for i from 1 to nops(mu) do
mu1:=mu[i]:
coe:=mu1[1]:
mu1:=mu1[2]:
ku:={seq(Targem(mu1[1],mu1[2][j]),j=1..nops(mu1[2]))}:

gu:=[op(gu), [coe,Kabets(ku) ]]:


od:

gu:

end:


#SpellOut1kS(k,S): all the ordered vectors of  length k missing the set S. Try:
#SpellOut1kS(5,{1,2});
SpellOut1kS:=proc(k,S) local gu,i,s:

gu:={seq(i,i=1..k+1)}:

{seq(sort(convert(gu minus {s},list)), s in S)}:

end:



#UIpats(k,j): the set of ultimately increasing patterns of length k where the last k-j entries are increasing.
#Try:
#UIpats(5,2);
UIpats:=proc(k,j) local mu,gu,i,gu1:

mu:={seq(i,i=1..k)}:

gu:=permute(k,j):

{seq([op(gu1), op(sort(convert(mu minus convert(gu1,set),list)))],gu1 in gu)}:


end:




#PolyExp(T,k,r,k0,k1): inputs a procedure T that outputs a sequence of patterns of length k, finds a polynomial expression for
#the number of permutations containing at least one occurence of that pattern of length k+r, as a polynomial in k
#starting at k0, and trying out until k=k1, otherwise it returns FAIL. Try:
#T1:=proc(k) local i: [seq(i,i=1..k)]:end:
#PolyExp(T1,k,1,1,6);
PolyExp:=proc(T,k,r,k0,k1) local lu,i,mu:

lu:=[seq(NuBG(T(i),r),i=k0..k1)]:
mu:=GuessPol(lu,k,1):

if mu=FAIL then
   RETURN(FAIL):
else
RETURN(expand(subs(k=k-k0+1,mu))):
fi:

end: