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

Author

John P. McSorley, Jul 17 2010

Keywords

• nonn
• tabl

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

Examples

			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.
		

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

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

Programs

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

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

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

Extensions

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