######################################################################
## ResPermsG.txt: Save this file as  ResPermsG.txt to use it,        #
# stay in the                                                        #
## same directory, get into Maple (by typing: maple <Enter> )        #
#then type: read `ResPermsG.txt`: <Enter>                            #
## Then follow the instructions given there                          #
##                                                                   #
## Written by George Spahn and Doron Zeilberger, Rutgers University ,#
##  DoronZeil@gmail.com      .                                       # 
######################################################################

#read Pdata:

with(combinat):

Digits:=100:

print(`First Written: Nov.-Dec. 2022: tested for Maple 20  `):
print():
print(`This is ResPermsG.txt, A Maple package`):
print(`accompanying George Spahn and Doron Zeilberger's  article: `):
print(` "Counting Permutations  Where Neigbors Can't Stay Neighbors With A few Specificed Exceptions" `):

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

print(`-------------------------------`):
print():
print(`The most current version is available on WWW at:`):
print(` http://www.math.rutgers.edu/~zeilberg/tokhniot/ResPermsG.txt .`):
print(`Please report all bugs to: zeilberg at math dot rutgers dot edu .`):
print():
print(`-------------------------------`):
print(`For general help, and a list of the MAIN functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name);" `):

print(`-------------------------------`):
print(`For a list of the supporting functions type: ezra1();`):
print(`For help with a specific procedure, type "ezra(procedure_name);"`):
print():
 print(`-------------------------------`):


ezra1:=proc()
if args=NULL then

print(` The supporting procedures are: DerSn, Expand11, Expand1, ExpandP1, ExpandP11, IsGoodAB, Lef, Shrink11, Shrink1, SnAB `):
print(` `):

else
 ezra(args):
fi:
end:

ezra:=proc()

if args=NULL then

print(` ResPermsG.txt: A Maple package for  counting permutations  where pi[i+1]-pi[i]<>1 with a few exceptions `):
print(`The main procedures are: `):


elif nargs=1 and args[1]=DerSn then
print(`DerSn(n,a,B): The set of permutations of length n-1, after in the set SnAB(n,{a},B) minus SnAB(n,{},B), the pair of neighbors (a,a+1) are combined and shrunk. Try:`):
print(`DerSn(6,1,{3});`):


elif nargs=1 and args[1]=Expand1 then
print(`Expand1(S,a) Inputs a set of permutation of length n say, and outputs the set of permutation of length n+1 with a replaced by [a,a+1] and a+1...n promoted. Try:`):
print(`Expand1({[3,1,2,4]},2;`):

elif nargs=1 and args[1]=Expand11 then
print(`Expand11(pi,a) Inputs a permutation of length n say, and outputs the permutation of length n+1 with a replaced by [a,a+1] and a+1...n promoted. Try:`):
print(`Expand11([3,1,2,4],2);`):



elif nargs=1 and args[1]=ExpandP1 then
print(`ExpandP1(pi): inputs a set of permutation pi and replaces for each permutation, the i-th entry, pi[i] by pi[i],pi[i]+1, making room for the rest. Try:`):
print(`ExpandP1({[2,1,3]},2);`):

elif nargs=1 and args[1]=ExpandP11 then
print(`ExpandP11(pi,i): inputs a permutation pi and replaces the i-th entry, pi[i] by pi[i],pi[i]+1, making room for the rest. Try:`):
print(`ExpandP11([2,1,3],2);`):

elif nargs=1 and args[1]=IsGoodAB then
print(`IsGoodAB(pi,A,B): Is the permutation pi such that pi[i+1]-pi[i]<>1 except possibly when p[i] is in A and/or  i is in B. Try:`):
print(`IsGood([3,1,2,4],{1},{2});`):


elif nargs=1 and args[1]=Lef then
print(`Lef(n,a,b): SnAB(n,{a},{b}) minus SnAB(n,{},{}) minus Expand1(SnAB(n-1,{},{}),a) minus ExpandP1(SnAB(n-1,{},{}),b) It also outputs`):
print(` nops(Expand1(SnAB(n-1,{},{}),a)  intersect  ExpandP1(SnAB(n-1,{},{}),b)). Try:`):
print(`Lef(6,3,3);`):

elif nargs=1 and args[1]=Shrink11 then
print(`Shrink11(pi,a): shrinks the pair [a,a+1] in the permutation pi (if it exists) and returns the permutation of length nops(pi)-1 where a is identitified with a+1 and the rest shrunk. Try:`):
print(`Shrink11[1,4,2,3],2);`):


elif nargs=1 and args[1]=Shrink1  then
print(`Shrink1(S,a): shrinks the pair [a,a+1] in the set of permutations pi and returns the set of permutations of length nops(pi)-1 where a is identitified with a+1 and the rest shrunk. Try:`):
print(`Shrink1({[1,4,2,3]},2);`):

