######################################################################
##PERCY: Save this file as PERCY. To use it, stay in the             #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read PERCY : <Enter>                               #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Temple University ,                   #
#zeilberg@math.temple.edu.                                           # 
#######################################################################
read ROTA: 
#Created: Aug. 23, 2000
#This version: Aug. 29, 2000
#PERCY: A Maple package to study the Markovian Permutation Statistics
#It accopmanies a paper by Foata and Zeilberger
#entitled " Babson and Steingrimsson's 
#Permutation Statistics Are Indeed Mahonian
#(and Sometimes Even Euler-Mahonian)
#Please report bugs to zeilberg@math.temple.edu
#IMPORTANT: YOU MUST HAVE The maple package ROTA
#in the same directory!
#
#The paper, and the this Maple package, and the Maple
#package ROTA are available from Zeilberger's homepage
#http://www.math.temple.edu/~zeilberg/
 
print(`Created:  Aug. 23, 2000`):
print(`This version:  Aug. 30, 2000`):
print(`This is PERCY: A Maple package to study the Markovian`):
print(` Permutation Statistics It accopmanies a paper by Foata and `):
print(`Zeilberger entitled " Babson and Steingrimsson's `):
print(`Statistics Are Indeed Mahonian`):
print(` (and Sometimes Even Euler-Mahonian) Please report bugs to `):
print(` zeilberg@math.temple.edu `):
print(`IMPORTANT: YOU MUST HAVE The maple package ROTA in the`):
print(` same directory!`):
 
print(`The paper, and the this Maple package, and the Maple`):
print(`package ROTA are available from Zeilberger's homepage`):
print(`http://www.math.temple.edu/~zeilberg/`):
 
