A179519 -id:A179519 - cp's OEIS frontend

A179781 a(n) = AP(n) is the total number of aperiodic k-palindromes of n, 1 <= k <= n.

1, 1, 1, 2, 3, 5, 7, 12, 14, 27, 31, 54, 63, 119, 123, 240, 255, 490, 511, 990, 1015, 2015, 2047, 4020, 4092, 8127, 8176, 16254, 16383, 32607, 32767, 65280, 65503, 130815, 131061, 261576, 262143, 523775, 524223, 1047540, 1048575, 2096003, 2097151, 4192254

Offset: 1

John P. McSorley, Jul 26 2010

nonn

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.
This sequence is AP(n), the total number of aperiodic k-palindromes of n, 1 <= k <= n.
For example AP(6)=5 because the number n=6
has 1 aperiodic 1-palindrome, namely 6 itself;
has 1 aperiodic 3-palindrome, namely 141;
has 2 aperiodic 4-palindromes, namely 2112 and 1221;
has 1 aperiodic 5-palindrome, namely 11211.
This gives a total of 1+1+2+1=5 aperiodic palindromes of 6.
Number of achiral set partitions of a primitive cycle of n elements having up to two different elements. - Robert A. Russell, Jun 19 2019

			For a(7)=7, the achiral set partitions are 0000001, 0000011, 0000101, 0000111, 0001001, 0010011, and 0010101. - _Robert A. Russell_, Jun 19 2019

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

Andrew Howroyd, Table of n, a(n) for n = 1..200
Hunki Baek, Sejeong Bang, Dongseok Kim, Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014.

Row sums of A179519.

A000048 (oriented), A000046 (unoriented), A308706 (chiral), A016116 (not primitive). - Robert A. Russell, Jun 19 2019

