A056309 Number of reversible strings with n beads using exactly two different colors.

0, 1, 4, 8, 18, 34, 70, 134, 270, 526, 1054, 2078, 4158, 8254, 16510, 32894, 65790, 131326, 262654, 524798, 1049598, 2098174, 4196350, 8390654, 16781310, 33558526, 67117054, 134225918, 268451838, 536887294, 1073774590, 2147516414, 4295032830, 8590000126

Offset

1,3

Comments

A string and its reverse are considered to be equivalent.

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]

Links

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (3,0,-6,4).

Formula

a(n) = A005418(n+1) - 2.

G.f.: x^2*(1 + x - 4*x^2)/(1 - 3*x + 6*x^3 - 4*x^4). - Colin Barker, Feb 03 2012

a(1)=0, a(2)=1, a(3)=4, a(4)=8, a(n) = 3*a(n-1) - 6*a(n-3) + 4*a(n-4). - Harvey P. Dale, Feb 18 2012

From Colin Barker, Nov 24 2017: (Start)

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

a(n) = 2^((n-1)/2) + 2^(n-1) - 2 for n odd. (End)

a(n) = A000079(n-1) + A056453(n-2). - Peter Luschny, Nov 25 2017

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

Example

For n=3, the four rows are ABA, BAB, AAB, and ABB, the last two being respectively equivalent to BAA and BBA, with which they form chiral pairs. - Robert A. Russell, Sep 25 2018

Maple

seq(2^(n-1) + 2^floor((n-1)/2) - 2, n=1..34); # Peter Luschny, Nov 25 2017

Mathematica

Rest[CoefficientList[Series[x^2(1+x-4x^2)/(1-3x+6x^3-4x^4), {x, 0, 30}], x]] (* or *) LinearRecurrence[{3, 0, -6, 4}, {0, 1, 4, 8}, 30] (* Harvey P. Dale, Feb 18 2012 *)

Prog

(PARI) Vec(x^2*(1+x-4*x^2)/(1-3*x+6*x^3-4*x^4) + O(x^40)) \\ Colin Barker, Nov 24 2017
(PARI) a(n) = 2^(n-1)+2^((n-1)\2)-2; \\ Altug Alkan, Sep 25 2018
(Magma) [2^(n-1)+2^((n-1) div 2)-2: n in [1..40]]; // Vincenzo Librandi, Sep 29 2018

Crossrefs

Cf. A000079, A005418.

Equals (A000918 + A056453) / 2.

a(n) = A000918(n) - A122746(n-2) = A122746(n-2) + A056453(n).

Sequence in context: A201686 A008240 A008375 * A007784 A008204 A190062

Adjacent sequences: A056306 A056307 A056308 * A056310 A056311 A056312

Keyword

nonn,easy

Author

Marks R. Nester

Status

approved