A180279 -id:A180279 - cp's OEIS frontend

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

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

A180171 Triangle read by rows: R(n,k) is the number of k-reverses of n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 4, 10, 5, 1, 1, 6, 9, 12, 15, 6, 1, 1, 7, 9, 19, 15, 21, 7, 1, 1, 8, 10, 24, 30, 20, 28, 8, 1, 1, 9, 12, 36, 26, 54, 28, 36, 9, 1, 1, 10, 15, 40, 50, 60, 70, 40, 45, 10, 1, 1, 11, 13, 53, 50, 108, 70, 106, 39, 55, 11, 1, 1, 12, 18, 60, 75, 120

Offset: 1

John P. McSorley, Aug 15 2010

A k-composition of n is an ordered collection of k positive integers (parts) which sum to n.
Two k-compositions are cyclically equivalent if one can be obtained from the other by a cyclic permutation of its parts.
The reverse of a k-composition is the k-composition obtained by writing its parts in reverse.
For example the reverse of 123 is 321.
A k-reverse of n is a k-composition of n which is cyclically equivalent to its reverse.
For example 114 is a 3-reverse of 6 since its set of cyclic equivalents {114,411,141} contains its reverse 411. But 123 is not a 3-reverse of 6 since its set of cyclic equivalents {123,312,231} does not contain its reverse 321.

			The triangle begins
  1
  1 1
  1 2 1
  1 3 3 1
  1 4 6 4 1
  1 5 4 10 5 1
  1 6 9 12 15 6 1
  1 7 9 19 15 21 7 1
  1 8 10 24 30 20 28 8 1
  1 9 12 36 26 54 28 36 9 1
For example row 8 is 1 7 9 19 15 21 7 1
We have R(8,3)=9 because there are 9 3-reverses of 8. In classes: {116,611,161} {224,422,242}, and {233,323,332}.
We have R(8,6)=21 because all 21 6-compositions of 8 are 6-reverses of 8.

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

Robert G. Wilson v, Table of n, a(n) for n = 1..500.
Petros Hadjicostas, Proofs of two formulae on the number of k-inverses of n

Row sums are A180249.

Cf. A023900, A119963, A180279.