a[n_] := DivisorSum[n, MoebiusMu[n/#] * 2^Floor[#/2]&];
Array[a, 44] (* Jean-François Alcover, Nov 04 2017 *)

a(n) = sumdiv(n, d, moebius(n/d) * 2^(d\2)); \\ Michel Marcus, Dec 09 2014

a(n) = Sum_{d | n} moebius(n/d)*2^(floor(d/2)) (see Baek et al. page 9). - Michel Marcus, Dec 09 2014
a(n) = 2*A000046(n) - A000048(n) = A000048(n) - 2*A308706(n) = A000046(n) - A308706(n). - Robert A. Russell, Jun 19 2019
A016116(n) =  Sum_{d|n} a(d). - Robert A. Russell, Jun 19 2019
G.f.: Sum_{k>=1} mu(k)*x^k*(1 + 2*x^k)/(1 - x^(2*k)). - Andrew Howroyd, Sep 27 2019

More terms from Michel Marcus, Dec 09 2014

A180653 'DP(n,k)' triangle read by rows. DP(n,k) is the number of k-double-palindromes of n.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 0, 4, 4, 4, 1, 0, 5, 3, 8, 4, 1, 0, 6, 6, 12, 12, 6, 1, 0, 7, 6, 17, 12, 19, 6, 1, 0, 8, 7, 24, 24, 20, 24, 8, 1, 0, 9, 8, 32, 21, 50, 24, 32, 8, 1, 0, 10, 10, 40, 40, 60, 60, 40, 40, 10, 1, 0, 11, 9, 49, 40, 100, 60, 98, 35, 51, 10, 1

Offset: 1

John P. McSorley, Sep 14 2010

A k-composition of n is an ordered collection of k positive integers (parts) which sum to n. A palindrome is a word which is the same when written backwards.
A k-double-palindrome of n is a k-composition of n which is the concatenation of two palindromes, PP'=P|P', where both |P|, |P'|>=1.
For example 1123532=11|23532 is a 7-double-palindrome of 17 since both 11 and 23532 are palindromes.
Let DP(n,k) denote the number of k-double-palindromes of n.
This sequence is the 'DP(n,k)' triangle read by rows.

			The triangle begins
  0
  0 1
  0 2 1
  0 3 2  1
  0 4 4  4  1
  0 5 3  8  4  1
  0 6 6 12 12  6  1
  0 7 6 17 12 19  6  1
  0 8 7 24 24 20 24  8 1
  0 9 8 32 21 50 24 32 8 1
  ...
For example, row 8 is: 0 7 6 17 12 19 6 1.
We have DP(8,3)=6 because there are 6 3-double-palindromes of 8: 116, 611, 224, 422, 233, and 332.
We have DP(8,4)=17 because there are 17 4-double-palindromes of 8: 1115, 5111, 1511, 1151, 1214, 4121, 1412, 2141, 1133, 3311, 1313, 3131, 1232, 2123, 3212, 2321, and 2222.

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

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

Row sums are A180750.
See sequence A051159 for the triangle whose (n, k) term gives the number of k-palindromes (single-palindromes) of n.
Cf. A179519, A180279, A180918, A181111, A181169.

\\ p(n,k) is k*A119963(n,k); q(n,k) is A051159(n-1, k-1).
p(n, k) = {k*binomial((n-k%2)\2, k\2)}
q(n, k) = {if(n%2==1&&k%2==0, 0, binomial((n-1)\2, (k-1)\2))}
invphi(n) = {sumdiv(n, d, d*moebius(d))}
T(n, k) = sumdiv(gcd(n, k), d, invphi(d) * p(n/d, k/d) - moebius(d) * q(n/d, k/d)); \\ Andrew Howroyd, Sep 27 2019

T(n,k) = A180279(n,k) - A179519(n,k). - Andrew Howroyd, Sep 27 2019

Terms a(56) and beyond from Andrew Howroyd, Sep 27 2019

A181111 'ADP(n,k)' triangle read by rows. ADP(n,k) is the number of aperiodic k-double-palindromes of n.

Original entry on oeis.org

0, 0, 0, 0, 2, 0, 0, 2, 2, 0, 0, 4, 4, 4, 0, 0, 4, 2, 6, 4, 0, 0, 6, 6, 12, 12, 6, 0, 0, 6, 6, 14, 12, 16, 6, 0, 0, 8, 6, 24, 24, 18, 24, 8, 0, 0, 8, 8, 28, 20, 44, 24, 28, 8, 0, 0, 10, 10, 40, 40, 60, 60, 40, 40, 10, 0, 0, 10, 8, 44, 40, 94, 60, 88, 32, 46, 10, 0

Offset: 1

John P. McSorley, Oct 03 2010

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, i.e., if it is not the concatenation of at least two smaller compositions.
A palindrome is a word which is the same when written backwards.
A k-double-palindrome of n is a k-composition of n which is the concatenation of two palindromes, PP'=P|P', where both |P|, |P'|>=1.
For example 1123532=11|23532 is a 7-double-palindrome of 17 since both 11 and 23532 are palindromes. It is also aperiodic, and so it is an aperiodic 7-double-palindrome of 17. The 4-double-palindrome of 8 1313=131|3 is not aperiodic, so it is not an aperiodic 4-double-palindrome of 8.
Let ADP(n,k) denote the number of aperiodic k-double-palindromes of n.
This sequence is the 'ADP(n,k)' triangle read by rows.

			The triangle begins:
  0
  0 0
  0 2 0
  0 2 2  0
  0 4 4  4  0
  0 4 2  6  4  0
  0 6 6 12 12  6  0
  0 6 6 14 12 16  6  0
  0 8 6 24 24 18 24  8 0
  0 8 8 28 20 44 24 28 8 0
  ...
For example, row 8 is: 0 6 6 14 12 16 6 0.
We have ADP(8,3)=6 because there are 6 aperiodic 3-double-palindromes of 8: 116, 611, 224, 422, 233, and 332.
We have ADP(8,4)=14 because there are 14 4-double-palindromes of 8: 1115, 5111, 1511, 1151, 1214, 4121, 1412, 2141, 1133, 3311, 1232, 2123, 3212, and 2321.

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

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

Row sums are A181135.
See sequence A180653 for the triangle whose (n, k) term gives the number of k-double-palindromes of n.
See sequence A179519 for the triangle whose (n, k) term gives the number of aperiodic k-palindromes (single-palindromes) of n.
Cf. A180279, A180918, A181169.

\\ here p(n,k) is A119963(n,k), q(n,k) is A051159(n-1, k-1).
p(n, k) = { binomial((n-k%2)\2, k\2) }
q(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) * (k*p(n/d, k/d) - q(n/d, k/d))); \\ Andrew Howroyd, Sep 27 2019

T(n,k) = A180279(n,k) - A179519(n,k). - Andrew Howroyd, Sep 27 2019

a(37) corrected and terms a(56) and beyond from Andrew Howroyd, Sep 27 2019

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

Original entry on oeis.org

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

Offset: 1

John P. McSorley, Jul 10 2010

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

			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.

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

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (Rows n=1..50 of triangle, flattened)

The row sums of the 'APE(n, k)' triangle give sequence A056513.

If cyclic equivalence is ignored, we get sequence A179519. - John P. McSorley, Jul 26 2010

T[n_, k_] := (3-(-1)^k)/4*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, Sep 24 2019 *)

\\ 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

APE(n,k) = (3-(-1)^k)/4 * A179519(n,k). - Andrew Howroyd, Oct 07 2017

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

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

Original entry on oeis.org

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

John P. McSorley, Jun 30 2010

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.

			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.

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

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

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.

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

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

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

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

cp's OEIS Frontend

A179781 a(n) = AP(n) is the total number of aperiodic k-palindromes of n, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A180653 'DP(n,k)' triangle read by rows. DP(n,k) is the number of k-double-palindromes of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A181111 'ADP(n,k)' triangle read by rows. ADP(n,k) is the number of aperiodic k-double-palindromes of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions