A180279 - OEIS

%I #26 Apr 28 2020 14:59:06

%S 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,

%T 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,

%U 50,60,70,40,45,10,0,1,10,12,48,50,102,70,96,36,50,11,0

%N Triangle read by rows: AR(n,k) is the number of aperiodic k-reverses of n (n >= 1, 1 <= k <= n).

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

%C 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.

%C Two k-compositions are cyclically equivalent if one can be obtained from the other by a cyclic permutation of its parts.

%C 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.

%C 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.

%C 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.

%C 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.

%C Let AR(n,k) denote the number of aperiodic k-reverses of n.

%C This sequence is the 'AR(n,k)' triangle read by rows.

%D John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010.

%H Andrew Howroyd, <a href="/A180279/b180279.txt">Table of n, a(n) for n = 1..1275</a>

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

%e Triangle AR(n,k) (with n >= 1 and 1 <= k <= n) begins as follows:

%e   1

%e   1 0

%e   1 2  0

%e   1 2  3  0

%e   1 4  6  4  0

%e   1 4  3  8  5  0

%e   1 6  9 12 15  6  0

%e   1 6  9 16 15 18  7  0

%e   1 8  9 24 30 18 28  8 0

%e   1 8 12 32 25 48 28 32 9 0

%e   ...

%e For example, row 8 is 1 6 9 16 15 18 7 0.

%e We have AR(8,3) = 9 because there are 9 aperiodic 3-reverses of 8.

%e These are in the classes {116, 611, 161}, {224, 422, 242}, and {233, 323, 332}.

%e 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]

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

%o (PARI) \\ here p(n,k) is A119963.

%o p(n,k) = binomial((n-k%2)\2, k\2);

%o T(n, k) = k*sumdiv(gcd(n,k), d, moebius(d) * p(n/d, k/d));

%o for(n=1, 10, for(k=1, n, print1(T(n,k), ", ")); print) \\ _Andrew Howroyd_, Oct 08 2017

%Y If we ignore the aperiodic requirement, we get the sequence A180171.

%Y Row sums are A180322.

%Y Cf. A119963.

%K nonn,tabl

%O 1,5

%A _John P. McSorley_, Aug 23 2010

%E Terms a(56) and beyond from _Andrew Howroyd_, Oct 08 2017

%E Name edited by _Petros Hadjicostas_, Apr 28 2020