cp's OEIS Frontend

A180171 Triangle read by rows: R(n,k) is the number of k-reverses of n.

%I A180171 #32 Oct 21 2017 22:03:36
%S A180171 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,1,5,4,10,5,1,1,6,9,12,15,6,1,1,7,9,19,
%T A180171 15,21,7,1,1,8,10,24,30,20,28,8,1,1,9,12,36,26,54,28,36,9,1,1,10,15,
%U A180171 40,50,60,70,40,45,10,1,1,11,13,53,50,108,70,106,39,55,11,1,1,12,18,60,75,120
%N A180171 Triangle read by rows: R(n,k) is the number of k-reverses of n.
%C A180171 A k-composition of n is an ordered collection of k positive integers (parts) which sum to n.
%C A180171 Two k-compositions are cyclically equivalent if one can be obtained from the other by a cyclic permutation of its parts.
%C A180171 The reverse of a k-composition is the k-composition obtained by writing its parts in reverse.
%C A180171 For example the reverse of 123 is 321.
%C A180171 A k-reverse of n is a k-composition of n which is cyclically equivalent to its reverse.
%C A180171 For example 114 is a 3-reverse of 6 since its set of cyclic equivalents {114,411,141} contains its reverse 411. But 123 is not a 3-reverse of 6 since its set of cyclic equivalents {123,312,231} does not contain its reverse 321.
%D A180171 John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010.
%H A180171 Robert G. Wilson v, <a href="/A180171/b180171.txt">Table of n, a(n) for n = 1..500</a>.
%H A180171 Petros Hadjicostas, <a href="/A180171/a180171.pdf">Proofs of two formulae on the number of k-inverses of n</a>
%F A180171 R(n,k) = Sum_{d|gcd(n,k)} A180279(n/d, k/d). - _Andrew Howroyd_, Oct 08 2017
%F A180171 From _Petros Hadjicostas_, Oct 21 2017: (Start)
%F A180171 For proofs of these formulae, see the links.
%F A180171 R(n,k) = Sum_{d|gcd(n,k)} phi^{(-1)}(d)*(k/d)*A119963(n/d, k/d), where phi^{(-1)}(d) = A023900(d) is the Dirichlet inverse function of Euler's totient function.
%F A180171 G.f.: Sum_{s >= 1} phi^{(-1)}(s)*g(x^s, y^s), where phi^{(-1)}(s) = A023900(s) and g(x,y) = (x*y+x+1)*(x*y-x+1)*(x+1)*x*y/(x^2*y^2+x^2-1)^2.
%F A180171 (End)
%e A180171 The triangle begins
%e A180171   1
%e A180171   1 1
%e A180171   1 2 1
%e A180171   1 3 3 1
%e A180171   1 4 6 4 1
%e A180171   1 5 4 10 5 1
%e A180171   1 6 9 12 15 6 1
%e A180171   1 7 9 19 15 21 7 1
%e A180171   1 8 10 24 30 20 28 8 1
%e A180171   1 9 12 36 26 54 28 36 9 1
%e A180171 For example row 8 is 1 7 9 19 15 21 7 1
%e A180171 We have R(8,3)=9 because there are 9 3-reverses of 8. In classes: {116,611,161} {224,422,242}, and {233,323,332}.
%e A180171 We have R(8,6)=21 because all 21 6-compositions of 8 are 6-reverses of 8.
%t A180171 f[n_Integer, k_Integer] := Block[{c = 0, j = 1, ip = IntegerPartitions[n, {k}]}, lmt = 1 + Length@ ip; While[j < lmt, c += g[ ip[[j]]]; j++ ]; c]; g[lst_List] := Block[{c = 0, len = Length@ lst, per = Permutations@ lst}, While[ Length@ per > 0, rl = Union[ RotateLeft[ per[[1]], # ] & /@ Range@ len]; If[ MemberQ[rl, Reverse@ per[[1]]], c += Length@ rl]; per = Complement[ per, rl]]; c]; Table[ f[n, k], {n, 13}, {k, n}] // Flatten (* _Robert G. Wilson v_, Aug 25 2010 *)
%o A180171 (PARI) \\ here p(n,k) is A119963, AR(n,k) is A180279.
%o A180171 p(n,k) = binomial((n-k%2)\2, k\2);
%o A180171 AR(n,k) = k*sumdiv(gcd(n,k), d, moebius(d) * p(n/d, k/d));
%o A180171 T(n,k) = sumdiv(gcd(n,k), d, AR(n/d,k/d));
%o A180171 for(n=1, 10, for(k=1, n, print1(T(n,k), ", ")); print) \\ _Andrew Howroyd_, Oct 08 2017
%Y A180171 Row sums are A180249.
%Y A180171 Cf. A023900, A119963, A180279.
%K A180171 nonn,tabl
%O A180171 1,5
%A A180171 _John P. McSorley_, Aug 15 2010
%E A180171 a(56) onwards from _Robert G. Wilson v_, Aug 25 2010