A370686 a(n) is the number of 132-avoiding permutations p so that p^3 is the identity permutation.

1, 1, 1, 3, 5, 7, 17, 31, 49, 107, 201, 339, 699, 1327, 2327, 4643, 8843, 15895, 31099, 59251, 108239, 209239, 398355, 735619, 1411351, 2684147, 4993111, 9533775, 18112735, 33863375, 64457715, 122348279, 229537011, 436029791, 827012339, 1555314327, 2950532447, 5592873575, 10536068991

Offset

0,4

Comments

a(n) is the number of 132-avoiding permutations composed only of 3-cycles and fixed points.

Links

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Kassie Archer and Robert P. Laudone, Pattern-restricted permutations of small order, arXiv:2402.15463 [math.CO], 2024.

Seiichi Manyama, Recurrence of order 34

Formula

G.f.: c(x^3)/(sqrt(c(x^3)*(4-3*c(x^3)))-x*c(x^3)) where c(x) is the generating function for the Catalan numbers.

From Seiichi Manyama, Jul 02 2026: (Start)

G.f. A(x) satisfies (x^4+16*x^3+2*x^2-3)*A(x)^4 + (4*x^3+4*x)*A(x)^3 + (6*x^2+2)*A(x)^2 + 4*x*A(x) + 1 = 0.

a(n) = 1 + 2 * Sum_{i=0..floor(n/3)-1} (n-3*i-2)/(i+1) * Sum_{j=0..i} 4^j * binomial((n-3*i-2)/2+j,j) * binomial(2*i-j,i).

D-finite with a recurrence of order 34 (see link). (End)

Prog

(PARI) my(N=44, x='x+O('x^N), C(x)=(1-sqrt(1-4*x))/(2*x)); Vec(C(x^3)/(sqrt(C(x^3)*(4-3*C(x^3)))-x*C(x^3))) \\ Joerg Arndt, Feb 27 2024
(PARI) a(n) = 1+2*sum(i=0, n\3-1, (n-3*i-2)/(i+1)*sum(j=0, i, 4^j*binomial((n-3*i-2)/2+j, j)*binomial(2*i-j, i))); \\ Seiichi Manyama, Jul 02 2026

Crossrefs

Cf. A000108, A309331.

Sequence in context: A002092 A274906 A296422 * A174394 A057476 A016041

Adjacent sequences: A370683 A370684 A370685 * A370687 A370688 A370689

Keyword

nonn,changed

Author

Kassie Archer, Feb 26 2024

Status

approved