login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001998 Bending a piece of wire of length n+1; walks of length n+1 on a tetrahedron; also non-branched catafusenes with n+2 condensed hexagons.
(Formerly M1211 N0468)
20

%I M1211 N0468

%S 1,2,4,10,25,70,196,574,1681,5002,14884,44530,133225,399310,1196836,

%T 3589414,10764961,32291602,96864964,290585050,871725625,2615147350,

%U 7845353476,23535971854,70607649841,211822683802,635467254244,1906400965570,5719200505225,17157599124190

%N Bending a piece of wire of length n+1; walks of length n+1 on a tetrahedron; also non-branched catafusenes with n+2 condensed hexagons.

%C 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.

%C 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 self-avoiding.

%C Also, it appears that a(n) gives the number of equivalence classes of n-tuples of 0, 1 and 2, where two n-tuples 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)=2-x). 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

%C There exists a bijection between chains of n+2 hexagons and the above described equivalence classes of n-tuples 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 5-tuple 11111. - _Emeric Deutsch_, Apr 22 2013

%C If we treat two wire bends (or walks, or tuples) related by turning over (or reversing) as different in any of the above-given interpretations of this sequence, we get A007051 (or A124302). Also, a(n-1) is the sum of first 3 terms in n-th row of A284949, see crossrefs therein. - _Andrey Zabolotskiy_, Sep 29 2017

%C a(n-1) 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

%D A. T. Balaban, Enumeration of Cyclic Graphs, pp. 63-105 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976; see p. 75.

%D Balaban, A. T., Brunvoll, J., Cyvin, B. N., & Cyvin, S. J. (1988). Enumeration of branched catacondensed benzenoid hydrocarbons and their numbers of Kekulé structures. Tetrahedron, 44(1), 221-228. See Eq. 6.

%D A. T. Balaban and F. Harary, Chemical graphs V: enumeration and proposed nomenclature of benzenoid cata-condensed polycyclic aromatic hydrocarbons, Tetrahedron 24 (1968), 2505-2516.

%D S. J. Cyvin et al., Unbranched catacondensed polygonal systems containing hexagons and tetragons, Croatica Chem. Acta, 69 (1996), 757-774.

%D S. J. Cyvin et al., Enumeration of tree-like octagonal systems: catapolyoctagons, ACH Models in Chem. 134 (1997), 55-70.

%D R. C. Read, The Enumeration of Acyclic Chemical Compounds, pp. 25-61 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]

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D Gy. Tasi and F. Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chemistry, 25, 1999, 55-64 (see p. 60).

%H Indranil Ghosh, <a href="/A001998/b001998.txt">Table of n, a(n) for n = 0..2092</a> (terms 0..500 from T. D. Noe)

%H Christian Barrientos, Sarah Minion, <a href="https://dx.doi.org/10.20429/tag.2017.040103">On the Graceful Cartesian Product of Alpha-Trees</a>, Theory and Applications of Graphs, Vol. 4: Iss. 1, Article 3, 2017. (mentions this sequence on p. 7)

%H L. W. Beineke and R. E. Pippert, <a href="https://doi.org/10.1017/S0017089500002305">On the enumeration of planar trees of hexagons</a>, Glasgow Math. J., 15 (1974), 131-147.

%H L. W. Beineke and R. E. Pippert, <a href="/A004127/a004127.pdf">On the enumeration of planar trees of hexagons</a>, Glasgow Math. J., 15 (1974), 131-147 [annotated scanned copy].

%H R. M. Foster, <a href="https://doi.org/10.2307/2301339">Solution to Problem E185</a>, Amer. Math. Monthly, 44 (1937), 50-51.

%H R. M. Foster, <a href="/A001997/a001997.pdf">Solution to Problem E185</a>, Amer. Math. Monthly, 44 (1937), 50-51 [annotated scanned copy].

