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

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

Offset: 1

Author

John P. McSorley, Aug 15 2010

Keywords

• nonn
• tabl

Comments

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

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.

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.

Examples

			The triangle begins
  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 15 21 7 1
  1 8 10 24 30 20 28 8 1
  1 9 12 36 26 54 28 36 9 1
For example row 8 is 1 7 9 19 15 21 7 1
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}.
We have R(8,6)=21 because all 21 6-compositions of 8 are 6-reverses of 8.
		

References

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

Links

• Robert G. Wilson v, Table of n, a(n) for n = 1..500.
• Petros Hadjicostas, Proofs of two formulae on the number of k-inverses of n

Crossrefs

Row sums are A180249.

Cf. A023900, A119963, A180279.

Programs

Mathematica

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

PARI

\\ here p(n,k) is A119963, AR(n,k) is A180279.
p(n,k) = binomial((n-k%2)\2, k\2);
AR(n,k) = k*sumdiv(gcd(n,k), d, moebius(d) * p(n/d, k/d));
T(n,k) = sumdiv(gcd(n,k), d, AR(n/d,k/d));
for(n=1, 10, for(k=1, n, print1(T(n,k), ", ")); print) \\ Andrew Howroyd, Oct 08 2017

Formula

R(n,k) = Sum_{d|gcd(n,k)} A180279(n/d, k/d). - Andrew Howroyd, Oct 08 2017

From Petros Hadjicostas, Oct 21 2017: (Start)

For proofs of these formulae, see the links.

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.

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.

(End)

Extensions

a(56) onwards from Robert G. Wilson v, Aug 25 2010