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,4

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..23.

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

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

Example

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.

Prog

(Python) See A346204.

Crossrefs

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

Sequence in context: A371836 A149809 A263245 * A020050 A106958 A331336

Adjacent sequences: A346196 A346197 A346198 * A346200 A346201 A346202

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