elif nargs=1 and args[1]= SnAB then
print(`SnAB(n,A,B): The set of permutations of n such that pi[i+1]-pi[i]<>1 except possibly when i is in A and p[i] is in B. Using Brute Force`):
print(` Try:`):
print(`SnAB(5,{1},{3});`):

else
 print(`There is no such thing as`, args):

fi:



end:

with(combinat):



#IsGoodAB(pi,A,B): Is the permutation pi such that pi[i+1]-pi[i]<>1 except possibly when p[i] is in A and/or  i is in B. Try:
#IsGood([3,1,2,4],{1},{2});
IsGoodAB:=proc(pi,A,B) local i,n:
n:=nops(pi):

for i from 1 to n-1 do
 if pi[i+1]-pi[i]=1 and (not member(i,B) and not member(pi[i],A)) then
   RETURN(false):
 fi:
od:
true:
end:

#SnAB(n,A,B): The set of permutations of n such that pi[i+1]-pi[i]<>1 except possibly when i is in A and p[i] is in B. Using Brute Force
SnAB:=proc(n,A,B) local mu,mu1,gu :
mu:=permute(n):
gu:={}:

for mu1 in mu do
 if IsGoodAB(mu1,A,B) then
   gu:=gu union {mu1}:
 fi:
od:
gu:

end:




#Shrink11(pi,a): shrinks the pair [a,a+1] in ther permutation pi (if it exists) and returns the permutation of length nops(pi)-1 where a is identitified with a+1 and the rest shrunk. Try:
#Shrink11([1,4,2,3],2);
Shrink11:=proc(pi,a) local n,i,j:
n:=nops(pi):
for i from 1 to n-1 while pi[i]<>a do od:
if i>n-1 or pi[i+1]<>a+1 then
 FAIL:
else
subs({seq(j=j-1,j=a+2..n)},[op(1..i,pi),op(i+2..n,pi)]):
fi:
end:

#DerSn(n,a,B): The set of permutations of length n-1, after SnAB(n,{a},B) minus SnAB(n,{},B) (a,a+1) are combined and shrunk. Try:
#DerSn(6,1,{3});
DerSn:=proc(n,a,B) local gu,gu1:
gu:= SnAB(n,{a},B) minus SnAB(n,{},B):
{seq(Shrink1(gu1,a),gu1 in gu)}:
end:


#Expand11(pi,a) Inputs a permutation of length n say, and outputs the permutation of length n+1 with a replaced by [a,a+1] and a+1...n promoted. Try
#Expand11([3,1,2,4],2);
Expand11:=proc(pi,a) local i,j,n,pi1:
n:=nops(pi):

if not a>=1 and a<=n then
 RETURN(FAIL):
fi:

pi1:=subs({seq(j=j+1,j=a+1..n)},pi):

for i from 1 to n while pi1[i]<>a do od:

[op(1..i-1,pi1),a,a+1, op(i+1..n,pi1)]:

end:

Expand1:=proc(S,a) local pi:
{seq(Expand11(pi,a), pi in S)}:
end:



Shrink1:=proc(S,a) local pi:
{seq(Shrink11(pi,a), pi in S)}:
end:



#ExpandP11(pi,i): inputs a permutation pi and replaces the i-th entry, pi[i] by pi[i],pi[i]+1, making room for the rest. Try:
#ExpandP11([2,1,3],2);
ExpandP11:=proc(pi,i) local n,pi1,j,a:
n:=nops(pi):
a:=pi[i]:
pi1:=subs({seq(j=j+1,j=a+1..n)},pi):
[op(1..i,pi1),a+1,op(i+1..n,pi1)]:
end:



ExpandP1:=proc(S,i) local pi:
{seq(ExpandP11(pi,i), pi in S)}:
end:



#Lef(n,a,b): SnAB(n,{a},{b}) minus SnAB(n,{},{}) minus Expand1(SnAB(n-1,{},{}),a) minus ExpandP1(SnAB(n-1,{},{}),b) It also outputs
# nops(Expand1(SnAB(n-1,{},{}),a)  intersect  ExpandP1(SnAB(n-1,{},{}),b)). Try:
#Lef(6,3,3);
Lef:=proc(n,a,b) local gu00,gu01,gu10,gu11,ku:
gu00:=SnAB(n,{},{}):

gu10:=Expand1(SnAB(n-1,{},{}),a):

gu01:=ExpandP1(SnAB(n-1,{},{}),b):

gu11:=SnAB(n,{a},{b}):

ku:=gu11 minus gu00 minus gu01 minus gu10:

[ku,nops(gu01 intersect gu10)]:

end: