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

Author

Juan B. Gil, Jun 22 2023

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

Cf. A075834.

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.