A179519 - OEIS

%I #30 Nov 05 2017 11:51:44

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

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

%U 0,4,4,10,8,10,8,4,4,1,0

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

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

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

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

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

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

%C 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

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

%H Andrew Howroyd, <a href="/A179519/b179519.txt">Table of n, a(n) for n = 1..1275</a>

%F T(n,k) = Sum_{d|gcd(n,k)} mu(d) * A051159(n/d-1, k/d-1). - _Andrew Howroyd_, Oct 07 2017

%F 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

%e The triangle begins

%e   1

%e   1,0

%e   1,0,0

%e   1,0,1,0

%e   1,0,2,0,0

%e   1,0,1,2,1,0

%e   1,0,3,0,3,0,0

%e   1,0,3,2,3,2,1,0

%e   1,0,3,0,6,0,4,0,0

%e   1,0,4,4,5,4,4,4,1,0

%e For example, row 8 is 1,0,3,2,3,2,1,0.

%e We have AP(8,3)=3 because there are 3 aperiodic 3-palindromes of 8, namely: 161, 242, and 323.

%e We have AP(8,4)=2 because there are 2 aperiodic 4-palindromes of 8, namely: 3113 and 1331.

%t 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_ *)

%o (PARI) \\ here p(n,k)=A051159(n-1,k-1) is number of k-palindromes of n.

%o p(n, k) = if(n%2==1&&k%2==0, 0, binomial((n-1)\2, (k-1)\2));

%o T(n, k) = sumdiv(gcd(n,k), d, moebius(d) * p(n/d, k/d));

%o for(n=1, 10, for(k=1, n, print1(T(n,k), ", ")); print) \\ _Andrew Howroyd_, Oct 07 2017

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

%Y The row sums of this triangle give sequence A179781. - _John P. McSorley_, Jul 26 2010

%K nonn,tabl

%O 1,13

%A _John P. McSorley_, Jul 17 2010

%E Terms a(56) and beyond from _Andrew Howroyd_, Oct 07 2017