login
a(n) is the number of cyclic permutations with at most 2 ascents.
0

%I #16 May 18 2018 20:44:06

%S 1,1,1,2,6,18,58,186,570,1680,4878,14058,40200,114450,325290,923846,

%T 2624730,7465410,21261828,60647370,173288724,496014934,1422223506,

%U 4084793082,11751102060,33857989968,97697014590,282295318536,816759712080,2366027865810,6861964439314

%N a(n) is the number of cyclic permutations with at most 2 ascents.

%C a(n) is the number of cyclic permutations with at most two ascents. These permutations can also be characterized as admitting a [1, 1, 1]-gridding, meaning they are composed of three contiguous increasing segments.

%H K. Archer and S. Elizalde, <a href="http://dx.doi.org/10.4310/JOC.2014.v5.n1.a1">Cyclic permutations realized by signed shifts</a>, Journal of Combinatorics, 5 (2014), 1-30.

%H I. M. Gessel and C. Reutenauer, <a href="http://dx.doi.org/10.1016/0097-3165(93)90095-P">Counting permutations with given cycle structure and descent set</a>, J. Combin. Theory, Ser. A, 64, 1993, 189-215.

%F a(n) = L(3,n) - n*L(2,n) when n !== 2 (mod 4) and n>2;

%F a(n) = L(3,n) + L(3,n/2) - n*(L(2,n) + L(2,n/2)) when n == 2 (mod 4) and n>2;

%F where L(k,n) is the number of k-ary Lyndon words of length n.

%o (PARI) L2(n) = if(n>1, sumdiv(n, d, moebius(d)*2^(n/d))/n, n+1); \\ A001037

%o L3(n) = if(n<1, n==0, sumdiv(n, d, moebius(n/d)*3^d)/n); \\ A027376

%o a(n) = if (n <=2, 1, if ((n % 4) != 2, L3(n) - n*L2(n), L3(n) + L3(n/2) - n*(L2(n) + L2(n/2)))); \\ _Michel Marcus_, May 16 2018

%Y Equals A303117 when n !== 2 (mod 4).

%Y Cf. A001037, A027376.

%K nonn

%O 0,4

%A _Kassie Archer_, May 07 2018