A179968 'AT(n,k)' triangle read by rows. AT(n,k) is the number of aperiodic k-compositions of n.

1, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 4, 6, 4, 0, 1, 4, 9, 8, 5, 0, 1, 6, 15, 20, 15, 6, 0, 1, 6, 21, 32, 35, 18, 7, 0, 1, 8, 27, 56, 70, 54, 28, 8, 0, 1, 8, 36, 80, 125, 120, 84, 32, 9, 0, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 0

Offset

1,5

Comments

A k-composition of n is an ordered collection of k positive integers (parts) which sum to n.

A k-composition is aperiodic (primitive) if its period is k, or if it is not the concatenation of at least two smaller compositions.

Let AT(n,k) denote the number of aperiodic k-compositions of n.

This sequence is the 'AT(n,k)' triangle read by rows.

If we form the row sum sequence of the 'AT(n, k)' triangle above we get sequence A056278, except for the first term.

If we form the triangle which counts the aperiodic k-compositions of n up to cyclic equivalence, ATE(n, k), and place an extra 0 at the end of each row of the 'ATE(n, k)' triangle, we get sequence A051168 (Lyndon words).

References

John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010. [Apparently unpublished as of Mar 27 2017]

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.

Formula

T(n,k) = k * A051168(n,k). - Andrew Howroyd, Mar 26 2017

T(n,k) = (k/n) * Sum_{d | gcd(n,k)} mu(d) * binomial(n/d,k/d). - Andrew Howroyd, Mar 26 2017

G.f.: Sum_{k>=1}mu(k)y^k A(x^k)/(1 - y^k A(x^k)) where mu(k) is the Moebius Mu function and A(x) = x/(1-x). - Geoffrey Critzer, Aug 05 2022

Example

The triangle begins
  1
  1, 0
  1, 2,  0
  1, 2,  3,  0
  1, 4,  6,  4,   0
  1, 4,  9,  8,   5,   0
  1, 6, 15, 20,  15,   6,  0
  1, 6, 21, 32,  35,  18,  7,  0
  1, 8, 27, 56,  70,  54, 28,  8, 0
  1, 8, 36, 80, 125, 120, 84, 32, 9, 0
For example, row 8 is 1, 6, 21, 32, 35, 18, 7, 0.
We have AT(8,2)=6 because there are 6 aperiodic 2-compositions of 8, namely: 17, 71, 26, 62, 35, 53. The remaining 2-composition of 8 is 44, it is not aperiodic.
We have AT(8,3)=21 because all 21 3-compositions of 8 are aperiodic.

Mathematica

T[n_, k_]:=(k/n) * Sum[MoebiusMu[d] Binomial[n/d, k/d], {d, Divisors[GCD[n, k]]}]; Flatten[Table[T[n, k], {n, 11}, {k, n}]] (* Indranil Ghosh, Mar 27 2017, after the formula by Andrew Howroyd *)

Crossrefs

Cf. A051168, A056278.

Sequence in context: A364912 A321449 A180279 * A323844 A350263 A360677

Adjacent sequences: A179965 A179966 A179967 * A179969 A179970 A179971

Keyword

nonn,tabl

Author

John P. McSorley, Aug 03 2010

Extensions

a(56)-a(66) from Andrew Howroyd, Mar 26 2017

Status

approved