cp's OEIS Frontend

A180424 "ARE(n,k)" triangle read by rows. ARE(n,k) is the number of aperiodic k-reverses of n up to cyclic equivalence.

%I A180424 #29 Jan 21 2023 14:44:27
%S A180424 1,1,0,1,1,0,1,1,1,0,1,2,2,1,0,1,2,1,2,1,0,1,3,3,3,3,1,0,1,3,3,4,3,3,
%T A180424 1,0,1,4,3,6,6,3,4,1,0,1,4,4,8,5,8,4,4,1,0,1,5,5,10,10,10,10,5,5,1,0,
%U A180424 1,5,4,12,10,17,10,12,4,5,1,0
%N A180424 "ARE(n,k)" triangle read by rows. ARE(n,k) is the number of aperiodic k-reverses of n up to cyclic equivalence.
%C A180424 A k-composition of n is an ordered collection of k positive integers (parts) which sum to n.
%C A180424 A k-composition is aperiodic (primitive) if its period is k, or if it is not the concatenation of at least two smaller compositions.
%C A180424 Two k-compositions are cyclically equivalent if one can be obtained from the other by a cyclic permutation of its parts.
%C A180424 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 A180424 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 A180424 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 A180424 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 A180424 Let AR(n,k) denote the number of aperiodic k-reverses of n, then sequence A180279 is the 'AR(n,k)' triangle read by rows.
%C A180424 For the above sequence we count the aperiodic k-reverses of n up to cyclic equivalence, ARE(n,k), in other words, the number of equivalence classes under cyclic permutation which contain at least one aperiodic k-reverse of n.
%D A180424 John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010.
%H A180424 Andrew Howroyd, <a href="/A180424/b180424.txt">Table of n, a(n) for n = 1..1275</a>
%F A180424 ARE(n,k) = Sum_{d|gcd(n,k)} mu(d) * A119963(n/d,k/d). - _Andrew Howroyd_, Oct 07 2017
%e A180424 The triangle begins
%e A180424   1
%e A180424   1 0
%e A180424   1 1 0
%e A180424   1 1 1 0
%e A180424   1 2 2 1 0
%e A180424   1 2 1 2 1 0
%e A180424   1 3 3 3 3 1 0
%e A180424   1 3 3 4 3 3 1 0
%e A180424   1 4 3 6 6 3 4 1 0
%e A180424   1 4 4 8 5 8 4 4 1 0
%e A180424 For example, row 8 is 1 3 3 4 3 3 1 0.
%e A180424 We have ARE(8,3)=3 because there are 9 aperiodic 3-reverses of 8 in the 3 classes {116,611,161}, {224,422,242}, and {233,323,332}, and so there are ARE(8,3)=3 aperiodic 3-reverses of 8 up to cyclic equivalence.
%e A180424 We have ARE(8,6)=3 because there are 3 aperiodic 6-reverses of 8 up to cyclic equivalence. The representatives of the 3 classes are 111113, 111122, and 111212.
%t A180424 Table[DivisorSum[GCD[n, k], MoebiusMu[#]*Binomial[Floor[((n/#) - Boole[OddQ[k/#]])/2], Floor[k/(2 #)]] &], {n, 12}, {k, n}] // Flatten (* _Michael De Vlieger_, Oct 31 2021 *)
%o A180424 (PARI) \\ here RE(n,k) is A119963(n,k).
%o A180424 RE(n,k) = binomial((n-k%2)\2, k\2);
%o A180424 T(n,k) = sumdiv(gcd(n,k), d, moebius(d)*RE(n/d,k/d));
%o A180424 for(n=1, 10, for(k=1, n, print1(T(n,k), ", ")); print) \\ _Andrew Howroyd_, Oct 07 2017
%Y A180424 As mentioned above, if we don't count the classes, but rather the elements in the classes, we get sequence A180279.
%Y A180424 If we remove the aperiodic requirement, see sequence A119963.
%Y A180424 The row sums of the "ARE(n, k)" triangle above give sequence A056493 (except for the first term). See also sequence A056498.
%K A180424 nonn,tabl
%O A180424 1,12
%A A180424 _John P. McSorley_, Sep 03 2010
%E A180424 Terms a(56) and beyond from _Andrew Howroyd_, Oct 07 2017