login
A343795
Number of Dumont permutations of the fourth kind of length 2n avoiding the pattern 312.
1
1, 1, 3, 10, 39, 174, 872, 4805, 28474, 178099, 1160173, 7803860, 53924841, 381640934, 2761331130, 20400560942, 153738854242, 1180631743440, 9229687049249, 73372263658451, 592476077260123, 4854377724124700, 40315729803287046, 339065862485375334, 2885324166565733641
OFFSET
0,3
COMMENTS
Dumont permutations of the fourth kind are permutations of even length where all deficiencies (drops) are even values at even positions.
REFERENCES
O. Jones, Enumeration of Dumont permutations avoiding certain four-letter patterns, Ph.D. thesis, Howard University, 2019.
LINKS
A. Burstein and O. Jones, Enumeration of Dumont permutations avoiding certain four-letter patterns, arXiv:2002.12189 [math.CO], 2020.
A. Burstein, M. Josuat-Vergès, and W. Stromquist, New Dumont permutations, Pure Math. Appl. (Pu.M.A.) 21 (2010), no. 2, 177-206.
FORMULA
Let F_k(x) be the truncation of the g.f. of A048990 to a polynomial of degree k. Let G_k(x) be the truncation of the g.f. of A024492 to a polynomial of degree k. Let G_{-1}(x) = 0. For k>=0, define A_k(x) recursively as follows: A_k(x) = F_k(x)/((1-x*G_{k-1}(x))^2-x*F_k(x)/(1-x*G_k(x)-x*F_k(x)^2/(1-x*A_{k+1}(x)))). Then A_0(x) is the g.f. of this sequence.
EXAMPLE
For n=2, a(2)=3 counts the permutations 1234, 1342, 1432.
PROG
(PARI) seq(n)={my(h=sqrt(1-16*x + O(x*x^n)), F=sqrt((1-h)/(8*x)), G=(1-sqrt((1+h)/2))/(2*x), A=O(1)); forstep(k=n\3, 0, -1, my(f=Pol(F + O(x*x^k))); A = f/((1 - x*Pol(G + O(x^k)))^2 - x*f/(1 - x*Pol(G + O(x*x^k)) - x*f^2/(1 - x*A))) ); Vec(A + O(x*x^n))} \\ Andrew Howroyd, Apr 29 2021
CROSSREFS
Cf. A000108 (permutations avoiding 312), A024492, A048990, A110501 (length 2n Dumont permutations of 4th kind).
Sequence in context: A137590 A352174 A124532 * A305560 A074728 A087860
KEYWORD
easy,nonn
AUTHOR
EXTENSIONS
Terms a(12) and beyond from Andrew Howroyd, Apr 29 2021
STATUS
approved