|
| |
|
|
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
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.
(End)
|
|
|
LINKS
|
|
|
|
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).
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)
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)
|
|
|
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 ...
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 range(1, 21): print([a(k, n - k + 1) for k in range(1, n + 1)]) # Indranil Ghosh, Apr 07 2017
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