%H F. Harary and R. W. Robinson, <a href="/A001333/a001333_2.pdf">Tapeworms</a>, Unpublished manuscript, circa 1973. (Annotated scanned copy)

%H Thomas M. Liggett, Wenpin Tang, <a href="https://arxiv.org/abs/1804.06877">One-dependent hard-core processes and colorings of the star graph</a>, arXiv:1804.06877 [math.PR], 2018.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 1992.

%H <a href="/index/Fo#fold">Index entries for sequences obtained by enumerating foldings</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,0,-12,9).

%F a(n) = if n mod 2 = 0 then ((3^((n-2)/2)+1)/2)^2 else 3^((n-3)/2)+(1/4)*(3^(n-2)+1).

%F G.f.: (1-2*x-4*x^2+6*x^3) / ((1-x)*(1-3*x)*(1-3*x^2)). - Corrected by _Colin Barker_, May 15 2016

%F a(n) = 4*a(n-1)-12*a(n-3)+9*a(n-4), with a(0)=1, a(1)=2, a(2)=4, a(3)=10. - _Harvey P. Dale_, Apr 10 2013

%F a(n) = (1+3^n+3^(1/2*(-1+n))*(2-2*(-1)^n+sqrt(3)+(-1)^n*sqrt(3)))/4. - _Colin Barker_, May 15 2016

%F 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

%F From _Robert A. Russell_, Oct 28 2018: (Start)

%F a(n-1) = (A124302(n) + A182522(n)) / 2 = A124302(n) - A107767(n-1) = A107767(n-1) + A182522(n).

%F a(n-1) = 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(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)).

%F a(n-1) = A057427(n) + A056326(n) + A056327(n). (End)

%e There are 2 ways to bend a piece of wire of length 2 (bend it or not).

%e For n=4 and a(n-1)=10, the 6 achiral patterns are AAAA, AABB, ABAB, ABBA, ABCA, and ABBC. The 4 chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB. - _Robert A. Russell_, Oct 28 2018

%p A001998 := proc(n) if n = 0 then 1 elif n mod 2 = 1 then (1/4)*(3^n+4*3^((n-1)/2)+1) else (1/4)*(3^n+2*3^(n/2)+1); fi; end;

%p A001998:=(-1+3*z+2*z**2-8*z**3+3*z**4)/(z-1)/(3*z-1)/(3*z**2-1); # conjectured by _Simon Plouffe_ in his 1992 dissertation; gives sequence with an extra leading 1

%t 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}] (* _Jean-François Alcover_, Jan 25 2013, from formula *)

%t LinearRecurrence[{4,0,-12,9},{1,2,4,10},30] (* _Harvey P. Dale_, Apr 10 2013 *)

%t Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)

%t k=3; Table[Sum[StirlingS2[n,j]+Ach[n,j],{j,k}]/2,{n,40}] (* _Robert A. Russell_, Oct 28 2018 *)

%o (PARI) Vec((1-2*x-4*x^2+6*x^3)/((1-x)*(1-3*x)*(1-3*x^2)) + O(x^50)) \\ _Colin Barker_, May 15 2016

%o (GAP) a:=[];; for n in [2..45] do if n mod 2 =0 then Add(a,((3^((n-2)/2)+1)/2)^2); else Add(a, 3^((n-3)/2)+(1/4)*(3^(n-2)+1)); fi; od; a; # _Muniru A Asiru_, Oct 28 2018

%Y Cf. A036359, A002216, A005963, A000228, A001997, A001444, A038766.

%Y Column 3 of A320750, offset by one.

%Y Cf. A124302 (oriented), A107767 (chiral), A182522 (achiral), with varying offsets.

%K nonn,nice,easy,changed

%O 0,2

%A _N. J. A. Sloane_

%E Offset and Maple code corrected by _Colin Mallows_, Nov 12 1999

%E Term added by _Robert A. Russell_, Oct 30 2018.

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 23 12:03 EST 2019. Contains 320431 sequences. (Running on oeis4.)