login
A346189
a(n) is the number of permutations on [n] with no strong fixed points or small descents.
3
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
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.
KEYWORD
nonn
STATUS
approved