|
%I #50 May 08 2021 07:46:02
%S 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,
%T 1,8,49,96,265,304,279,100,1,9,64,133,456,605,880,549,160,1,10,81,176,
%U 721,1056,2125,1768,1209,260,1,11,100,225,1072,1687,4356,4345,4936,2127,424,1
%N Array read by antidiagonals: T(n,k) = number of double palindromes of length n using a maximum of k different symbols.
%C A double palindrome is a concatenation of two palindromes.
%C Also, number of words of length n using a maximum of k different symbols that are rotations of their reversals.
%C The sequence A165135 (number of n-digit positive papaya numbers) is 9/10 of the value of column 10.
%C All rows are polynomials of degree 1 + floor(n/2). - _Andrew Howroyd_, Oct 10 2017
%C From _Petros Hadjicostas_, Oct 27 2017: (Start)
%C 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.
%C 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.
%C 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).
%C (End)
%H Andrew Howroyd, <a href="/A284873/b284873.txt">Table of n, a(n) for n = 1..1275</a>
%H Chuan Guo, J. Shallit, and A. M. Shur, <a href="http://arxiv.org/abs/1503.09112">On the Combinatorics of Palindromes and Antipalindromes</a>, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.
%H R. Kemp, <a href="http://dx.doi.org/10.1016/0012-365X(82)90123-6">On the number of words in the language {w in Sigma* | w = w^R }^2</a>, Discrete Math., 40 (1982), 225-234.
%F 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).
%F From _Petros Hadjicostas_, Oct 27 2017: (Start)
%F 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.
%F 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.
%F (End)
%F From _Richard L. Ollerton_, May 07 2021: (Start)
%F T(n,k) = Sum_{i=1..n} phi^{(-1)}(n/gcd(n,i))*r(gcd(n,i),k)/phi(n/gcd(n,i)).
%F T(n,k) = Sum_{i=1..n} phi^{(-1)}(gcd(n,i))*r(n/gcd(n,i),k)/phi(n/gcd(n,i)).
%F r(n,k) = Sum_{i=1..n} T(gcd(n,i),k). (End)
%e Table starts:
%e 1 2 3 4 5 6 7 8 9 10 ...
%e 1 4 9 16 25 36 49 64 81 100 ...
%e 1 8 21 40 65 96 133 176 225 280 ...
%e 1 16 57 136 265 456 721 1072 1521 2080 ...
%e 1 32 123 304 605 1056 1687 2528 3609 4960 ...
%e 1 52 279 880 2125 4356 7987 13504 21465 32500 ...
%e 1 100 549 1768 4345 9036 16765 28624 45873 69940 ...
%e 1 160 1209 4936 14665 35736 75985 146224 260721 437680 ...
%e 1 260 2127 9112 27965 69756 150955 294512 530937 899380 ...
%e 1 424 4689 25216 93025 270936 670369 1471744 2948481 5494600 ...
%e From _Petros Hadjicostas_, Oct 27 2017: (Start)
%e We explain how to use the above formulae to find general expressions for some rows.
%e 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.
%e 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}).
%e For example, if m=1, then T(2,k) = 1+(k+1)*(1*k-1-0) = k^2.
%e 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.
%e (End)
%t 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 *)
%o (PARI)
%o r(d,k)=if (d % 2 == 0, (d/2)*(k+1)*k^(d/2), d*k^((d+1)/2));
%o a(n,k) = r(n,k) - sumdiv(n,d, if (d<n, eulerphi(n/d)*a(d,k), 0));
%o for(n=1, 10, for(k=1, 10, print1( a(n,k),", ");); print(););
%o (Python)
%o from sympy import totient, divisors
%o def r(d, k): return (d//2)*(k + 1)*k**(d//2) if d%2 == 0 else d*k**((d + 1)//2)
%o def a(n, k): return r(n, k) - sum([totient(n//d)*a(d, k) for d in divisors(n) if d<n])
%o for n in range(1, 21): print([a(k, n - k + 1) for k in range(1, n + 1)]) # _Indranil Ghosh_, Apr 07 2017
%Y Columns 2-5 are A007055, A007056, A007057, A007058.
%Y Rows 3-4 are A000567, A187277.
%Y Cf. A023900, A165137, A165135.
%K nonn,tabl
%O 1,2
%A _Andrew Howroyd_, Apr 04 2017
|
