A179519 'AP(n,k)' triangle read by rows. AP(n,k) is the number of aperiodic k-palindromes of n.

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

Offset

1,13

Comments

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

A k-composition is aperiodic (primitive) if its period is k, or if it is not the concatenation of a smaller composition.

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

Let AP(n,k) denote the number of aperiodic k-palindromes of n.

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

The g.f. of this triangular array follows easily from A. Howroyd's formula for this sequence and P. Deleham's g.f. for sequence A051159. If T(n,k) = A051159(n,k), then g.f. = Sum_{n,k>=1} AP(n,k)*x^n*y^k = Sum_{n,k>=1} Sum_{d|gcd(n,k)} mu(d)*T(n/d-1,k/d-1)*x^n*y^k. Letting m = n/d and s = k/d, we get g.f. = Sum_{d>=1} mu(d)*Sum_{m,s>=1} T(m-1,s-1)*(x^d)^m*(y^d)^s. But P. Deleham's formula for sequence A051159 implies Sum_{m,s>=1} T(m-1,s-1)*x^m*y^s = x*y*(1+x+x*y)/(1-x^2-x^2*y^2). Thus, Sum_{n,k>=1} AP(n,k)*x^n*y^k = Sum_{d>=1} mu(d)*f(x^d,y^d), where f(x,y) = x*y*(1+x+x*y)/(1-x^2-x^2*y^2). - Petros Hadjicostas, Nov 04 2017

References

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

Links

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

Formula

T(n,k) = Sum_{d|gcd(n,k)} mu(d) * A051159(n/d-1, k/d-1). - Andrew Howroyd, Oct 07 2017

G.f.: Sum_{n>=1} mu(n)*f(x^n,y^n), where f(x,y) = x*y*(1+x+x*y)/(1-x^2-x^2*y^2). - Petros Hadjicostas, Nov 04 2017

Example

The triangle begins
  1
  1,0
  1,0,0
  1,0,1,0
  1,0,2,0,0
  1,0,1,2,1,0
  1,0,3,0,3,0,0
  1,0,3,2,3,2,1,0
  1,0,3,0,6,0,4,0,0
  1,0,4,4,5,4,4,4,1,0
For example, row 8 is 1,0,3,2,3,2,1,0.
We have AP(8,3)=3 because there are 3 aperiodic 3-palindromes of 8, namely: 161, 242, and 323.
We have AP(8,4)=2 because there are 2 aperiodic 4-palindromes of 8, namely: 3113 and 1331.

Mathematica

T[n_, k_] := Sum[MoebiusMu[d]*QBinomial[n/d-1, k/d-1, -1], {d, Divisors[ GCD[n, k]]}]; Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 30 2017, after Andrew Howroyd *)

Prog

(PARI) \\ here p(n, k)=A051159(n-1, k-1) is number of k-palindromes of n.
p(n, k) = if(n%2==1&&k%2==0, 0, binomial((n-1)\2, (k-1)\2));
T(n, k) = sumdiv(gcd(n, k), d, moebius(d) * p(n/d, k/d));
for(n=1, 10, for(k=1, n, print1(T(n, k), ", ")); print) \\ Andrew Howroyd, Oct 07 2017

Crossrefs

If we count the aperiodic k-palindromes of n up to cyclic equivalence, APE(n, k), we get sequence A179317.

The row sums of this triangle give sequence A179781. - John P. McSorley, Jul 26 2010

Sequence in context: A320808 A338203 A324930 * A091979 A321742 A228716

Adjacent sequences: A179516 A179517 A179518 * A179520 A179521 A179522

Keyword

nonn,tabl

Author

John P. McSorley, Jul 17 2010

Extensions

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

Status

approved