A383408 Number of king permutations on n elements avoiding the mesh pattern (12, {(0,0),(0,2),(1,0),(1,1),(1,2),(2,1)}).

1, 1, 0, 0, 2, 14, 88, 632, 5152, 46972, 474008, 5248616, 63294680, 825940168, 11597278752, 174367336624, 2795167052832, 47591679875632, 857754907053056, 16314976128578752, 326598651690933216, 6863945954213702816, 151108752072042907968, 3477537076217415673344, 83503583639127861347392

Offset

0,5

Comments

A permutation p(1)p(2)...p(n) is a king permutation if |p(i+1)-p(i)|>1 for each 0<i<n. The sequence counts the number a(n) of king permutations of length n that avoid the mesh pattern 12 with squares (0,0), (0,2), (1,0), (1,1), (1,2), and (2,1) shaded.

Links

Table of n, a(n) for n=0..24.

Dan Li and Philip B. Zhang, Distributions of mesh patterns of short lengths on king permutations, arXiv:2411.18131 [math.CO], 2024. See Theorem 4.6 at page 19.

Formula

G.f.: (1 + t)*(A(t) - t)/(1 + t*(A(t) - t - 1)) where A(t)=Sum_{n >= 0} n!*t^n*(1-t)^n/(1+t)^n is the g.f. for king permutations given by A002464.

Example

For n = 4 the a(4) = 2 solutions are the two permutations 2413 and 3142.
For n = 5 the a(5) = 14 solutions are these 14 permutations: 13524, 14253, 24135, 24153, 25314, 31425, 31524, 35142, 35241, 41352, 42513, 42531, 52413, 53142.

Crossrefs

Cf. A002464, A382644, A382645, A382651, A383040, A383107, A383312, A383406, A383407.

Sequence in context: A162478 A348615 A380552 * A383406 A383407 A383107

Adjacent sequences: A383405 A383406 A383407 * A383409 A383410 A383411

Keyword

nonn,easy

Author

Dan Li, Apr 26 2025

Status

approved