A032121 Number of reversible strings with n beads of 4 colors.

1, 4, 10, 40, 136, 544, 2080, 8320, 32896, 131584, 524800, 2099200, 8390656, 33562624, 134225920, 536903680, 2147516416, 8590065664, 34359869440, 137439477760, 549756338176, 2199025352704, 8796095119360, 35184380477440, 140737496743936, 562949986975744

Offset: 0

Author

Christian G. Bower

Keywords

• nonn
• easy

Comments

Also the number of 4-ary strings of length m = n+1 with number of 1's, 2's and 3's all even. Bijective proof, anyone? - Frank Ruskey, Jul 14 2002

Examples

			a(2) = 10 = |{000, 110,101,011, 220,202,022, 330,303,033}|.
		

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Christian Barrientos, Sarah Minion, Series-Parallel Operations with Alpha-Graphs, Theory and Applications of Graphs (2019) Vol. 6, Issue 1, Article 4.
• C. G. Bower, Transforms (2)
• Index entries for linear recurrences with constant coefficients, signature (4,4,-16).

Crossrefs

Column 4 of A277504.

Cf. A000302 (oriented), A032087(n>1) (chiral), A056450 (achiral).

Programs

Mathematica

k = 4; Table[(k^n + k^Ceiling[n/2])/2, {n, 0, 30}] (* Robert A. Russell, Nov 25 2017 *)
LinearRecurrence[{4, 4, -16}, {1, 4, 10}, 31] (* Robert A. Russell, Nov 10 2018 *)
CoefficientList[Series[1/4 E^(-2 x) (-1 + 3 E^(4 x) + 2 E^(6 x)), {x, 0, 20}], x]*Table[n!, {n, 0, 20}] (* Stefano Spezia, Nov 12 2018 *)

PARI

Vec((1-10*x^2) / ((1 - 2*x)*(1 + 2*x)*(1 - 4*x)) + O(x^40)) \\ Colin Barker, Nov 25 2017

Formula

"BIK" (reversible, indistinct, unlabeled) transform of 4, 0, 0, 0, ...

a(n) = (4^m+3*2^m+(-2)^m)/8, where m = n+1. - Frank Ruskey, Jul 14 2002

G.f.: (1-10x^2) / ((1-4x)*(1-4x^2)). - Maksym Voznyy (voznyy(AT)mail.ru), Jul 27 2009; corrected by R. J. Mathar, Sep 16 2009 [Adapted to offset 0 by Robert A. Russell, Nov 10 2018]

From Colin Barker, Nov 25 2017: (Start)

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

a(n) = 4*a(n-1) + 4*a(n-2) - 16*a(n-3) for n>2.

(End)

a(n) = (4^n + 4^floor((n+1)/2)) / 2 = (A000302(n) + A056450(n)) / 2. - Robert A. Russell and Danny Rorabaugh, Jun 22 2018

E.g.f.: (1/4)*exp(-2*x)*(- 1 + 3*exp(4*x) + 2*exp(6*x)). - Stefano Spezia, Nov 12 2018

Extensions

a(0) = 1 prepended by Robert A. Russell, Nov 10 2018