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

%I #38 May 28 2021 00:53:26

%S 1,2,6,21,82,346,1547,7236,35090,175268,897273,4690392,24961300,

%T 134917123,739213795,4099067786,22973964976,129998127216,741951610676,

%U 4267733183951,24722711348105,144147076572858,845460619537567,4986014094568416,29553202933497989,175988793822561947,1052569034807964425,6320797287983675428,38100643422386086309,230476496238489596293,1398812189780917895946,8516159717810715750712,51999675864641162206960,318388601290603235387353,1954555567303560704554767,12028490623505389875097231,74197729371621673254309374,458706129189543207063584184,2841808950641424998337843123

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

%C a(n) is the number of permutations of size n that are both Baxter and twisted Baxter.

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

%H Vaclav Kotesovec, <a href="/A281784/b281784.txt">Table of n, a(n) for n = 1..1000</a>

%H A. Bostan, K. Raschel, B. Salvy, <a href="https://hal.archives-ouvertes.fr/hal-00697386/file/BoRaSa12.pdf">Non D-finite excursions in the quarter plane</a>, J. Comb. Theory A, 121:45-63, 2014.

%H Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer and Simone Rinaldi, <a href="https://arxiv.org/abs/1702.04529">Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence.</a> Arxiv preprint, 2017.

%H Arturo Merino and Torsten Mütze, <a href="https://arxiv.org/abs/2103.09333">Combinatorial generation via permutation languages. III. Rectangulations</a>, arXiv:2103.09333 [math.CO], 2021.

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

%F Consequently, neither A(x;1,1) nor A(x;y,z) are D-finite (see preprint of Bouvel et al.).

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

%p S:=x*y*z:

%p s[1]:=1:

%p for en from 2 to 200 do

%p 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;

%p S:=normal(%):

%p s[en]:=subs(x=1,z=1,y=1,S);

%p od:

%p # Veronica Guerrini, Mar 01 2017

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

%K easy,nonn,walk

%O 1,2

%A _Mathilde Bouvel_, Mar 01 2017