A165964 Number of circular permutations of length n without increasing or decreasing 3-sequences.

1, 1, 0, 4, 16, 86, 542, 3932, 32330, 297438, 3028320, 33814454, 410954878, 5400878692, 76329470882, 1154445436334, 18606430004984, 318369275913710, 5764046146341198, 110091446931897180, 2212282487296335866, 46658484076867264702, 1030533208360458081232

Offset: 1

Author

Isaac Lambert, Oct 07 2009

Keywords

• nonn

Comments

Circular permutations are permutations whose indices are from the ring of integers modulo n. Increasing 3-sequences are of the form i,i+1,i+2, while decreasing 3-sequences are of the form i,i-1,i-2.

Examples

			For n=4 the a(4)=4 solutions are (0,1,3,2), (0,2,1,3), (0,2,3,1), and (0,3,1,2).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..450
• W. M. Dymacek, I. Lambert, Permutations Avoiding Runs of i, i+1, i+2 or i, i-1, i-2 , J. Int. Seq. 14 (2011) # 11.1.6, Table 1.

Crossrefs

Cf. A095816, A165963, A078628.

Formula

a(n) = A095816(n-1) - 2 * Sum_{i=1..[(n+1)/3]} (A095816(n-3*i) - A095816(n-1-3*i)). [Corrected by Sean A. Irvine, Jul 07 2025]

Extensions

Edited and more terms added by Max Alekseyev, Jun 14 2011