A304201 a(n) is the number of cyclic permutations of length n that admit a [1,-1,-1]-gridding.

1, 1, 1, 2, 5, 15, 43, 120, 338, 952, 2672, 7494, 21035, 59115, 166433, 469560, 1327802, 3763545, 10692500, 30447858, 86894361, 248506757, 712109663, 2044402512, 5879579540, 16937048040, 48864612668, 141179970820, 408444645375, 1183143522435, 3431241484223, 9961919944284

Offset: 0

Author

Kassie Archer, May 08 2018

Keywords

• nonn

Comments

a(n) is the number of permutations of length n that are composed of an increasing segment, followed by a decreasing segment, followed by another decreasing segment. In other words, these permutation have a descent set of the form {i, i+1, ..., n-1} for some i or {i, i+1, ..., n-1}\{j} for some i and j > i.

Crossrefs

Cf. A027376, A303979, A133267.

Programs

PARI

t051168(n, k) = if (n==0, 1, (1/n) * sumdiv(gcd(n, k), d, moebius(d) * binomial(n/d, k/d)));
T303979(n, k) = my(t=sum(j=1, k-1, (-1)^(k+j+1)*t051168(n, j))); if (!(n % 2), t += (-1)^(k+1)*sum(j=1, k-1, if (((n-j) % 4) == 2, t051168(n/2, j/2)))); t;
a027376(n) = if(n<1, n==0, sumdiv(n, d, moebius(n/d)*3^d)/n);
a133267(n) = sumdiv(n, d, moebius(d)*3^(n/d)/n - if (d%2, moebius(d)*(3^(n/d)-1)/(2*n)));
a006575(n) = sumdiv(n, d, if ( bitand(d, 1), moebius(d) * (3^(n/d)-1) , 0 ) ) / (2*n);
a(n) = if (n <= 2, 1, res = a027376(n)/2 - sum(i=2, n-1, (n+1-i)*T303979(n,i)); if (!(n%2), if ((n%4)==2, res += a133267(n/2)/2, res += a006575(n/2)/2)); res); \\ Michel Marcus, May 18 2018

Formula

a(n) = A027376(n)/2 - Sum_{i=2..n-1} (n+1-i)*A303979(n,i), when n is odd and n > 2;

a(n) = (A027376(n) + A133267(n/2))/2 - Sum_{i=2..n-1} (n+1-i)*A303979(n,i), when n = 2 (mod 4) and n > 2.

a(n) = (A027376(n) + A006575(n/2))/2 - Sum_{i=2..n-1} (n+1-i)*A303979(n,i), when n = 0 (mod 4) and n > 2.

Extensions

More terms from Michel Marcus, May 19 2018