lprint(``):
print(`Written by Doron Zeilberger, zeilberg@math.temple.edu`):
lprint(``):
print(`Please report bugs to zeilberg@math.temple.edu`):
lprint(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://www.math.temple.edu/~zeilberg/`):
 print(`For a list of the procedures type Ezra(), for help with`):
 print(`a specific procedure, type Ezra(procedure_name)`):
print(`For help with the package ROTA, that is called by PERCY`):
print(` type: ezra(); `):
 print(``):
Ezra:=proc()
if args=NULL then
 print(`Contains the following procedures: BS, BSE,`):
 print(` DATA, GF, GFdirect, GFdirectMS, GFMS, GFMSz, `):
 print(` GFz,  PermPreUmbra,PermPreUmbraMS `):
 print(` PermUmbra, PermUmbraMS, ValStat `):
fi:
 
if nops([args])=1 and op(1,[args])=BS then
print(`BS(ee,j,i,n): Translates a_bc, a_cb, b_ac, b_ca, c_ab, c_ba`):
print(`to Markovian Permutation-Statistics Notation [f,g,j,i,n]`):
fi:
 
if nops([args])=1 and op(1,[args])=BSE then
print(`BSE(bitui,j,i,n): Translates a linear expression in`):
print(`a_bc, a_cb, b_ac, b_ca, c_ab, c_ba,ab,ba`):
print(`to Markovian Permutation-Statistics Notation [f,g,j,i,n]`):
print(`For example: BSE(ba,j,i,n); should give [1,0,j,i,n]`):
fi:
 
if nops([args])=1 and op(1,[args])=DATA then
print(`The following statistics from the Babson-SteinGrimsson article`):
print(` are built-in  in this package `):
print(`S5:=b_ca+c_ab+a_bc+ab:`):
print(`S8:=a_cb+b_ca+c_ba+ba: (MAJ)`):
print(`S10:=b_ca+b_ac+a_bc+ab: STAT'`):
print(`S11:=a_cb+2*b_ca+ba:`):
print(`S12:=a_cb+c_ab+c_ba+ba:`):
print(`S13:=a_cb+2*b_ac+ab:`):
print(`S14:=a_cb+b_ac+a_bc+ab:(INV) `):
print(` des=ba `):
fi:
 
if nops([args])=1 and op(1,[args])=GF then
print(`GF(MPS,q,L):`):
print(` Given a Markovian Permutation Statistic`):
print(`MPS=[f,g,j,i,n], where f and g are `):
print(`affine-linear functions`):
print(` in the discrete variables j,i,n and a variable q`):
print(` and integer L, finds the first L terms in the sequence of `):
print(`wt.-enumerators of S_n according to the weight q^stat(pi)`):
print(`(using the Umbra)`):
print(`For example, to get the first 10 terms of the sequence of`):
print(`of generating functions according to maj, type`):
print(` GF([0,n-1,j,i,n],q,10); `):
fi:
 
 
if nops([args])=1 and op(1,[args])=GFdirect then
print(`GFdirect(MPS,q,L):`):
print(` Given a Markovian Permutation Statistic`):
print(`MPS=[f,g,j,i,n], where f and g are `):
print(`affine-linear functions`):
print(` in the discrete variables j,i,n and a variable q`):
print(` and integer L, finds the first L terms in the sequence of `):
print(`wt.-enumerators of S_n according to the weight q^stat(pi)`):
print(`(using (Extremely Slow!) Direct Enumeration`):
print(` Should only be used for checking puroposes!`):
print(`For example, to get the first 5 terms of the sequence of`):
print(`of generating functions according to maj, computed directly, type`):
print(` GFdirect([0,n-1,j,i,n],q,5); `):
fi:
 
 
if nops([args])=1 and op(1,[args])=GFdirectMS then
print(`GFdirectMS(MPSs,qs,L): Given a list of Markovian Permutation`):
print(`Statistics MPSs=[[f1,g1,j,i,n],[f2,g2,j,i,n], ...] where`):
print(`f1,f2, .. and g1,g2, ... are affine-linear `):
print(`in the discrete variables j,i,n and variables`):
print(`qs=[q1,q2,...] `):
print(`finds the sequence of weight-enumerators of S_n`):
print(` according to the weight `):
print(`wt. q1^(stat1(pi))*q2^(stat2(pi))*.. `):
print(`By direct enumeration!, Only to be used for checking purporses`):
print(`For example, to get the first 5 terms of the sequence of`):
print(`of generating functions according to maj and des, type`):
print(` GFdirectMS([[0,n-1,j,i,n],[0,1,j,i,n]],[q,t],5); `):
fi:
 
if nops([args])=1 and op(1,[args])=GFMS then
print(`GFMS(MPSs,qs,L): Given a list of Markovian Permutation`):
print(`Statistics MPSs=[[f1,g1,j,i,n],[f2,g2,j,i,n], ...] where`):
print(`f1,f2, .. and g1,g2, ... are affine-linear `):
print(`in the discrete variables j,i,n and variables`):
print(`qs=[q1,q2,...]  `):
print(` finds the sequence of weight-enumerators of S_n`):
print(` according to the weight `):
print(`wt. q1^(stat1(pi))*q2^(stat2(pi))*.. `):
print(`For example, to get the first 12  terms of the sequence of`):
print(`of generating functions according to maj and des, type`):
print(` GFMS([[0,n-1,j,i,n],[0,1,j,i,n]],[q,t],12); `):
fi:
 
if nops([args])=1 and op(1,[args])=GFMSz then
print(`GFMSz(MPSs,z,qs,L): Given a list of Markovian Permutation`):
print(`Statistics MPSs=[[f1,g1,j,i,n],[f2,g2,j,i,n], ...] where`):
print(`f1,f2, .. and g1,g2, ... are affine-linear `):
print(`in the discrete variables j,i,n and variables`):
print(`qs=[q1,q2,...] and variable `):
print(`z, finds the first L terms in the sequence of`):
print(`weight-enumerators of S_n, n=1,2, ..., L`):
print(`according to q1^stat1(pi)*q2^stat2(pi)*...*z^(last_letter)`):
print(`For example, to get the first 12  terms of the sequence of`):
print(`of generating functions according to maj and des, `):
print(` and the last-letter type`):
print(` GFMSz([[0,n-1,j,i,n],[0,1,j,i,n]],z,[q,t],12); `):
fi:
 
if nops([args])=1 and op(1,[args])=GFz then
print(`GFz(MPS,z,q,L):`):
print(` Given a Markovian Permutation Statistic`):
print(`MPS=[f,g,j,i,n], where f and g are `):
print(`affine-linear functions`):
print(` in the discrete variables j,i,n and a variables q and z`):
print(` and integer L, finds the first L terms in the sequence of `):
print(`wt.-enumerators of S_n according to the weight `):
print(` q^stat(pi)*z^(last letter) (using the Umbra)`):
print(`For example, to get the first 12  terms of the sequence of`):
print(`of generating functions according to maj, `):
print(` and the last-letter type`):
print(` GFz([0,n-1,j,i,n],z,q,12); `):
fi:
 
if nops([args])=1 and op(1,[args])=PermPreUmbra then
print(`PermPreUmbra(MPS,q,z):`):
print(` Given a Markovian Permutation Statistic`):
print(`MPS=[f,g,j,i,n], where f and g are `):
print(`affine-linear functions`):
print(` in the discrete variables j,i,n `):
print(`finds the pre-umbra relating A_(n-1) (the wt.`):
print(`enumerator for permutations according to the `):
print(`wt. q^(stat(pi))*z^(last letter) to A_n`):
print(`For example, to get the pre-umbra pertaining to maj type:`):
print(`PermPreUmbra([0,n-1,j,i,n],q,z));`):
fi:
 
if nops([args])=1 and op(1,[args])=PermPreUmbraMS then
print(`PermPreUmbraMS(MPSs,qs,z): Given a list of Markovian Permutation`):
print(`Statistics MPSs=[[f1,g1,j,i,n],[f2,g2,j,i,n], ...] where`):
print(`f1,f2, .. and g1,g2, ... are affine-linear `):
print(`in the discrete variables j,i,n and variables`):
print(`qs=[q1,q2,...] and variable `):
print(`z, finds the pre-umbra relating A_(n-1) (the wt.`):
print(`enumerator for permutations according to the `):
print(`wt. q^(stat(pi))*z^(last letter) to A_n`):
print(`For example, to get the pre-umbra pertaining to maj and des type:`):
print(`PermPreUmbraMS([[0,n-1,j,i,n],[0,1,j,i,n]],[q,t],z));`)
fi:
 
if nops([args])=1 and op(1,[args])=PermUmbra then
print(`PermUmbra(MPS,q,z):`):
print(` Given a Markovian Permutation Statistic`):
print(`MPS=[f,g,j,i,n], where f and g are `):
print(`affine-linear functions`):
print(` in the discrete variables j,i,n `):
print(`finds the Umbra relating A_(n-1) (the wt.`):
print(`enumerator for permutations according to the `):
print(`wt. q^(stat(pi))*z^(last letter) to A_n`):
print(`For example, to get the umbra pertaining to maj type:`):
print(`PermUmbra([0,n-1,j,i,n],q,z));`):
fi:
 
if nops([args])=1 and op(1,[args])=PermUmbraMS then
print(`PermUmbraMS(MPSs,qs,z): Given a list of Markovian Permutation`):
print(`Statistics MPSs=[[f1,g1,j,i,n],[f2,g2,j,i,n], ...] where`):
print(`f1,f2, .. and g1,g2, ... are affine-linear `):
print(`in the discrete variables j,i,n and variables`):
print(`qs=[q1,q2,...] and variable `):
print(`z, finds the Umbra relating A_(n-1) (the wt.`):
print(`enumerator for permutations according to the `):
print(`wt. q^(stat(pi))*z^(last letter) to A_n`):
print(`For example, to get the umbra pertaining to maj and des type:`):
print(`PermUmbraMS([[0,n-1,j,i,n],[0,1,j,i,n]],[q,t],z));`)
fi:
 
 
if nops([args])=1 and op(1,[args])=ValStat then
print(`ValStat(MPS,per): Given `):
print(`a Markovian Permutation statistic, MPS=[f,g,j,i,n]l`):
print(`where f and g  are affine linear functions `):
print(`in the discrete variables j,i,n and a permutation`):
print(`per, finds the value of the statistics on per`):
print(`For example to find maj([1,4,3,2]) type:`):
print(`ValStat([0,n-1,j,i,n],[1,4,3,2])) ;`)
fi:
 
end:
 
S5:=b_ca+c_ab+a_bc+ab:
S8:=a_cb+b_ca+c_ba+ba:
S10:=b_ca+b_ac+a_bc+ab:
S11:=a_cb+2*b_ca+ba:
S12:=a_cb+c_ab+c_ba+ba:
S13:=a_cb+2*b_ac+ab:
S14:=a_cb+b_ac+a_bc+ab:
des:=ba:
rise:=ab:
gu5:=BSE(S5,j,i,n):
gu8:=BSE(S8,j,i,n):
gu10:=BSE(S10,j,i,n):
gu11:=BSE(S11,j,i,n):
gu12:=BSE(S12,j,i,n):
gu13:=BSE(S13,j,i,n):
gu14:=BSE(S14,j,i,n):
gudes:=BSE(ba,j,i,n):
gurise:=BSE(ab,j,i,n):
lu5:=PermUmbra(gu5,q,z):
lu8:=PermUmbra(gu8,q,z):
lu10:=PermUmbra(gu10,q,z):
lu11:=PermUmbra(gu11,q,z):
lu12:=PermUmbra(gu12,q,z):
lu13:=PermUmbra(gu13,q,z):
lu14:=PermUmbra(gu14,q,z):
ludes:=PermUmbra(des,t,z):
luinc:=PermUmbra(inc,t,z):
 
 
#BS(ee,j,i,n): Translates a_bc, a_cb, b_ac, b_ca, c_ab, c_ba
#to Markovian Permutation-Statistics Notation [f,g,j,i,n]
BS:=proc(ee,j,i,n)
local gu:
gu:={a_bc, a_cb, b_ac, b_ca, c_ab, c_ba,ba,ab}:
if ee=a_bc then
RETURN([j-1,0,j,i,n]):
elif ee=a_cb then
RETURN([0,i-1,j,i,n]):
elif ee=b_ac then
RETURN([i-j-1,0,j,i,n]):
elif ee=b_ca then
RETURN([0,j-i-1,j,i,n]):
elif ee=c_ab then
RETURN([n-i,0,j,i,n]):
elif ee=c_ba then
RETURN([0,n-j,j,i,n]):
elif ee=ba then
RETURN([0,1,j,i,n]):
elif ee=ab then
RETURN([1,0,j,i,n]):
 
else
ERROR(`The first argument must belong to`,gu):
fi:
end:
 
 
#BSE(bitui,j,i,n): Translates a linear expression in
#a_bc, a_cb, b_ac, b_ca, c_ab, c_ba,ab,ba
#to Markovian Permutation-Statistics Notation [f,g,j,i,n]
BSE:=proc(bitui,j,i,n)
local mu,lu,gu1,gu2,i1,c,ku:
 
mu:=bitui:
lu:={a_bc, a_cb, b_ac, b_ca, c_ab, c_ba,ba,ab}:
 
gu1:=0:
gu2:=0:
for i1 from 1 to nops(lu) do
c:=coeff(bitui,lu[i1],1):
mu:=expand(mu-c*lu[i1]):
ku:=BS(lu[i1],j,i,n):
gu1:=gu1+c*ku[1]:
gu2:=gu2+c*ku[2]:
od:
 
if mu<>0 then
ERROR(`The first argument must be a linear combination of`,lu):
fi:
[gu1,gu2,j,i,n]:
end:
 
#GF(MPS,q,L): Given a Markovian permutation statistic
#MPS=[f,j,j,i,n], where f and g are
#affine-linear functions
#in the discrete variables j,i,n and a variable
#variable q, finds the first L terms in the sequence of 
#wt.-enumerators of S_n according to the weight q^stat(pi)
#(using the Umbra)
GF:=proc(MPS,q,L)
local z,gu,mu,mu1,n1:
gu:=PermUmbra(MPS,q,z):
 
mu1:=z:
mu:=[1]:
 
for n1 from 2 to L do
mu1:=ApplyUmbra(subs(n=n1,gu),mu1,[z]):
mu:=[op(mu),expand(subs(z=1,mu1))]:
od:
mu:
end:
 
 
#GFMS(MPSs,qs,L): Given a list of Markovian Permutation
#Statistics MPSs=[[f1,g1,j,i,n],[f2,g2,j,i,n], ...] where
#f1,f2, .. and g1,g2, ... are affine-linear 
#in the discrete variables j,i,n and variables
#qs=[q1,q2,...] 
# finds the first L terms in the sequence of
#weight-enumerators of S_n, n=1,2, ..., L
#according to q1^stat1(pi)*q2^stat2(pi)*...
GFMS:=proc(MPSs,qs,L)
local z,gu,mu,mu1,n1:
gu:=PermUmbraMS(MPSs,qs,z):
 
mu1:=z:
mu:=[1]:
 
for n1 from 2 to L do
mu1:=ApplyUmbra(subs(n=n1,gu),mu1,[z]):
mu:=[op(mu),expand(subs(z=1,mu1))]:
od:
mu:
end:
 
 
 
#GFMSz(MPSs,z,qs,L): Given a list of Markovian Permutation
#Statistics MPSs=[[f1,g1,j,i,n],[f2,g2,j,i,n], ...] where
#f1,f2, .. and g1,g2, ... are affine-linear 
#in the discrete variables j,i,n and variables
#qs=[q1,q2,...] and variable 
#z, finds the first L terms in the sequence of
#weight-enumerators of S_n, n=1,2, ..., L
#according to q1^stat1(pi)*q2^stat2(pi)*...*z^(last_letter)
GFMSz:=proc(MPSs,z,qs,L)
local gu,mu,mu1,n1:
gu:=PermUmbraMS(MPSs,qs,z):
 
mu1:=z:
mu:=[z]:
 
for n1 from 2 to L do
mu1:=ApplyUmbra(subs(n=n1,gu),mu1,[z]):
mu:=[op(mu),mu1]:
od:
mu:
end:
 
 
#GFz(MPS,z,q,L): Given a Markovian permutation statistic
#MPS=[f,j,j,i,n], where f and g are
#affine-linear functions
#in the discrete variables j,i,n and variables
#variable q and z, finds the first L terms in the sequence of 
#wt.-enumerators of S_n according to the weight 
#q^stat(pi)*z^(last Letter) (using the Umbra)
GFz:=proc(MPS,z,q,L)
local gu,mu,mu1,n1:
gu:=PermUmbra(MPS,q,z):
 
mu1:=z:
mu:=[z]:
 
for n1 from 2 to L do
mu1:=ApplyUmbra(subs(n=n1,gu),mu1,[z]):
mu:=[op(mu),factor(mu1)]:
od:
mu:
end:
 
 
#GFdirect(MPS,q,L): Given a Markovian permutation statistic
#MPS=[f,j,j,i,n], where f and g are
#affine-linear functions
#in the discrete variables j,i,n and a variable
#variable q, finds the first L terms in the sequence of 
#wt.-enumerators of S_n according to the weight q^stat(pi)
#By direct (Super Exponentially Slow!) computation
#Only for Checking Purposes!
GFdirect:=proc(MPS,q,L)
local gu,i:
gu:=[]:
for i from 1 to L do
gu:=[op(gu),GFdirect1(MPS,q,i)]:
od:
gu:
end:
 
 
#GFdirectMS(MPSs,qs,L): Given a 
#list of Markovian permutation statistic
#MPSs=[[f1,g1,j,i,n],[f2,g2,j,i,n],...] where f1,f2 and g1,g2 are
#affine-linear functions
#in the discrete variables j,i,n and a list of variables
#qs=[q1,q2,...], finds the first L terms in the sequence of 
#wt.-enumerators of S_n according to the weight q1^stat1(pi)*q2^stat2(pi)
#By direct (Super Exponentially Slow!) computation
#Only for Checking Purposes!
GFdirectMS:=proc(MPSs,qs,L)
local gu,i:
gu:=[]:
for i from 1 to L do
gu:=[op(gu),GFdirect1MS(MPSs,qs,i)]:
od:
gu:
end:
 
#GFdirect1(MPS,q,n0): Given a Markovian permutation statistic
#MPS=[f,g,j,i,n], where f and g are
#affine-linear functions
#in the discrete variables j,i,n and a variable
#variable q, finds the weight-enumerator
#S_n0 according to the weight q^stat(pi)
#By direct (Super Exponentially Slow!) computation
#Only for Checking Purposes!
GFdirect1:=proc(MPS,q,n0)
local gu,i,mu:
with(combinat):
mu:=permute(n0):
 
gu:=0:
 
for i from 1 to nops(mu) do
gu:=gu+q^ValStat(MPS,mu[i]):
od:
gu:
end:
 
 
 
#GFdirect1MS(MPSs,qs,n0): Given a 
#list of Markovian permutation statistics
#MPSs=[[f1,g1,j,i,n],[f2,g2,j,i,n], ...] where f1,f2,...
# and g1,g2, .. are affine-linear functions
#in the discrete variables j,i,n and a list of variables
#variable qs=[q1,q2,...], finds the weight-enumerator
#S_n0 according to the weight q1^stat1(pi)*q2^stat2(pi)*...
#By direct (Super Exponentially Slow!) computation
#Only for Checking Purposes!
GFdirect1MS:=proc(MPSs,qs,n0)
local lu,gu,i,mu,j:
with(combinat):
mu:=permute(n0):
 
gu:=0:
 
for i from 1 to nops(mu) do
lu:=1:
for j from 1 to nops(MPSs) do
lu:=lu*qs[j]^ValStat(MPSs[j],mu[i]):
od:
gu:=gu+lu:
od:
 
gu:
end:
 
#PermPreUmbra(MPS,q,z): Given a Markovian Permutation
#Statistics MPS=[f,g,j,i,n], where
#f and g are affine-linear 
#in the discrete variables j,i,n and variables
#q and z, finds the pre-umbra relating A_(n-1) (the wt.
#enumerator for permutations according to the 
#wt. q^(stat(pi))*z^(last letter) to A_n
PermPreUmbra:=proc(MPS,q,z)
local F,G,g1,f,g,j,i,n:
f:=MPS[1]: g:=MPS[2]: j:=MPS[3]: i:=MPS[4]: n:=MPS[5]:
g1:=subs(j=j+1,g):
F:=sum(z^i*q^g1,i=1..j):
F:=normal(F):
G:=sum(z^i*q^f,i=j+1..n):
G:=normal(G):
normal(F+G):
end:
 
 
#PermPreUmbraMS(MPSs,qs,z): Given a list of Markovian Permutation
#Statistics MPSs=[[f1,g1,j,i,n],[f2,g2,j,i,n], ...] where
#f1,f2, .. and g1,g2, ... are affine-linear 
#in the discrete variables j,i,n and variables
#qs=[q1,q2,...] and variable 
#z, finds the pre-umbra relating A_(n-1) (the wt.
#enumerator for permutations according to the 
#wt. q^(stat(pi))*z^(last letter) to A_n
PermPreUmbraMS:=proc(MPSs,qs,z)
local F,G,j,i,n,lu,x1:
j:=MPSs[1][3]: i:=MPSs[1][4]: n:=MPSs[1][5]:
 
lu:=1:
for x1 from 1 to nops(MPSs) do
lu:=lu*qs[x1]^subs(j=j+1,MPSs[x1][2]):
od:
 
F:=sum(z^i*lu,i=1..j):
F:=normal(F):
 
lu:=1:
for x1 from 1 to nops(MPSs) do
lu:=lu*qs[x1]^MPSs[x1][1]:
od:
 
G:=sum(z^i*lu,i=j+1..n):
G:=normal(G):
normal(F+G):
end:
 
 
 
#PermUmbra(MPS,q,z): Given a Markovian Permutation Statistic,
#MPS=[f,g,j,i,n], where f and g are
#affine-linear functions
#in the discrete variables j,i,n and variables
#q and z, finds the Umbra relating A_(n-1) (the wt.
#enumerator for permutations according to the 
#wt. q^(stat(pi))*z^(last letter) to A_n
PermUmbra:=proc(MPS,q,z)
local gu,j:
j:=MPS[3]:
gu:=PermPreUmbra(MPS,q,z):
ToUmbra(gu,[q,z],[j]):
end:
 
 
#PermUmbraMS(MPSs,qs,z): Given a list of Markovian Permutation
#Statistics MPSs=[[f1,g1,j,i,n],[f2,g2,j,i,n], ...] where
#f1,f2, .. and g1,g2, ... are affine-linear 
#in the discrete variables j,i,n and variables
#qs=[q1,q2,...] and variable 
#z, finds the Umbra relating A_(n-1) (the wt.
#enumerator for permutations according to the 
#wt. q^(stat(pi))*z^(last letter) to A_n
PermUmbraMS:=proc(MPSs,qs,z)
local gu,j:
j:=MPSs[1][3]:
gu:=PermPreUmbraMS(MPSs,qs,z):
ToUmbra(gu,[op(qs),z],[j]):
end:
 
 
#ValStat(MPS,per): Given 
#a Markovian Permutation statistic, MPS=[f,g,j,i,n]l
#where f and g  are affine linear functions 
#in the discrete variables j,i,n and a permutation
#per, finds the value of the statistics on per
#
ValStat:=proc(MPS,per)
local f,g,j,i,n,j1,i1,n1,per1,xx,gu,per1a:
option remember:
 
if nops(per)=1 then
RETURN(0):
fi:
 
f:=MPS[1]:g:=MPS[2]:j:=MPS[3]:i:=MPS[4]:n:=MPS[5]:
n1:=nops(per):
i1:=per[n1]:
j1:=per[n1-1]:
per1:=[op(1..n1-1,per)]:
 
per1a:=[]:
for xx from 1 to n1-1 do
if per1[xx]<i1 then
per1a:=[op(per1a),per1[xx]]:
else
per1a:=[op(per1a),per1[xx]-1]:
fi:
od:
 
per1:=per1a:
 
gu:=ValStat(MPS,per1):
 
if j1<i1 then
RETURN(gu+subs({j=j1,i=i1,n=n1},f)):
else
RETURN(gu+subs({j=j1,i=i1,n=n1},g)):
fi:
 
end: