OFFSET
1,2
COMMENTS
a(n) is the number of permutations of size n that are both Baxter and twisted Baxter.
a(n) is also the number of excursions in the positive quarter-plane, using n steps, and with step (multi-)set {(-1,0),(0,-1),(1,-1),(1,0),(0,1),(0,0),(0,0)}.
LINKS
Vaclav Kotesovec, Table of n, a(n) for n = 1..1000
A. Bostan, K. Raschel, B. Salvy, Non D-finite excursions in the quarter plane, J. Comb. Theory A, 121:45-63, 2014.
Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer and Simone Rinaldi, Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence. Arxiv preprint, 2017.
Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
FORMULA
The generating function for a(n) is A(x;1,1) where A(x;y,z) satisfies A(x;y,z) = x*y*z + (x/(1-y))*(y*A(x;1,z) - A(x;y,z)) + x*z*A(x;y,z) + (x*y*z/(1-z))*(A(x;y,1) - A(x;y,z)).
Consequently, neither A(x;1,1) nor A(x;y,z) are D-finite (see preprint of Bouvel et al.).
EXAMPLE
For n=4, there are a(4)=21 permutations that avoid 2-41-3, 3-14-2 and 3-41-2 (all permutations of size 4 except 2413, 3142 and 3412).
MAPLE
S:=x*y*z:
s[1]:=1:
for en from 2 to 200 do
x*y/(1-y)*(subs(y=1, S))-x/(1-y)*S+x*z*S+x*y*z/(1-z)*(subs(z=1, S))-x*y*z/(1-z)*S;
S:=normal(%):
s[en]:=subs(x=1, z=1, y=1, S);
od:
# Veronica Guerrini, Mar 01 2017
CROSSREFS
KEYWORD
easy,nonn,walk
AUTHOR
Mathilde Bouvel, Mar 01 2017
STATUS
approved