A281784 Number of permutations of size n avoiding the three vincular patterns 2-41-3, 3-14-2 and 3-41-2.

1, 2, 6, 21, 82, 346, 1547, 7236, 35090, 175268, 897273, 4690392, 24961300, 134917123, 739213795, 4099067786, 22973964976, 129998127216, 741951610676, 4267733183951, 24722711348105, 144147076572858, 845460619537567, 4986014094568416, 29553202933497989, 175988793822561947, 1052569034807964425, 6320797287983675428, 38100643422386086309, 230476496238489596293, 1398812189780917895946, 8516159717810715750712, 51999675864641162206960, 318388601290603235387353, 1954555567303560704554767, 12028490623505389875097231, 74197729371621673254309374, 458706129189543207063584184, 2841808950641424998337843123

Offset: 1

Author

Mathilde Bouvel, Mar 01 2017

Keywords

• easy
• nonn
• walk

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)}.

Examples

			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).
		

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.

Crossrefs

Baxter and twisted Baxter permutations are both enumerated by the Baxter numbers A001181.

Programs

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

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.).