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

1, 1, 0, 0, 2, 10, 68, 500, 4170, 38730, 397172, 4459116, 54421082, 717571442, 10167743668, 154104395348, 2487968793386, 42630767594522, 772730550801940, 14773475294401180, 297121458577213850, 6270996358146824738, 138591948457411817684, 3200867594024256790020, 77112844928711640695594

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. a(n) is the number of king permutations of length n that avoid the mesh pattern 12 with squares (0,2), (1,0), (1,1), (2,0), 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.8 at page 23.

Formula

G.f.: 1 + t + 1/(1 + t) - 1/A(t) 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) = 10 solutions are these 10 permutations: 24153, 25314, 31524, 35142, 35241, 41352, 42513, 42531, 52413, 53142.

Crossrefs

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

Sequence in context: A208561 A152620 A152621 * A382651 A382645 A147725

Adjacent sequences: A383431 A383432 A383433 * A383435 A383436 A383437

Keyword

nonn,easy

Author

Dan Li, Apr 27 2025

Status

approved