|
|
A179317
|
|
'APE(n,k)' triangle read by rows. APE(n,k) is the number of aperiodic k-palindromes of n up to cyclic equivalence.
|
|
4
|
|
|
1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 3, 0, 3, 0, 0, 1, 0, 3, 1, 3, 1, 1, 0, 1, 0, 3, 0, 6, 0, 4, 0, 0, 1, 0, 4, 2, 5, 2, 4, 2, 1, 0, 1, 0, 5, 0, 10, 0, 10, 0, 5, 0, 0, 1, 0, 4, 2, 10, 4, 10, 4, 4, 2, 1, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,13
|
|
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-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 APE(n,k) denote the number of aperiodic k-palindromes of n up to cyclic equivalence.
This sequence is the 'APE(n,k)' triangle read by rows.
The only possibility for two distinct aperiodic palindromes to be cyclically equivalent is with an even number of terms and with a rotation by half the number of terms. For example, 123321 is cyclically equivalent to 321123. - Andrew Howroyd, Oct 07 2017
|
|
REFERENCES
|
John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
The triangle begins
1
1,0
1,0,0
1,0,1,0
1,0,2,0,0
1,0,1,1,1,0
1,0,3,0,3,0,0
1,0,3,1,3,1,1,0
1,0,3,0,6,0,4,0,0
1,0,4,2,5,2,4,2,1,0
For example, row 8 is 1,0,3,1,3,1,1,0.
We have APE(8,3)=3 because there are 3 aperiodic 3-palindromes of 8, namely: 161, 242, and 323, and none are cyclically equivalent to the others.
We have APE(8,4)=1 because there are 2 aperiodic 4-palindromes of 8, namely: 3113 and 1331, but they are cyclically equivalent.
|
|
MATHEMATICA
|
T[n_, k_] := (3-(-1)^k)/4*Sum[MoebiusMu[d]*QBinomial[n/d - 1, k/d - 1, -1], {d, Divisors[GCD[n, k]]}];
|
|
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) = if(k%2, 1, 1/2) * 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
|
The row sums of the 'APE(n, k)' triangle give sequence A056513.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|