A363431 Number of 123-avoiding stabilized-interval-free permutations of size n.

1, 1, 1, 2, 5, 14, 44, 150, 496, 1758, 6018, 21782, 76414, 280448, 1001752, 3714032, 13450270, 50259604, 183995056, 691863078, 2555043320, 9657267848, 35921300392, 136360740016, 510267869416, 1944193285228, 7312488701868, 27950641500876, 105590010259396, 404724123141348, 1534775681029994

Offset

0,4

Comments

A stabilized-interval-free (SIF) permutation on [n] = {1, 2, ..., n} is one that does not stabilize any proper subinterval of [n].

Links

Table of n, a(n) for n=0..30.

Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.

Formula

For n>2, a(n) = f_0(n) - f_1(n-1) + f_2(n) - Sum_{k=1..floor((n-3)/2)} C(k)^2*a(n-2*k), where C(k)=binomial(2*k,k)/(k+1) and f_j(m) denotes the number of 123-avoiding permutations of size m having j fixed points.

Example

For n=4 the a(4)=5 permutations are 2413, 3142, 3412, 3421, 4312.

Crossrefs

Cf. A075834.

Sequence in context: A149883 A307786 A360592 * A149884 A149885 A149886

Adjacent sequences: A363428 A363429 A363430 * A363432 A363433 A363434

Keyword

nonn

Author

Juan B. Gil, Jun 22 2023

Status

approved