A284873 Array read by antidiagonals: T(n,k) = number of double palindromes of length n using a maximum of k different symbols.

1, 2, 1, 3, 4, 1, 4, 9, 8, 1, 5, 16, 21, 16, 1, 6, 25, 40, 57, 32, 1, 7, 36, 65, 136, 123, 52, 1, 8, 49, 96, 265, 304, 279, 100, 1, 9, 64, 133, 456, 605, 880, 549, 160, 1, 10, 81, 176, 721, 1056, 2125, 1768, 1209, 260, 1, 11, 100, 225, 1072, 1687, 4356, 4345, 4936, 2127, 424, 1

Offset: 1

Author

Andrew Howroyd, Apr 04 2017

Keywords

• nonn
• tabl

Comments

A double palindrome is a concatenation of two palindromes.

Also, number of words of length n using a maximum of k different symbols that are rotations of their reversals.

The sequence A165135 (number of n-digit positive papaya numbers) is 9/10 of the value of column 10.

All rows are polynomials of degree 1 + floor(n/2). - Andrew Howroyd, Oct 10 2017

From Petros Hadjicostas, Oct 27 2017: (Start)

Following Kemp (1982), we note that the formula by A. Howroyd below is equivalent to r(n,k) = Sum_{d|n} phi(d)*T(n/d,k), where r(2d, k) = d*(k+1)*k^d and r(2d+1, k) = (2d+1)*k^(d+1). Inverting (according to the theory of Dirichlet convolutions) we get T(n,k) = Sum_{d|n} phi^{(-1)}(d)*r(n/d,k), where phi^{(-1)}(n) = A023900(n) is the Dirichlet inverse of Euler's totient function.

We can easily prove that Sum_{n>=1} r(n,k)*x^n = R(k,x) = k*x*(x+1)*(k*x+1)/(1-k*x^2)^2 (for each k>=1). We also have Sum_{n>=1} T(n,k)*x^n = Sum_{n>=1} Sum_{d|n} phi^{(-1)}(d)*r(n/d,k)*x^n. Letting m = n/d and noting that x^n = (x^d)^m, we can easily get the g.f. given in the formula section.

Note that r(n,1) = n, r(n,2) = A187272(n), r(n,3) = A187273(n), r(n,4) = A187274(n), and r(n,5) = A187275(n).

(End)

Examples

			Table starts:
  1   2    3     4     5      6      7       8       9      10 ...
  1   4    9    16    25     36     49      64      81     100 ...
  1   8   21    40    65     96    133     176     225     280 ...
  1  16   57   136   265    456    721    1072    1521    2080 ...
  1  32  123   304   605   1056   1687    2528    3609    4960 ...
  1  52  279   880  2125   4356   7987   13504   21465   32500 ...
  1 100  549  1768  4345   9036  16765   28624   45873   69940 ...
  1 160 1209  4936 14665  35736  75985  146224  260721  437680 ...
  1 260 2127  9112 27965  69756 150955  294512  530937  899380 ...
  1 424 4689 25216 93025 270936 670369 1471744 2948481 5494600 ...
From _Petros Hadjicostas_, Oct 27 2017: (Start)
We explain how to use the above formulae to find general expressions for some rows.
If p is an odd prime, then phi^{(-1)}(p) = 1-p. Since, also, phi^{(-1)}(1) = 1, we get T(p,k) = (1-p)*k+p*k^{(p+1)/2} for the p-th row above.
If m is a positive integer, then phi^{(-1)}(2^m) = -1, and so T(2^m,k) = 1+(k+1)*(2^{m-1}*k^{2^{m-1}}-1-Sum_{0<=s<=m-2} 2^s*k^{2^s}).
For example, if m=1, then T(2,k) = 1+(k+1)*(1*k-1-0) = k^2.
If m=2, then T(4,k) = 1+(k+1)*(2*k^2-1-k) = k*(2*k^2+k-2), which is the formula conjectured by C. Barker for sequence A187277 and verified by A. Howroyd.
(End)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275
• Chuan Guo, J. Shallit, and A. M. Shur, On the Combinatorics of Palindromes and Antipalindromes, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.
• R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234.

Crossrefs

Columns 2-5 are A007055, A007056, A007057, A007058.

Rows 3-4 are A000567, A187277.

Cf. A023900, A165137, A165135.

Programs

Mathematica

r[d_, k_]:=If[OddQ[d], d*k^((d + 1)/2), (d/2)*(k + 1)*k^(d/2)]; a[n_, k_]:= r[n, k] - Sum[If[dIndranil Ghosh, Apr 07 2017 *)

PARI

r(d,k)=if (d % 2 == 0, (d/2)*(k+1)*k^(d/2), d*k^((d+1)/2));
a(n,k) = r(n,k) - sumdiv(n,d, if (d
				

Python

from sympy import totient, divisors
def r(d, k): return (d//2)*(k + 1)*k**(d//2) if d%2 == 0 else d*k**((d + 1)//2)
def a(n, k): return r(n, k) - sum([totient(n//d)*a(d, k) for d in divisors(n) if dIndranil Ghosh, Apr 07 2017

Formula

T(n, k) = r(n, k) - Sum_{d|n, d

From Petros Hadjicostas, Oct 27 2017: (Start)

T(n,k) = Sum_{d|n} phi^{(-1)}(d)*r(n/d,k), where r(n,k) is given above and phi^{(-1)}(n) = A023900(n) is the Dirichlet inverse of Euler's totient function.

G.f.: For each k>=1, Sum_{n>=1} T(n,k)*x^n = Sum_{d>=1} phi^{(-1)}(d)*R(k,x^d), where R(k,x) = k*x*(x+1)*(k*x+1)/(1-k*x^2)^2.

(End)

From Richard L. Ollerton, May 07 2021: (Start)

T(n,k) = Sum_{i=1..n} phi^{(-1)}(n/gcd(n,i))*r(gcd(n,i),k)/phi(n/gcd(n,i)).

T(n,k) = Sum_{i=1..n} phi^{(-1)}(gcd(n,i))*r(n/gcd(n,i),k)/phi(n/gcd(n,i)).

r(n,k) = Sum_{i=1..n} T(gcd(n,i),k). (End)

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.