login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A296372 Triangle read by rows: T(n,k) is the number of normal sequences of length n whose standard factorization into Lyndon words (aperiodic necklaces) has k factors. 21
1, 1, 2, 4, 5, 4, 18, 31, 18, 8, 108, 208, 153, 56, 16, 778, 1700, 1397, 616, 160, 32, 6756, 15980, 14668, 7197, 2196, 432, 64, 68220, 172326, 171976, 93293, 31564, 7208, 1120, 128 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

A finite sequence is normal if its union is an initial interval of positive integers.

LINKS

Andrew Howroyd, Rows n = 1..50 of triangle, flattened

Wikipedia, Lyndon word: Standard factorization

EXAMPLE

The T(3,2) = 5 normal sequences are {2,1,2}, {1,2,1}, {2,1,3}, {2,3,1}, {3,1,2}.

Triangle begins:

     1;

     1,     2;

     4,     5,     4;

    18,    31,    18,     8;

   108,   208,   153,    56,    16;

   778,  1700,  1397,   616,   160,    32;

  6756, 15980, 14668,  7197,  2196,   432,    64;

MATHEMATICA

neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];

aperQ[q_]:=UnsameQ@@Table[RotateRight[q, k], {k, Length[q]}];

qit[q_]:=If[#===Length[q], {q}, Prepend[qit[Drop[q, #]], Take[q, #]]]&[Max@@Select[Range[Length[q]], neckQ[Take[q, #]]&&aperQ[Take[q, #]]&]];

allnorm[n_]:=Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1];

Table[Length[Select[Join@@Permutations/@allnorm[n], Length[qit[#]]===k&]], {n, 5}, {k, n}]

PROG

(PARI) \\ here U(n, k) is A074650(n, k).

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i, vars))/i ))-1)}

U(n, k)={sumdiv(n, d, moebius(n/d) * k^d)/n}

A(n)={[Vecrev(p/y) | p<-sum(k=1, n, EulerMT(vector(n, n, y*U(n, k)))*sum(j=k, n, (-1)^(k-j)*binomial(j, k)))]}

{ my(T=A(10)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Dec 08 2018

CROSSREFS

Row sums are A000670.

First column is A060223.

Cf. A000740, A001045, A008965, A019536, A059966, A074650, A185700, A228369, A232472, A277427, A281013, A296373.

Sequence in context: A200289 A165044 A274079 * A278300 A034214 A317749

Adjacent sequences:  A296369 A296370 A296371 * A296373 A296374 A296375

KEYWORD

nonn,tabl

AUTHOR

Gus Wiseman, Dec 11 2017

EXTENSIONS

Example and program corrected by Gus Wiseman, Dec 08 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 17 14:30 EDT 2021. Contains 343972 sequences. (Running on oeis4.)