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

Author

John P. McSorley, Aug 03 2010

Keywords

• nonn
• tabl

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).

Examples

			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.
		

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.

Crossrefs

Cf. A051168, A056278.

Programs

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 *)

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

Extensions

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