login
A346199
a(n) is the number of permutations on [n] with at least one strong fixed point and no small descents.
3
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
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.
KEYWORD
nonn
STATUS
approved