A346189 a(n) is the number of permutations on [n] with no strong fixed points or small descents.

0, 0, 2, 6, 34, 214, 1550, 12730, 116874, 1187022, 13219550, 160233258, 2100360778, 29610224590, 446789311934, 7185155686666, 122690711149290, 2217055354281582, 42269657477711198, 847998698508705834, 17857221256001240458, 393839277313540073230, 9078806210245773668990, 218340709713567352161226

Offset

1,3

Comments

A small descent in a permutation p is a position i such that p(i)-p(i+1)=1.

A strong fixed point is a fixed point (or splitter) p(k)=k such that p(i) < k for i < k and p(j) > k for j > k.

References

E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways For Your Mathematical Plays, Vol. 1, CRC Press, 2001.

Links

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

M. Lind, E. Fiorini, A. Woldar, and W. H. T. Wong, On Properties of Pebble Assignment Graphs, Journal of Integer Sequences, 24(6), 2020.

Formula

For n > 3, a(n) = b(n) - b(n-1) - Sum{i=4..n}(a(i-1)*b(n-i)) where b(n) = A000255(n-1) and b(0) = 1.

Example

For n = 4, the a(4) = 6 permutations on [4] with no strong fixed points or small descents: {(2,3,4,1),(3,4,1,2),(4,1,2,3),(3,1,4,2),(2,4,1,3),(4,2,3,1)}.

Prog

(Python) See A346204.

Crossrefs

Cf. A000255, A000166, A000153, A000261, A001909, A001910, A055790, A346198, A346199, A346204.

Sequence in context: A003499 A279609 A253778 * A018953 A009199 A052824

Adjacent sequences: A346186 A346187 A346188 * A346190 A346191 A346192

Keyword

nonn

Author

Eugene Fiorini, Jared Glassband, Garrison Lee Koch, Sophia Lebiere, Xufei Liu, Evan Sabini, Nathan B. Shank, Andrew Woldar, Jul 09 2021

Status

approved