######################################################################
##ICPW.txt: Save this file as  ICPW.txt                              #
## To use it, stay in the                                            #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read ICPW.txt<Enter>                               #
##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-May, 2018
#This version: May 11, 2018

print(`Created:  March-May  2018`):
print(`this version: May 11, 2018`):
print(` This is ICPW.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 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: A1, A2, BoCo, 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])=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 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])=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])=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])=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])=Vecs then
print(`Vecs(n,r): all the 0-1 vectors of length n with r 1's. Try:`):
print(`Vecs(5,2);`):



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



ez:=proc(): print(` A1(r,n), A2(r,a,b)  `): end:

#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,`+`)<r then
 RETURN({}):
fi:

if r<0 then
 RETURN({}):
fi:

gu:={}:

 for i from 0 to min(r,L[n]) do
  mu:=BoCo([op(1..n-1,L)],r-i):
  gu:=gu union {seq([op(mu1),i],mu1 in mu)}:
 od:
gu:
end:


#NewLv(L,v): inputs a list L and another list v (of the same length) outputs what happens to the list
#1^L[1] ...s^L[s] where one deletes v[1] from the 1 part, v[2] from the 2-part (demoting them to 1) etc.
#Try:
#NewLv([3,3,2],[1,1,1]);
NewLv:=proc(L,v) local i:

if not type(L,list) and type(v,list) and nops(L)=nops(v) then
 RETURN(FAIL):
fi:

[seq(L[i]-v[i]+v[i+1],i=1..nops(L)-1),L[nops(L)]-v[nops(v)]]:
end:

#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 s.
#in particular B(r,[n]) is the number of permutations of length n avoiding the pattern 1...r
#B(r,[0,n]) is  the number of words in 1^2 ...n^2 of length 2n avoiding the pattern 1...r, etc. Try
#B(3,[0,5]);
B:=proc(r,L) local gu,mu,mu1,j,tot,s,v,i:
option remember:
s:=nops(L):
tot:=add(L[i]*i,i=1..s):

if L=[0$s] then
  RETURN(1):
fi:

if min(op(L))<0 then
  RETURN(0):
fi:

gu:=0:

for j from 0 to trunc((tot-1)/r) do
   mu:=BoCo(L, r*j+1):
    for mu1 in mu do
     v:=NewLv(L,mu1):
     gu:=gu+ mul(binomial(L[i],mu1[i]),i=1..s)*B(r,v):
   od:
od:

for j from 1 to trunc((tot)/r) do
   mu:=BoCo(L, r*j):
    for mu1 in mu do
     v:=NewLv(L,mu1):
     gu:=gu- mul(binomial(L[i],mu1[i]),i=1..s)*B(r,v):
   od:
od:


gu:

end:


#Mamar(R,ListS): inputs a positive integer R larger than 2, and a list of positive integers ListS of size, S, say
#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
#number of words (of length n*s) with s copies of each of 1..n, that avoid the CONSECUTIVE pattern 1...r. Try
#Mamar(5,[40,30,20,10]);
Mamar:=proc(R,ListS) local S,r,s,i,n,t0,t1:
S:=nops(ListS):

t0:=time():
print(``):
print(`The Sequences Enumerating words  with s occurrences of each of 1, ...n, avoiding the Consecutive Increasing  Pattern of length r`):
print(`For s from 1 to `, S, `and for r from 3 to`, R):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):

for s from 1 to S do
print(``):
print(`-----------------------------`):
print(``):
print(`Chapter Number`, s, `: The first`, ListS[s], `terms of the sequences enumerating words with`, s, `occurrences of each of 1...n avoiding increasing`):
print(`consecutive patterns of length 3 to`, R):
print(``):
 for r from 3 to R do
print(`The first`, ListS[s], `terms of the sequences enumerating words with`, s, `occurrences of each of 1...n `):
print(`avoiding the consecutive pattern`, cat(seq(i,i=1..r)), `are `):
print(``):
print([seq(B(r,[0$(s-1),n]),n=1..ListS[s])]):
print(``):
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: