A056453 Number of palindromes of length n using exactly two different symbols.

0, 0, 2, 2, 6, 6, 14, 14, 30, 30, 62, 62, 126, 126, 254, 254, 510, 510, 1022, 1022, 2046, 2046, 4094, 4094, 8190, 8190, 16382, 16382, 32766, 32766, 65534, 65534, 131070, 131070, 262142, 262142, 524286, 524286, 1048574, 1048574, 2097150, 2097150, 4194302

Offset: 1

Author

Marks R. Nester

Keywords

• nonn
• easy

Comments

Also the number of bitstrings of length n+2 where the last two runs have the same length. (A run is a maximal subsequence of (possibly just one) identical bits.) - David Nacin, Mar 03 2012

Also, the decimal representation of the diagonal from the corner to the origin of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 62", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. - Robert Price, Apr 22 2017

Examples

			The palindromes in two symbols of length three take the forms 000, 111, 010, 101. Of these only two have exactly two symbols.  Thus a(3) = 2. - _David Nacin_, Mar 03 2012
		

References

• M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
• S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..2000
• Aruna Gabhe, Problem 11623, Am. Math. Monthly 119 (2012) 161.
• N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015
• Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
• S. Wolfram, A New Kind of Science
• Wolfram Research, Wolfram Atlas of Simple Programs
• Index entries for sequences related to cellular automata
• Index to 2D 5-Neighbor Cellular Automata
• Index to Elementary Cellular Automata
• Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Crossrefs

Cf. A000918, A016116, A056391, A208900, A208901, A208902, A208903.

Programs

Magma

[2^Floor((n+1)/2)-2: n in [1..40]]; // Vincenzo Librandi, Aug 16 2011

Mathematica

Table[2^(Floor[n/2] + 1) - 2, {n, 0, 40}] (* David Nacin, Mar 03 2012 *)
LinearRecurrence[{1, 2, -2}, {0, 0, 2}, 40] (* David Nacin, Mar 03 2012 *)
k=2; Table[k! StirlingS2[Ceiling[n/2],k],{n,1,30}] (* Robert A. Russell, Sep 25 2018 *)

PARI

a(n) = 2^((n+1)\2)-2; \\ Altug Alkan, Sep 25 2018

Python

def A056453(n): return (1<<(n+1>>1))-2 # Chai Wah Wu, Feb 18 2024

Formula

a(n) = 2^floor((n+1)/2) - 2.

a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3). - David Nacin, Mar 03 2012

G.f.: 2*x^3/((1-x)*(1-2*x^2)). - David Nacin, Mar 03 2012

G.f.: k!(x^(2k-1)+x^(2k))/Product_{i=1..k}(1-ix^2), where k=2 is the number of symbols. - Robert A. Russell, Sep 25 2018

a(n) = k! S2(ceiling(n/2),k), where k=2 is the number of symbols and S2 is the Stirling subset number. - Robert A. Russell, Sep 25 2018

E.g.f.: 1 - 2*cosh(x) + cosh(sqrt(2)*x) - 2*sinh(x) + sqrt(2)*sinh(sqrt(2)*x). - Stefano Spezia, Jun 06 2023

Extensions

More terms from Vincenzo Librandi, Aug 16 2011

Name clarified by Michel Marcus and Felix Fröhlich, Jul 09 2018