|
%I M1211 N0468 #157 Mar 28 2024 21:57:23
%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
%C From _Allan Bickle_, Jun 02 2022: (Start)
%C a(n) is the number of (unlabeled) 3-paths with n+6 vertices. (A 3-path with order n at least 5 can be constructed from a 4-clique by iteratively adding a new 3-leaf (vertex of degree 3) adjacent to an existing 3-clique containing an existing 3-leaf.)
%C Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)
%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 S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Enumeration of tree-like octagonal systems: catapolyoctagons, ACH Models in Chem. 134 (1997), 55-70.
%D 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.]
%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).
%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 A. T. Balaban, J. Brunvoll, B. N. Cyvin, and S. J. Cyvin, <a href="https://doi.org/10.1016/S0040-4020(01)85110-3">Enumeration of branched catacondensed benzenoid hydrocarbons and their numbers of Kekulé structures</a>, Tetrahedron 44(1) (1988), 221-228. See Eq. (6), p. 223.
%H A. T. Balaban and F. Harary, <a href="https://doi.org/10.1016/S0040-4020(01)82523-0">Chemical graphs V: enumeration and proposed nomenclature of benzenoid cata-condensed polycyclic aromatic hydrocarbons</a>, Tetrahedron 24 (1968), 2505-2516.
%H Christian Barrientos and 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. (It 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 Allan Bickle, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Bickle/bickle5.html">How to Count k-Paths</a>, J. Integer Sequences, 25 (2022) Article 22.5.6.
%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.
%H S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, <a href="https://dx.doi.org/10.1016/0022-2860(95)09039-8">Isomer enumeration of some polygonal systems representing polycyclic conjugated hydrocarbons</a>, Journal of Molecular structure 376 (Issues 1-3) (1996), 495-505. See Table 2 on p. 501.
%H S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, <a href="https://hrcak.srce.hr/177109">Unbranched catacondensed polygonal systems containing hexagons and tetragons</a>, Croatica Chem. Acta, 69 (1996), 757-774.
%H J. Eckhoff, <a href="https://doi.org/10.1002/jgt.3190170112">Extremal interval graphs</a>, J. Graph Theory 17 1 (1993), 117-127.
%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 and 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 L. Markenzon, O. Vernet, and P. R. da Costa Pereira, <a href="https://doi.org/10.1016/j.dam.2008.05.015">A clique-difference encoding scheme for labelled k-path graphs</a>, Discrete Appl. Math. 156 (2008), 3216-3222.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H Gyula Tasi and Fujio Mizukami, <a href="https://doi.org/10.1023/A:1019163812482">Quantum algebraic-combinatoric study of the conformational properties of n-alkanes</a>, J. Math. Chemistry, 25, 1999, 55-64 (see p. 60).
%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)
%F a(2*n) = A007051(n)^2; a(2*n+1) = A007051(n)*A007051(n+1). - _Todd Simpson_, Mar 25 2024
%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, A007051.
%Y Column 3 of A320750, offset by one. Column k = 0 of A323942, offset by two.
%Y Cf. A124302 (oriented), A107767 (chiral), A182522 (achiral), with varying offsets.
%Y Column 3 of A320750.
%Y The numbers of unlabeled k-paths for k = 2..7 are given in A005418, A001998, A056323, A056324, A056325, and A345207, respectively.
%Y The sequences above converge to A103293(n+1).
%K nonn,nice,easy
%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
|
