A343795 Number of Dumont permutations of the fourth kind of length 2n avoiding the pattern 312.

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

Author

Alexander Burstein and Opel Jones, Apr 29 2021

Keywords

• easy
• nonn

Comments

Dumont permutations of the fourth kind are permutations of even length where all deficiencies (drops) are even values at even positions.

Examples

			For n=2, a(2)=3 counts the permutations 1234, 1342, 1432.
		

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.

Crossrefs

Cf. A000108 (permutations avoiding 312), A024492, A048990, A110501 (length 2n Dumont permutations of 4th kind).

Programs

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

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.

Extensions

Terms a(12) and beyond from Andrew Howroyd, Apr 29 2021