login
A180279
Triangle read by rows: AR(n,k) is the number of aperiodic k-reverses of n (n >= 1, 1 <= k <= n).
6
1, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 4, 6, 4, 0, 1, 4, 3, 8, 5, 0, 1, 6, 9, 12, 15, 6, 0, 1, 6, 9, 16, 15, 18, 7, 0, 1, 8, 9, 24, 30, 18, 28, 8, 0, 1, 8, 12, 32, 25, 48, 28, 32, 9, 0, 1, 10, 15, 40, 50, 60, 70, 40, 45, 10, 0, 1, 10, 12, 48, 50, 102, 70, 96, 36, 50, 11, 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 [identical] compositions.
Two k-compositions are cyclically equivalent if one can be obtained from the other by a cyclic permutation of its parts.
The reverse of a k-composition is the k-composition obtained by writing its parts in reverse. For example the reverse of 123 is 321.
A k-reverse of n is a k-composition of n which is cyclically equivalent to its reverse. And an aperiodic k-reverse of n is a k-reverse of n which is aperiodic.
For example, 114 is an aperiodic 3-reverse of 6 since it is aperiodic and its set of cyclic equivalents {114, 411, 141} contains its reverse 411.
But 123 is not an aperiodic 3-reverse of 6 since, even though it is aperiodic, its set of cyclic equivalents {123, 312, 231} does not contain its reverse 321.
Let AR(n,k) denote the number of aperiodic k-reverses of n.
This sequence is the 'AR(n,k)' triangle read by rows.
REFERENCES
John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010.
LINKS
FORMULA
AR(n, k) = k * Sum_{d|gcd(n,k)} mu(d) * A119963(n/d, k/d). - Andrew Howroyd, Oct 08 2017 (Corrected by Petros Hadjicostas, Oct 11 2017.)
EXAMPLE
Triangle AR(n,k) (with n >= 1 and 1 <= k <= n) begins as follows:
1
1 0
1 2 0
1 2 3 0
1 4 6 4 0
1 4 3 8 5 0
1 6 9 12 15 6 0
1 6 9 16 15 18 7 0
1 8 9 24 30 18 28 8 0
1 8 12 32 25 48 28 32 9 0
...
For example, row 8 is 1 6 9 16 15 18 7 0.
We have AR(8,3) = 9 because there are 9 aperiodic 3-reverses of 8.
These are in the classes {116, 611, 161}, {224, 422, 242}, and {233, 323, 332}.
We have AR(8,6) = 18 because all, except 3, of the 21 6-compositions of 8 are aperiodic 6-reverses of 8. The missing 3 form one class, {112112, 211211, 121121}, and they are each 6-reverses of 8, but they are each periodic of period 3; so, they are not aperiodic. [Edited by Petros Hadjicostas, Apr 27 2020]
MATHEMATICA
Table[k DivisorSum[GCD[n, k], MoebiusMu[#] Apply[Binomial[Floor[(#1 - Boole[OddQ@ #2])/2], Floor[#2/2]] &, {n/#, k/#}] &], {n, 12}, {k, n}] // Flatten (* Michael De Vlieger, Oct 11 2017 *)
PROG
(PARI) \\ here p(n, k) is A119963.
p(n, k) = binomial((n-k%2)\2, k\2);
T(n, k) = k*sumdiv(gcd(n, k), d, moebius(d) * p(n/d, k/d));
for(n=1, 10, for(k=1, n, print1(T(n, k), ", ")); print) \\ Andrew Howroyd, Oct 08 2017
CROSSREFS
If we ignore the aperiodic requirement, we get the sequence A180171.
Row sums are A180322.
Cf. A119963.
Sequence in context: A361756 A364912 A321449 * A179968 A323844 A350263
KEYWORD
nonn,tabl
AUTHOR
John P. McSorley, Aug 23 2010
EXTENSIONS
Terms a(56) and beyond from Andrew Howroyd, Oct 08 2017
Name edited by Petros Hadjicostas, Apr 28 2020
STATUS
approved