f[n_Integer, k_Integer] := Block[{c = 0, j = 1, ip = IntegerPartitions[n, {k}]}, lmt = 1 + Length@ ip; While[j < lmt, c += g[ ip[[j]]]; j++ ]; c]; g[lst_List] := Block[{c = 0, len = Length@ lst, per = Permutations@ lst}, While[ Length@ per > 0, rl = Union[ RotateLeft[ per[[1]], # ] & /@ Range@ len]; If[ MemberQ[rl, Reverse@ per[[1]]], c += Length@ rl]; per = Complement[ per, rl]]; c]; Table[ f[n, k], {n, 13}, {k, n}] // Flatten (* Robert G. Wilson v, Aug 25 2010 *)

\\ here p(n,k) is A119963, AR(n,k) is A180279.
p(n,k) = binomial((n-k%2)\2, k\2);
AR(n,k) = k*sumdiv(gcd(n,k), d, moebius(d) * p(n/d, k/d));
T(n,k) = sumdiv(gcd(n,k), d, AR(n/d,k/d));
for(n=1, 10, for(k=1, n, print1(T(n,k), ", ")); print) \\ Andrew Howroyd, Oct 08 2017

R(n,k) = Sum_{d|gcd(n,k)} A180279(n/d, k/d). - Andrew Howroyd, Oct 08 2017
From Petros Hadjicostas, Oct 21 2017: (Start)
For proofs of these formulae, see the links.
R(n,k) = Sum_{d|gcd(n,k)} phi^{(-1)}(d)*(k/d)*A119963(n/d, k/d), where phi^{(-1)}(d) = A023900(d) is the Dirichlet inverse function of Euler's totient function.
G.f.: Sum_{s >= 1} phi^{(-1)}(s)*g(x^s, y^s), where phi^{(-1)}(s) = A023900(s) and g(x,y) = (x*y+x+1)*(x*y-x+1)*(x+1)*x*y/(x^2*y^2+x^2-1)^2.
(End)

a(56) onwards from Robert G. Wilson v, Aug 25 2010

A180322 a(n) = AR(n) is the total number of aperiodic k-reverses of n.

Original entry on oeis.org

1, 1, 3, 6, 15, 21, 49, 72, 126, 195, 341, 486, 819, 1225, 1845, 2880, 4335, 6552, 9709, 14850, 21315, 33077, 47081, 72360, 102300, 158067, 220752, 341334, 475107, 732735, 1015777, 1566720, 2161599, 3333615, 4587135, 7062552, 9699291, 14922733, 20444697

Offset: 1

John P. McSorley, Aug 27 2010

nonn

The n-th term of this sequence a(n) = AR(n) gives the total number of aperiodic k-reverses of n for k=1,2,...,n. It is the sum of the n-th row of the 'AR(n,k)' triangle from sequence A180279.
See sequence A180279 for the definition of an aperiodic k-reverse of n.
Briefly, a k-reverse of n is a k-composition of n whose reverse is cyclically equivalent to itself, and an aperiodic k-reverse of n is a k-reverse of n which is also aperiodic.
For example a(6)=21 because there are 21 aperiodic k-reverses of n=6 for k=1,2,3,4,5, or 6.
They are, in cyclically equivalent classes: {6}, {15,51}, {24,42}, {114,411,141}, {1113,3111,1311,1131}, {1122,2112,2211,1221},{11112,21111,12111,11211,11121}.

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

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

If we ask for the number of cyclically equivalent classes we get sequence A056493 (except for the first term). For example, the 6th term of A056493 is 7, corresponding to the 7 classes in the example above.

Row sums of A180279.

a[n_] := n*Sum[MoebiusMu[n/d]*If[OddQ[d], 2, 3]*2^Quotient[d-1, 2], {d, Divisors[n]}]/2;
Array[a, 40] (* Jean-François Alcover, Jul 06 2018, after Andrew Howroyd *)

a(n) = n * sumdiv(n, d, moebius(n/d) * if(d%2,2,3) * 2^((d-1)\2)) / 2; \\ Andrew Howroyd, Oct 07 2017

a(n) = n * A056493(n) / 2. - Andrew Howroyd, Oct 07 2017

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

A180424 "ARE(n,k)" triangle read by rows. ARE(n,k) is the number of aperiodic k-reverses of n up to cyclic equivalence.

Original entry on oeis.org

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

Offset: 1

John P. McSorley, Sep 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, or if it is not the concatenation of at least two smaller compositions.
Two k-compositions are cyclically equivalent if one can be obtained from the other by a cyclic permutation of its parts.
The reverse of a k-composition is the k-composition obtained by writing its parts in reverse. For example, the reverse of 123 is 321.
A k-reverse of n is a k-composition of n which is cyclically equivalent to its reverse. And an aperiodic k-reverse of n is a k-reverse of n which is aperiodic.
For example, 114 is an aperiodic 3-reverse of 6 since it is aperiodic and its set of cyclic equivalents {114,411,141} contains its reverse 411.
But 123 is not an aperiodic 3-reverse of 6 since, even though it is aperiodic, its set of cyclic equivalents {123,312,231} does not contain its reverse 321.
Let AR(n,k) denote the number of aperiodic k-reverses of n, then sequence A180279 is the 'AR(n,k)' triangle read by rows.
For the above sequence we count the aperiodic k-reverses of n up to cyclic equivalence, ARE(n,k), in other words, the number of equivalence classes under cyclic permutation which contain at least one aperiodic k-reverse of n.

			The triangle begins
  1
  1 0
  1 1 0
  1 1 1 0
  1 2 2 1 0
  1 2 1 2 1 0
  1 3 3 3 3 1 0
  1 3 3 4 3 3 1 0
  1 4 3 6 6 3 4 1 0
  1 4 4 8 5 8 4 4 1 0
For example, row 8 is 1 3 3 4 3 3 1 0.
We have ARE(8,3)=3 because there are 9 aperiodic 3-reverses of 8 in the 3 classes {116,611,161}, {224,422,242}, and {233,323,332}, and so there are ARE(8,3)=3 aperiodic 3-reverses of 8 up to cyclic equivalence.
We have ARE(8,6)=3 because there are 3 aperiodic 6-reverses of 8 up to cyclic equivalence. The representatives of the 3 classes are 111113, 111122, and 111212.

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

As mentioned above, if we don't count the classes, but rather the elements in the classes, we get sequence A180279.
If we remove the aperiodic requirement, see sequence A119963.
The row sums of the "ARE(n, k)" triangle above give sequence A056493 (except for the first term). See also sequence A056498.

Table[DivisorSum[GCD[n, k], MoebiusMu[#]*Binomial[Floor[((n/#) - Boole[OddQ[k/#]])/2], Floor[k/(2 #)]] &], {n, 12}, {k, n}] // Flatten (* Michael De Vlieger, Oct 31 2021 *)

\\ here RE(n,k) is A119963(n,k).
RE(n,k) = binomial((n-k%2)\2, k\2);
T(n,k) = sumdiv(gcd(n,k), d, moebius(d)*RE(n/d,k/d));
for(n=1, 10, for(k=1, n, print1(T(n,k), ", ")); print) \\ Andrew Howroyd, Oct 07 2017

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

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

cp's OEIS Frontend

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

A180171 Triangle read by rows: R(n,k) is the number of k-reverses of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A180322 a(n) = AR(n) is the total number of aperiodic k-reverses of n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A180424 "ARE(n,k)" triangle read by rows. ARE(n,k) is the number of aperiodic k-reverses of n up to cyclic equivalence.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions