A346199 a(n) is the number of permutations on [n] with at least one strong fixed point and no small descents.

1, 1, 1, 5, 19, 95, 569, 3957, 31455, 281435, 2799981, 30666153, 366646995, 4751669391, 66348304849, 992975080813, 15856445382119, 269096399032035, 4836375742967861, 91766664243841393, 1833100630242606203, 38452789552631651191, 845116020421125048153

Offset: 1

Author

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

Keywords

• nonn

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.

Examples

			For n = 4, the a(4) = 5 permutations on [4] with strong fixed points but no small descents: {(1*, 2*, 3*, 4*), (1*, 3, 4, 2), (1*, 4, 2, 3), (2, 3, 1, 4*), (3, 1, 2, 4*)} where * marks strong fixed points.
		

References

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

Links

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

Crossrefs

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

Programs

Python

See A346204.

Formula

a(n) = b(n-1) + Sum_{i=4..n} A346189(i-1)*b(n-i) where b(n) = A000255(n).