login
A179968
'AT(n,k)' triangle read by rows. AT(n,k) is the number of aperiodic k-compositions of n.
1
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
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
Sequence in context: A364912 A321449 A180279 * A323844 A350263 A360677
KEYWORD
nonn,tabl
AUTHOR
John P. McSorley, Aug 03 2010
EXTENSIONS
a(56)-a(66) from Andrew Howroyd, Mar 26 2017
STATUS
approved