###################################################################### ##ICPWt.txt: Save this file as ICPWt.txt # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read ICPWt.txt # ##Then follow the instructions given there # ## # ##Written by Mingjia Yang and Doron Zeilberger, Rutgers University # #DoronZeil at gmail dot com, my239@math.rutgers.edu # ###################################################################### #Created: March 30, 2018 print(`Created: March 30, 2018`): print(` This is ICPWt.txt `): print(`It is one of the packages that accompany the article `): print(` Increasing Consecutive Patterns in Words`): print(`by Mingjia Yang and Doron Zeilberger`): print(`and also available from Yang's and Zeilberger's websites`): print(``): print(`Please report bugs to DoronZeil at gmail dot com `): print(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://sites.math.rutgers.edu/~zeilberg/ .`): 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 Checking procedures type ezraC();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`---------------------------------------`): print(`---------------------------------------`): print(`For a list of the Original MAIN procedures (with t=0) type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`---------------------------------------`): print(`---------------------------------------`): print(`For a list of the General procedures (with general t) type ezraG();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`---------------------------------------`): with(combinat): ezraC:=proc() if args=NULL then print(` The checking procedures are: AtBF, NuPat, Words `): print(``): else ezra(args): fi: end: ezraG:=proc() if args=NULL then print(` The general procedures (with t) are: AlphaSeq. At, Bt, MamarT, YZ `): print(``): else ezra(args): fi: end: ezra1:=proc() if args=NULL then print(` The supporting procedures are: A1, A2, BoCo, ConjMoms, GUP, GUR, KickZ, NewLv, Vecs `): print(``): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: A, B, Mamar `): print(` `): elif nops([args])=1 and op(1,[args])=A then print(`A(r,m): Inputs a list of non-neg. integers m, and a pos. integer r, and outputs the number of words in 1^m1...nops(m)^m[nops(m)] that`): print(`avoid the consecutive pattern 1..r. Try:`): print(``): print(` To get the first 10 terms of https://oeis.org/A177596 , type: `): print(`seq(A(3,[3$i]),i=1..10);` ): print(``): print(``): print(` To get the first 10 terms of https://oeis.org/A177599 , type: `): print(`seq(A(3,[4$i]),i=1..10);` ): print(``): print(``): print(` To get the first 10 terms of https://oeis.org/A177605 , type: `): print(`seq(A(5,[3$i]),i=1..10);` ): print(``): print(` To get the first 10 terms of https://oeis.org/A177615 type: `): print(`seq(A(6,[3$i]),i=1..10);` ): print(``): print(` To get the first 10 terms of https://oeis.org/A177635 type: `): print(`seq(A(7,[3$i]),i=1..10);` ): print(``): print(``): elif nops([args])=1 and op(1,[args])=A1 then print(`A1(r,n): the number of permutations of length n avoiding the consecutive pattern 1...r.`): print(`Same as B(r,[n]). `); print(` To get the first 100 terms of https://oeis.org/A049774 , type: `): print(`seq(A1(3,i),i=1..100);` ): print(``): print(` To get the first 100 terms of https://oeis.org/A117158 , type:`): print(`seq(A1(4,i),i=1..100);`): print(``): print(` To get the first 100 terms of https://oeis.org/A177523 , type: `): print(`seq(A1(5,i),i=1..100);`): print(``): print(` To get the first 100 terms of https://oeis.org/A177533 , type: `): print(`seq(A1(6,i),i=1..100);`): print(``): print(` To get the first 100 terms of https://oeis.org/A177553 , type: `): print(`seq(A1(7,i),i=1..100);`): print(``): print(` To get the first 100 terms of https://oeis.org/A230051 , type: `): print(`seq(A1(8,i),i=1..100);`): print(``): print(` To get the first 100 terms of https://oeis.org/A230231 , type:`): print(`seq(A1(9,i),i=1..100);`): print(``): print(` To get the first 100 terms of https://oeis.org/A230232 , type:`): print(`seq(A1(10,i),i=1..100);`): print(``): print(` To get the first 100 terms of https://oeis.org/A230233 , type:`): print(`seq(A1(11,i),i=1..100);`): print(``): print(` To get the first 100 terms of https://oeis.org/A254523, type:`): print(`seq(A1(12,i),i=1..100);`): print(``): print(` To get a Sequence NOT in the OEIS (at least not on March 30, 2017), type: `): print(`seq(A1(13,i),i=1..100);`): print(``): elif nops([args])=1 and op(1,[args])=A2 then print(`A2(r,a,b): the number of words permuting a 112233... bb(b+1)...(b+a) (b letters occuring twice and a letters occuring once) .`): print(` avoiding the consecutive pattern 1...r`): print(`Same as B(r,[a,b]). `); print(` To get the first 50 terms of https://oeis.org/A177555 type:`): print(`seq(A2(3,0,i),i=1..50);`): print(``): print(` To get the first 50 terms of https://oeis.org/A177558 type:`): print(`seq(A2(4,0,i),i=1..50);`): print(``): print(``): print(` To get the first 50 terms of https://oeis.org/A177564 type:`): print(`seq(A2(5,0,i),i=1..50);`): print(``): print(``): print(` To get the first 50 terms of https://oeis.org/A177574 type:`): print(`seq(A2(6,0,i),i=1..50);`): print(``): print(``): print(` To get the first 50 terms of https://oeis.org/A177594 type:`): print(`seq(A2(7,0,i),i=1..50);`): print(``): print(` To get a Sequence NOT in the OEIS (at least not on March 30, 2017), type: `): print(`seq(A2(7,0,i),i=1..50);`): print(``): elif nops([args])=1 and op(1,[args])=AlphaSeq then print(`From HISTABRUT`): print(` AlphaSeq(f,x,N): Given a probability generating function `): print(` f(x) (a polynomial, rational function and possibly beyond) `): print(` returns a list, of length N, whose `): print(` (i) First entry is the average `): print(` (ii): Second entry is the variance `): print(` for i=3...N, the i-th entry is the so-called alpha-coefficients `): print(` that is the i-th moment about the mean divided by the `): print(` variance to the power i/2 (For example, i=3 is the skewness `): print(` and i=4 is the Kurtosis) `): print(` If f(1) is not 1, than it first normalizes it by dividing `): print(` by f(1) (if it is not 0) . `): print(`For example, try: `): print(`AlphaSeq(((1+x)/2)^100,x,4);`): elif nops([args])=1 and op(1,[args])=At then print(`At(r,m,t): Inputs a list of non-neg. integers m, and a pos. integer r, and outputs the weight-enumerator of words in 1^m1...nops(m)^m[nops(m)] `): print(`according to the weight t^NumberOfPattern1..r.Try:`): print(`seq(At(3,[1$i],t),i=1..10);` ): print(``): elif nops([args])=1 and op(1,[args])=AtBF then print(`AtBF(r,m,t): Inputs a list of non-neg. integers m, and a pos. integer r, and outputs the weight-enumerator of words in 1^m1...nops(m)^m[nops(m)] `): print(`according to the weight t^(#OfOccurrences of the pattern 1...r), by brute force. FOR CHECKING PURPOSES ONLY. Try: `): print(`AtBF(3,[2,3,4],t);`): elif nops([args])=1 and op(1,[args])=B then print(`B(r,L): a quicker way to compute A(r,[1^L[1],2^L[2], ..., s^L[s]]), where s is the number of elements of L.`): print(`in particular B(r,[n]) is the number of permutations of length n avoiding the consecutive pattern 1...r`): print(` B(r,[0,n]) is the number of words in 1^2 ...n^2 of length 2n avoiding the pattern 1...r, etc. Try: `): print(` B(3,[0,5]); `): elif nops([args])=1 and op(1,[args])=Bt then print(`Bt(r,L,t): a quicker way to compute At(r,[1^L[1],2^L[2], ..., s^L[s]],t), where s is the number of elements of L.`): print(`in particular Bt(r,[n],t) is the weight-enumerator of permutations of length n according to the number of consecutive patterns 1...r`): print(` Bt(r,[0,n],t) is the weight-enumerator of words in 1^2 ...n^2 of length 2n according to the pattern 1...r, etc. Try: `): print(` Bt(3,[0,5],t); `): elif nops([args])=1 and op(1,[args])=BoCo then print(`BoCo(L,r): Given a list L of non-negative integers, the set of vectors v, of non-negative integers of the same length as L `): print(`that add-up to r, such that their sum is r. Try:`): print(`BoCo([2,2,2],3);`): elif nops([args])=1 and op(1,[args])=ConjMoms then print(`ConjMoms(L,t,K,n): given a list of prob. generating functions L, starting at n=1, a positive integer K and a variable n`): print(`outputs the average and the first K moments about the mean, if they are ultimate polynomials. It returns the pairs [pol,n0].`): print(`It tries to go all the way to the K-th moment`): print(`if it can't it returns what it has. Try:`): print(`L:=[seq(Bt(3,[i],t),i=1..40)]; ConjMoms(L,t,4,n);`): elif nops([args])=1 and op(1,[args])=GUP then print(`GUP(L,n): guesses an ultimate polynomial, R, of n, such that R(L[i][1])=L[i][2]. for i>=n0 for some n0.`): print(`It returns the pair [Polynomial, n0]. `): print(`Try: GUP([[1,6],[2,100],seq([i, i^3],i=3..10)],n);`): elif nops([args])=1 and op(1,[args])=GUR then print(`GUR(L,n): guesses an ultimate rational function, R, of n, such that R(L[i][1])=L[i][2]. for i>=n0 for some n0.`): print(`It returns the pair [RationalFunction, n0]. `): print(`Try: GUR([[1,6],[2,100],seq([i, (i+1)/(i+2)],i=3..10)],n);`): elif nops([args])=1 and op(1,[args])=KickZ then print(`KickZ(m): kicks all the 0's from m`): elif nops([args])=1 and op(1,[args])=Mamar then print(`Mamar(R,ListS): `): print(` inputs a positive integer R larger than 2, and a list of positive integers ListS of size, S, say`): print(`and outputs,for r from 3 to R, and for s from 1 to S the first ListS[s] terms , starting at n=1 of the sequence`): print(`number of words (of length n*s) with s copies of each of 1..n, that avoid the CONSECUTIVE pattern 1...r. Try: `): print(` Mamar(10,[40,40,30,20,10,10]);`): elif nops([args])=1 and op(1,[args])=MamarT then print(`MamarT(R,t,K,a,ListS,n): inputs a positive integer R larger than 2, and a list of positive integers ListS of size, S, say`): print(`a variable t, a positive integer K, and a positive integer a,`): print(`and outputs,for r from 3 to R, and for s from 1 to S the first ListS[s] terms , starting at n=1 of the sequence`): print(`word enumerator of words (of length n*s) with s copies of each of 1..n, according to the number of occurrences of the CONSECUTIVE pattern 1...r. `): print(`It also returns for each case, the enumerating sequences for such words with exactly j occurrences of the pattern for j from 0 to a`): print(` (in particular reproducing the output of Mamar(R,ListS)), and explicit expressions, in n, for the `): print(` first K moments of the r.v. "number of occurrences" confirming the`): print(` known fact that these are asymptotically normal. `): print(`Try: `): print(`MamarT(4,t, 4, 2, [40,30],n);`): elif nops([args])=1 and op(1,[args])=NewLv then print(`NewLv(L,v): inputs a list L and another list v (of the same length) outputs what happens to the list`): elif nops([args])=1 and op(1,[args])=NuPat then print(`NuPat(w,r): the number of occurrences of the pattern 1...r in the word w`): elif nops([args])=1 and op(1,[args])=Vecs then print(`Vecs(n,r): all the 0-1 vectors of length n with r 1's. Try:`): print(`Vecs(5,2);`): elif nops([args])=1 and op(1,[args])=Words then print(`Words(m): the set of words in {1, ,,,.nops(m)) with m[i]'s occurrences of i. Try:`): print(`Word([2,2,2]);`): elif nops([args])=1 and op(1,[args])=YZ then print(`YZ(r,n,t): the weight-enumerator of abstract clusters of length n with the consecutive pattern 1...r, where the weight of a cluster is (t-1)^NumberOfMembers. Try:`): print(` YZ(4,10,t);`): else print(`There is no ezra for`,args): fi: end: ###start guess poly #GP1(L,n,d): guesses a polynomial R of n, of degree d, such that R(L[i][1])=L[i][2]. #Try: GP1([seq([i,i^3+1],i=1..4)],n,1); GP1:=proc(L,n,d) local i,eq,var,a,b,R: if nops(L){0} then RETURN(FAIL): fi: R: end: #GP(L,n): guesses a polynomial R of n, such that R(L[i][1])=L[i][2]. #Try: GP([seq([i, i^3],i=1..5)],n); GP:=proc(L,n) local d,gu,i,L1: for i from 1 to nops(L) while L[i][1]=0 do od: L1:=[op(i+1..nops(L),L)]: for d from 0 to trunc((nops(L1)-2)/2) do gu:=GP1(L1,n,d): if gu<>FAIL then RETURN(gu): fi: od: gu: end: #GUP(L,n): guesses an ultimate polynomial R of n, such that R(L[i][1])=L[i][2]. for i>=n0 for some n0. #It returns the pair [Polynomial, n0]. #Try: GUP([1,6],[2,100],[seq([i, i^3],i=3..10)],n); GUP:=proc(L,n) local i,gu,j,n0: for i from 1 to trunc(2*nops(L)/3) do gu:=GP([op(i..nops(L),L)],n): if gu<>FAIL then n0:=L[i+1][1]: for j from 1 to nops(L) do if L[j][1]>=n0 and subs(n=L[j][1],gu)-L[j][2]<>0 then RETURN(FAIL): fi: od: RETURN([gu,L[i+1][1]]): fi: od: FAIL: end: #GR1(L,n,d): guesses a rational function R of n, of degree d, such that R(L[i][1])=L[i][2]. #Try: GR1([seq([i,(i+2)/(i+3)],i=1..4)],n,1); GR1:=proc(L,n,d) local i,eq,var,a,b,R: if nops(L)<2*d+2 then print(L, `should have at least`, 2*d+2, `members. `): RETURN(FAIL): fi: R:=add(a[i]*n^i,i=0..d)/(1+add(b[i]*n^i,i=1..d)): eq:={seq(subs(n=L[i][1],R)-L[i][2],i=1..2*d+2)}; var:={seq(a[i],i=0..d),seq(b[i],i=1..d)}: var:=solve(eq,var): if var=NULL then RETURN(FAIL): fi: R:=factor(subs(var,R)): if {seq(subs(n=L[i][1],R)-L[i][2],i=2*d+2..nops(L))}<>{0} then RETURN(FAIL): fi: R: end: #GR(L,n): guesses a rational function R of n, such that R(L[i][1])=L[i][2]. #Try: GR([seq([i,(i+2)/(i+3)],i=1..4)],n); GR:=proc(L,n) local d,gu: for d from 1 to trunc((nops(L)-2)/2) do gu:=GR1(L,n,d): if gu<>FAIL then RETURN(gu): fi: od: gu: end: #GUR(L,n): guesses a rational function R of n, such that R(L[i][1])=L[i][2] for i>=n0. It also returns n0. #Try: GUR([seq([i,(i+2)/(i+3)],i=1..4)],n); GUR:=proc(L,n) local gu,i,L1,j: for i from nops(L)-5 by -1 to 1 do L1:=[op(i..nops(L),L)]: gu:=GR(L1,n): if gu<>FAIL then for j from i-1 by -1 to 1 do if subs(n=L[j][1],gu)<>L[j][2] then RETURN([gu,j+1]): fi: od: RETURN([gu,1]): fi: od: FAIL: end: ###end guess ###########From HISTABRUT #AveAndMoms(f,x,N): Given a probability generating function #f(x) (a polynomial, rational function and possibly beyond) #returns a list whose first entry is the average #(alias expectation, alias mean) #followed by the variance, the third moment (about the mean) and #so on, until the N-th moment (about the mean). #If f(1) is not 1, than it first normalizes it by dividing #by f(1) (if it is not 0) . #For example, try: #AveAndMoms(((1+x)/2)^100,x,4); AveAndMoms:=proc(f,x,N) local mu,F,memu1,gu,i: mu:=simplify(subs(x=1,f)): if mu=0 then print(f, `is neither a prob. generating function nor can it be made so`): RETURN(FAIL): fi: F:=f/mu: memu1:=simplify(subs(x=1,diff(F,x))): gu:=[memu1]: F:=F/x^memu1: F:=x*diff(F,x): for i from 2 to N do F:=x*diff(F,x): gu:=[op(gu),simplify(subs(x=1,F))]: od: gu: end: #AlphaSeq(f,x,N): Given a probability generating function #f(x) (a polynomial, rational function and possibly beyond) #returns a list, of length N, whose #(i) First entry is the average #(ii): Second entry is the variance #for i=3...N, the i-th entry is the so-called alpha-coefficients #that is the i-th moment about the mean divided by the #variance to the power i/2 (For example, i=3 is the skewness #and i=4 is the Kurtosis) #If f(1) is not 1, than it first normalizes it by dividing #by f(1) (if it is not 0) . #For example, try: #AlphaSeq(((1+x)/2)^100,x,4); AlphaSeq:=proc(f,x,N) local gu,i: gu:=AveAndMoms(f,x,N): if gu=FAIL then RETURN(gu): fi: if gu[2]=0 then print(`The variance is 0`): RETURN(FAIL): fi: [gu[1],gu[2],seq(gu[i]/gu[2]^(i/2),i=3..N)]: end: #ConjMoms(L,t,K,n): given a list of prob. generating functions L, starting at n=1, a positive integer K and a variable n #outputs the average and the first K moments about the mean, if they are ultimate polynomials. It returns the pairs [pol,n0]. #It tries to go all the way to the K-th moment #if it can't it returns what it has. Try: #L:=[seq(B(3,[i],t),i=1..40)]; ConjMoms(L,t,4,n); ConjMoms:=proc(L,t,K,n) local mu,gu,j,mu1,i,lu1: mu:=[seq(AveAndMoms(L[i],t,K) ,i=1..nops(L))]: gu:=[]: for j from 1 to K do mu1:=[seq([i , mu[i][j]] , i=1..nops(mu))]: lu1:=GUP(mu1,n): if lu1=FAIL then RETURN(gu): else gu:=[op(gu),lu1]: fi: od: gu: end: ###########End HISTABRUT ####start original #Vecs(n,r): all the 0-1 vectors of length n with r 1's. Try: #Vecs(5,2); Vecs:=proc(n,r) local v,gu1,gu2: option remember: if n=0 then if r=0 then RETURN({[]}): else RETURN({}): fi: fi: gu1:=Vecs(n-1,r): gu2:=Vecs(n-1,r-1): {seq([op(v),0],v in gu1) , seq([op(v),1], v in gu2)}: end: #KickZ(m): kicks all the 0's from m KickZ:=proc(m) local i,m1: m1:=[]: for i from 1 to nops(m) do if m[i]<>0 then m1:=[op(m1),m[i]]: fi: od: m1: end: #A(r,m): Inputs a list of non-neg. integers m, and a pos. integer r, and outputs the number of words in 1^m1...nops(m)^m[nops(m)] that #avoid the consecutive pattern 1..r. Try: #A(3,[1$10]); A:=proc(r,m) local gu,j,mu,mu1: option remember: if m=[] then RETURN(1): fi: mu:=Vecs(nops(m),1): gu:=add(A(r,sort(KickZ(m-mu1))), mu1 in mu): for j from 1 to trunc(nops(m)/2)+1 do if r*j<=nops(m) then mu:=Vecs(nops(m),r*j): gu:=gu-add(A(r,sort(KickZ(m-mu1))), mu1 in mu): fi: if r*j+1<=nops(m) then mu:=Vecs(nops(m),r*j+1): gu:=gu+add(A(r,sort(KickZ(m-mu1))), mu1 in mu): fi: od: gu: end: #A1(r,n): the number of permutations of length n avoiding the consecutive pattern 1...r A1:=proc(r,n) local j: option remember: if n=0 then 1: elif n<0 then 0: else n*A1(r,n-1)-add(binomial(n,r*j)*A1(r,n-r*j),j=1..trunc(n/r))+add(binomial(n,r*j+1)*A1(r,n-r*j-1),j=1..trunc((n-1)/r)): fi: end: #A2(r,a,b): the number of words in 1^a 2^b avoiding the pattern 1...r A2:=proc(r,a,b) local j,a1,b1,gu: option remember: if a=0 and b=0 then 1: elif (a<0 or b<0) then 0: else gu:=a*A2(r,a-1,b)+b*A2(r,a+1,b-1): for j from 1 to trunc((a+b)/r) do for a1 from 0 to min(a,r*j+1) do b1:=r*j-a1: gu:=gu-binomial(a,a1)*binomial(b,b1)*A2(r,a-a1+b1,b-b1): b1:=r*j+1-a1: gu:=gu+binomial(a,a1)*binomial(b,b1)*A2(r,a-a1+b1,b-b1): od: od: RETURN(gu): fi: end: #BoCo(L,r): Given a list L of non-negative integers, the set of vectors v, of non-negative integers of the same length as L #that add-up to r, such that their sum is r. Try: #BaCo([2,2,2],3); BoCo:=proc(L,r) local n,gu,i,mu,mu1: option remember: n:=nops(L): if r=0 then RETURN({[0$n]}): fi: if L=[] then if r=0 then RETURN({[]}): else RETURN({}): fi: fi: if convert(L,`+`)=1 then co:=co+1: fi: od: co: end: #AtBF(r,m,t): Inputs a list of non-neg. integers m, and a pos. integer r, and outputs the weight-enumerator of words in 1^m1...nops(m)^m[nops(m)] #according to the weight t^(#OfOccurrences of the pattern 1...r), by brute force. FOR CHECKING PURPOSES ONLY. Try #AtBF(3,[2,3,4],t); AtBF:=proc(r,m,t) local gu,w: option remember: gu:=Words(m): add(t^NuPat(w,r),w in gu): end: ##end checking procedures #start New stuff (with t) #YZ(r,n,t): the weight-enumerator of abstract clusters of length n with the consecutive pattern 1...r, where the weight of a cluster is (t-1)^NumberOfMembers. Try: # YZ(4,10,t); YZ:=proc(r,n,t) local i: option remember: if nFAIL then print(`The average of the number of occurrences of the pattern`, cat(seq(i1,i1=1..r)), ` for n>=`, lu[1][2], `is `): print(``): print(lu[1][1]): print(``): print(`and in Maple format:`): print(``): lprint(lu[1][1]): print(``): fi: for j from 2 to K do lu[j]:=[seq([i,mu[i][j]],i=1..nops(mu))]: if s=1 then lu[j]:=GUP(lu[j],n): else lu[j]:=GUR(lu[j],n): fi: if lu[j]<>FAIL then if j=2 then print(` The variance for the r.v. number of occurrences of the pattern`, cat(seq(i1,i1=1..r)), `for n>=`,lu[j][2], `is `): print(lu[j][1]): else print(` The `, j , ` -th moment about the mean for number of occurrences of the pattern`, cat(seq(i1,i1=1..r)), `for n>=`,lu[j][2], `is `): print(``): print(lu[j][1]): print(``): print(`and in Maple format `): print(``): lprint(lu[j][1]): print(``): print(`The scaled`, j, `-th moment is`): print(lu[j][1]/sqrt(lu[2][1])^j): print(`whose limit, as n goes to infinity is`): print(limit(lu[j][1]/sqrt(lu[2][1])^j,n=infinity)): fi: fi: od: od: print(``): t1:=time(): print(`This ends Chapter`, s, `that took`, t1-t0, `seconds to produce.`): t0:=time(): print(``): od: print(`------------------------------------`): print(`This ends this article, that took`, time(), `to produce. `): end: