A179181 'PE(n,k)' triangle read by rows. PE(n,k) is the number of k-palindromes of n up to cyclic equivalence.

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 2, 0, 1, 1, 1, 2, 1, 1, 1, 1, 0, 3, 0, 3, 0, 1, 1, 1, 3, 2, 3, 2, 1, 1, 1, 0, 4, 0, 6, 0, 4, 0, 1, 1, 1, 4, 2, 6, 4, 4, 2, 1, 1, 1, 0, 5, 0, 10, 0, 10, 0, 5, 0, 1, 1, 1, 5, 3, 10, 6, 10, 5, 5, 3, 1, 1

Offset: 1

Author

John P. McSorley, Jun 30 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 of n are cyclically equivalent if one can be obtained from the other by a cyclic permutation of its parts.

A k-palindrome of n is a k-composition of n which is a palindrome.

Let PE(n,k) denote the number of k-palindromes of n up to cyclic equivalence.

This sequence is the 'PE(n,k)' triangle read by rows.

Examples

			The triangle begins
  1
  1,1
  1,0,1
  1,1,1,1
  1,0,2,0,1
  1,1,2,1,1,1
  1,0,3,0,3,0,1
  1,1,3,2,3,2,1,1
  1,0,4,0,6,0,4,0,1
  1,1,4,2,6,4,4,2,1,1
For example, row 8 is 1,1,3,2,3,2,1,1.
We have PE(8,3)=3 because there are 3 3-palindromes of 8, namely: 161, 242, and 323, and none are cyclically equivalent to the others.
We have PE(8,4)=2 because there are 3 4-palindromes of 8, namely: 3113, 1331, and 2222, but 3113 and 1331 are cyclically equivalent.
		

References

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275

Crossrefs

If we ignore cyclic equivalence then we have sequence A051159.

The row sums of the 'PE(n, k)' triangle give sequence A056503.

Cf. A179317, A179519.

Programs

Mathematica

T[n_, k_] := (3 - (-1)^k)/4*Sum[MoebiusMu[d]*QBinomial[n/d - 1, k/d - 1, -1], {d, Divisors@ GCD[n, k]}]; Table[DivisorSum[GCD[n, k], T[n/#, k/#] &], {n, 12}, {k, n}] // Flatten (* Michael De Vlieger, Oct 31 2021, after Jean-François Alcover at A179317 *)

PARI

p(n, k) = if(n%2==1&&k%2==0, 0, binomial((n-1)\2, (k-1)\2));
APE(n, k) = if(k%2,1,1/2) * sumdiv(gcd(n,k), d, moebius(d) * p(n/d, k/d));
T(n, k) = sumdiv(gcd(n,k), d, APE(n/d, k/d));
for(n=1, 10, for(k=1, n, print1(T(n,k), ", ")); print) \\ Andrew Howroyd, Oct 07 2017

Formula

PE(n, k) = Sum_{d | gcd(n,k)} A179317(n/d, k/d). - Andrew Howroyd, Oct 07 2017

Extensions

Terms a(56) and beyond from Andrew Howroyd, Oct 07 2017