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

Author

Marks R. Nester

Keywords

• nonn
• easy

Comments

A string and its reverse are considered to be equivalent.

Examples

			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
		

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).

Crossrefs

Cf. A000079, A005418.

Equals (A000918 + A056453) / 2.

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

Programs

Magma

[2^(n-1)+2^((n-1) div 2)-2: n in [1..40]]; // Vincenzo Librandi, Sep 29 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 *)

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

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