login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A284873 Array read by antidiagonals: T(n,k) = number of double palindromes of length n using a maximum of k different symbols. 8
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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)

LINKS

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

Chuan Guo, J. Shallit, 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.

FORMULA

T(n, k) = r(n, k) - Sum_{d|n, d<n} phi(n/d) * T(d, k) where r(2d, k) = d*(k+1)*k^d, r(2d+1, k) = (2d+1)*k^(d+1).

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)

EXAMPLE

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)

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[d<n, EulerPhi[n/d] a[d, k], 0], {d, Divisors[n]}]; Table[a[k, n - k + 1], {n, 20}, {k, n}] // Flatten (* Indranil Ghosh, Apr 07 2017 *)

PROG

(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<n, eulerphi(n/d)*a(d, k), 0));

for(n=1, 10, for(k=1, 10, print1( a(n, k), ", "); ); print(); );

(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 d<n])

for n in xrange(1, 21): print [a(k, n - k + 1) for k in xrange(1, n + 1)] # Indranil Ghosh, Apr 07 2017

CROSSREFS

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

Rows 3-4 are A000567, A187277.

Cf. A023900, A165137, A165135.

Sequence in context: A210219 A125103 A171275 * A107616 A055208 A051128

Adjacent sequences:  A284870 A284871 A284872 * A284874 A284875 A284876

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Apr 04 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 13 18:57 EDT 2019. Contains 327981 sequences. (Running on oeis4.)