

A001998


Bending a piece of wire of length n+1; walks of length n+1 on a tetrahedron; also nonbranched catafusenes with n+2 condensed hexagons.
(Formerly M1211 N0468)


26



1, 2, 4, 10, 25, 70, 196, 574, 1681, 5002, 14884, 44530, 133225, 399310, 1196836, 3589414, 10764961, 32291602, 96864964, 290585050, 871725625, 2615147350, 7845353476, 23535971854, 70607649841, 211822683802, 635467254244, 1906400965570, 5719200505225, 17157599124190
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

The wire stays in the plane, there are n bends, each is R,L or O; turning the wire over does not count as a new figure.
Equivalently, walks of n+1 steps on a tetrahedron, visiting n+2 vertices, with n "corners"; the symmetry group is S4, reversing a walk does not count as different. Simply interpret R,L,O as instructions to turn R, turn L, or retrace the last step. Walks are not selfavoiding.
Also, it appears that a(n) gives the number of equivalence classes of ntuples of 0, 1 and 2, where two ntuples are equivalent if one can be obtained from the other by a sequence of operations R and C, where R denotes reversal and C denotes taking the 2's complement (C(x)=2x). This has been verified up to a(19)=290585050. Example: for n=3 there are ten equivalence classes {000, 222}, {001, 100, 122, 221}, {002, 022, 200, 220}, {010, 212}, {011, 110, 112, 211}, {012, 210}, {020, 202}, {021, 102, 120, 201}, {101, 121}, {111}, so a(3)=10.  John W. Layman, Oct 13 2009
There exists a bijection between chains of n+2 hexagons and the above described equivalence classes of ntuples of 0,1, and 2. Namely, for a given chain of n+2 hexagons we take the sequence of the numbers of vertices of degree 2 (0, 1, or 2) between the consecutive contact vertices on one side of the chain; switching to the other side we obtain the 2's complement of this sequence; reversing the order of the hexagons, we obtain the reverse sequence. The inverse mapping is straightforward. For example, to a linear chain of 7 hexagons there corresponds the 5tuple 11111.  Emeric Deutsch, Apr 22 2013
If we treat two wire bends (or walks, or tuples) related by turning over (or reversing) as different in any of the abovegiven interpretations of this sequence, we get A007051 (or A124302). Also, a(n1) is the sum of first 3 terms in nth row of A284949, see crossrefs therein.  Andrey Zabolotskiy, Sep 29 2017
a(n1) is the number of color patterns (set partitions) in an unoriented row of length n using 3 or fewer colors (subsets).  Robert A. Russell, Oct 28 2018
a(n) is the number of (unlabeled) 3paths with n+6 vertices. (A 3path with order n at least 5 can be constructed from a 4clique by iteratively adding a new 3leaf (vertex of degree 3) adjacent to an existing 3clique containing an existing 3leaf.)
Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)


REFERENCES

A. T. Balaban, Enumeration of Cyclic Graphs, pp. 63105 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976; see p. 75.
S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Enumeration of treelike octagonal systems: catapolyoctagons, ACH Models in Chem. 134 (1997), 5570.
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.]
R. C. Read, The Enumeration of Acyclic Chemical Compounds, pp. 2561 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976. [I think this reference does not mention this sequence.  N. J. A. Sloane, Aug 10 2006]
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

F. Harary and R. W. Robinson, Tapeworms, Unpublished manuscript, circa 1973. (Annotated scanned copy)


FORMULA

a(n) = if n mod 2 = 0 then ((3^((n2)/2)+1)/2)^2 else 3^((n3)/2)+(1/4)*(3^(n2)+1).
G.f.: (12*x4*x^2+6*x^3) / ((1x)*(13*x)*(13*x^2)).  Corrected by Colin Barker, May 15 2016
a(n) = 4*a(n1)12*a(n3)+9*a(n4), with a(0)=1, a(1)=2, a(2)=4, a(3)=10.  Harvey P. Dale, Apr 10 2013
a(n) = (1+3^n+3^(1/2*(1+n))*(22*(1)^n+sqrt(3)+(1)^n*sqrt(3)))/4.  Colin Barker, May 15 2016
E.g.f.: (2*sqrt(3)*sinh(sqrt(3)*x) + 3*exp(2*x)*cosh(x) + 3*cosh(sqrt(3)*x))/6.  Ilya Gutkovskiy, May 15 2016
a(n1) = Sum_{j=1..k} (S2(n,j) + Ach(n,j)) / 2, where k=3 is the maximum number of colors, S2 is the Stirling subset number A008277, and Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n2,k) + Ach(n2,k1) + Ach(n2,k2)).


EXAMPLE

There are 2 ways to bend a piece of wire of length 2 (bend it or not).
For n=4 and a(n1)=10, the 6 achiral patterns are AAAA, AABB, ABAB, ABBA, ABCA, and ABBC. The 4 chiral pairs are AAABABBB, AABAABAA, AABCABCC, and ABACABCB.  Robert A. Russell, Oct 28 2018


MAPLE

A001998 := proc(n) if n = 0 then 1 elif n mod 2 = 1 then (1/4)*(3^n+4*3^((n1)/2)+1) else (1/4)*(3^n+2*3^(n/2)+1); fi; end;
A001998:=(1+3*z+2*z**28*z**3+3*z**4)/(z1)/(3*z1)/(3*z**21); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence with an extra leading 1


MATHEMATICA

a[n_?OddQ] := (1/4)*(3^n + 4*3^((n  1)/2) + 1); a[n_?EvenQ] := (1/4)*(3^n + 2*3^(n/2) + 1); Table[a[n], {n, 0, 27}] (* JeanFrançois Alcover, Jan 25 2013, from formula *)
LinearRecurrence[{4, 0, 12, 9}, {1, 2, 4, 10}, 30] (* Harvey P. Dale, Apr 10 2013 *)
Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n2, k] + Ach[n2, k1] + Ach[n2, k2]] (* A304972 *)
k=3; Table[Sum[StirlingS2[n, j]+Ach[n, j], {j, k}]/2, {n, 40}] (* Robert A. Russell, Oct 28 2018 *)


PROG

(PARI) Vec((12*x4*x^2+6*x^3)/((1x)*(13*x)*(13*x^2)) + O(x^50)) \\ Colin Barker, May 15 2016
(GAP) a:=[];; for n in [2..45] do if n mod 2 =0 then Add(a, ((3^((n2)/2)+1)/2)^2); else Add(a, 3^((n3)/2)+(1/4)*(3^(n2)+1)); fi; od; a; # Muniru A Asiru, Oct 28 2018


CROSSREFS

Column 3 of A320750, offset by one. Column k = 0 of A323942, offset by two.
The sequences above converge to A103293(n+1).


KEYWORD

nonn,nice,easy


AUTHOR



EXTENSIONS



STATUS

approved



