A187277 Let S denote the palindromes in the language {0,1,2,...,n-1}*; a(n) = number of words of length 4 in the language SS.

1, 16, 57, 136, 265, 456, 721, 1072, 1521, 2080, 2761, 3576, 4537, 5656, 6945, 8416, 10081, 11952, 14041, 16360, 18921, 21736, 24817, 28176, 31825, 35776, 40041, 44632, 49561, 54840, 60481, 66496, 72897, 79696, 86905, 94536, 102601, 111112, 120081, 129520, 139441, 149856, 160777, 172216, 184185

Offset: 1

Author

N. J. A. Sloane, Mar 07 2011

Keywords

• nonn

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234. See Table 1.

Crossrefs

Row 4 of A284873.

Programs

Magma

[2*n^3 + n^2 - 2*n: n in [1..50]]; // G. C. Greubel, Jul 25 2018

Maple

Using the Maple code from A007055: [seq(F(b,4),b=1..50)];

Mathematica

Array[# (2 #^2 + # - 2) &, 45] (* or *)
Rest@ CoefficientList[Series[-x (x^2 - 12 x - 1)/(x - 1)^4, {x, 0, 45}], x] (* Michael De Vlieger, Oct 10 2017 *)

PARI

a(n) = 2*n^3 + n^2 - 2*n; \\ Andrew Howroyd, Oct 10 2017

Python

def A187277(n): return n*(n*((n<<1)|1)-2) # Chai Wah Wu, Feb 19 2024

Formula

From Colin Barker, Jul 24 2013: (Start) (Conjectured formulas; later proven)

a(n) = n*(2*n^2 +n -2).

G.f.: x*(1 +12*x - x^2)/(x-1)^4. (End)

The above conjecture is true: A284873(4, n) evaluates to the same polynomial. - Andrew Howroyd, Oct 10 2017