This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005418 Number of (n-1) bead black-white reversible strings; also binary grids; also row sums of Losanitsch's triangle A034851; also number of caterpillar graphs on n nodes.
(Formerly M0771)

%I M0771

%S 1,2,3,6,10,20,36,72,136,272,528,1056,2080,4160,8256,16512,32896,

%T 65792,131328,262656,524800,1049600,2098176,4196352,8390656,16781312,

%U 33558528,67117056,134225920,268451840,536887296,1073774592,2147516416,4295032832

%N Number of (n-1) bead black-white reversible strings; also binary grids; also row sums of Losanitsch's triangle A034851; also number of caterpillar graphs on n nodes.

%C Equivalently, walks on triangle, visiting n+2 vertices, so length n+1, n "corners"; the symmetry group is S3, reversing a walk does not count as different. Walks are not self-avoiding. - _Colin Mallows_

%C Slavik V. Jablan (jablans(AT)yahoo.com) observes that this is also the number of rational knots and links with n crossings (cf. A018240). See reference.

%C Number of bit strings of length (n-1), not counting strings which are the end-for-end reversal or the 0-for-1 reversal of each other as different. - Carl Witty (cwitty(AT)newtonlabs.com), Oct 27 2001

%C The formula given in page 1095 of the Balasubramanian reference can be used to derive this sequence. - _Parthasarathy Nambi_, May 14 2007

%C a(n) written in base 2 (see A164370): a(1) = 1, a(2) = 10, a(3) = 11, a(n) for n >= 4: 1010, 10100, 100100, 1001000, 10001000, 100010000, 1000010000, ..., i.e. digit 1, (A004526(n-3)) times 0, digit 1, (A004526(n-2)) times 0. - _Jaroslav Krizek_, Aug 14 2009

%C Also number of compositions of n up to direction, where a composition is considered equivalent to its reversal, see example. - _Franklin T. Adams-Watters_, Oct 24 2009

%C Number of normally non-isomorphic realizations of the associahedron of type I starting with dimension 2 in Ceballos et al. - _Tom Copeland_, Oct 19 2011

%C Number of fibonacenes with n+2 hexagons. See the Balaban and the Dobrynin references. - _Emeric Deutsch_, Apr 21 2013

%C From the point of view of binary grids, it is a (1,n)-rectangular grid. A225826 to A225834 are the numbers of binary pattern classes in the (m,n)-rectangular grid, 1 < m < 11. - _Yosu Yurramendi_, May 19 2013

%C Number of n-vertex difference graphs (bipartite 2K_2-free graphs) [Peled & Sun, Thm. 9]. - _Falk Hüffner_, Jan 10 2016

%D K. Balasubramanian, "Combinatorial Enumeration of Chemical Isomers", Indian J. Chem., (1978) vol. 16B, pp. 1094-1096. See page 1095.

%D Dymacek, Wayne M. Steinhaus graphs. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 399--412, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561065 (81f:05120) - _N. J. A. Sloane_, May 30 2012

%D Jablan S. and Sazdanovic R., LinKnot: Knot Theory by Computer, World Scientific Press, 2007.

%D Joseph S. Madachy: Madachy's Mathematical Recreations. New York: Dover Publications, Inc., 1979, p. 46 (first publ. by Charles Scribner's Sons, New York, 1966, under the title: Mathematics on Vacation)

%D C. A. Pickover, Keys to Infinity, Wiley 1995, p. 75.

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

%H Reinhard Zumkeller, <a href="/A005418/b005418.txt">Table of n, a(n) for n = 1..1000</a>

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p.151, p. 733.

%H Andrei Asinowski, Alon Regev, <a href="https://www.emis.de/journals/INTEGERS/papers/q5/q5.Abstract.html">Triangulations with Few Ears: Symmetry Classes and Disjointness</a>, Integers 16 (2016), #A5.

%H A. T. Balaban, <a href="http://match.pmf.kg.ac.rs/electronic_versions/Match24/match24_29-38.pdf">Chemical graphs. Part 50. Symmetry and enumeration of fibonacenes (unbranched catacondensed benzenoids isoarithmic with helicenes and zigzag catafusenes</a>, MATCH: Commun. Math. Comput. Chem., 24 (1989) 29-38.

%H C. Ceballos, F. Santos, and G. Ziegler, <a href="http://arxiv.org/abs/1109.5544">Many Non-equivalent Realizations of the Associahedron</a>, p. 15 and 26, arXiv:1109.5544 [math.MG], 2011-2013.

%H S. J. Cyvin et al., <a href="http://dx.doi.org/10.1021/ci00013a027">Theory of polypentagons</a>, J. Chem. Inf. Comput. Sci., 33 (1993), 466-474.

%H A. A. Dobrynin, <a href="http://match.pmf.kg.ac.rs/electronic_versions/Match64/n3/match64n3_707-726.pdf">On the Wiener index of fibonacenes</a>, MATCH: Commun. Math. Comput. Chem, 64 (2010) 707-726.

%H T. A. Gittings, <a href="http://www.arXiv.org/abs/math.GT/0401051">Minimum braids: a complete invariant of knots and links</a>, arXiv:math/0401051 [math.GT], 2004. - _N. J. A. Sloane_, Jan 18 2013

%H R. K. Guy, <a href="/A005418/a005418.pdf">Letter to N. J. A. Sloane, Nov 1978</a>

%H N. Hoffman, <a href="http://www.jstor.org/stable/3026472">Binary grids and a related counting problem</a>, 2-Year Coll. Math. J., 9 (1978), 267-272.

%H S. V. Jablan, <a href="http://www.emis.de/journals/NSJOM/Papers/29_3/NSJOM_29_3_121_139.pdf">Geometry of Links</a>, XII Yugoslav Geometric Seminar (Novi Sad, 1998), Novi Sad J. Math. 29 (1999), no. 3, 121-139.

%H S. M. Losanitsch, <a href="/A000602/a000602_1.pdf">Die Isomerie-Arten bei den Homologen der Paraffin-Reihe</a>, Chem. Ber. 30 (1897), 1917-1926. (Annotated scanned copy)

%H Isaac B. Michael, M. R. Sepanski, <a href="https://ajc.maths.uq.edu.au/pdf/66/ajc_v66_p192.pdf">Net regular signed trees</a>, Australasian Journal of Combinatorics, Volume 66(2) (2016), Pages 192-204.

%H U. N. Peled and F. Sun, <a href="http://dx.doi.org/10.1016/0166-218X(94)00061-H">Enumeration of difference graphs</a>, Discrete Appl. Math., 60 (1995), 311-318.

%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 à Montréal, 1992.

%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. Regev, <a href="http://arxiv.org/abs/1309.0743">Remarks on two-eared triangulations</a>, arXiv preprint arXiv:1309.0743 [math.CO], 2013-2014.

%H N. J. A. Sloane, <a href="/classic.html#LOSS">Classic Sequences</a>

%H R. A. Sulanke, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/SULANKE/sulanke.html">Moments of generalized Motzkin paths</a>, J. Integer Sequences, Vol. 3 (2000), #00.1.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BarkerCode.html">Barker Code</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BishopsProblem.html">Bishops Problem</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Caterpillar.html">Caterpillar Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LosanitschsTriangle.html">Losanitsch's Triangle</a>

%H A. Yajima, <a href="https://www.jstage.jst.go.jp/article/bcsj/87/11/87_20140204/_pdf">How to calculate the number of stereoisomers of inositol-homologs</a>, Bull. Chem. Soc. Jpn. 2014, 87, 1260-1264 | doi:10.1246/bcsj.20140204. See Tables 1 and 2 (and text). - _N. J. A. Sloane_, Mar 26 2015

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,2,-4)

%F a(n) = 2^(n-2) + 2^([n/2]-1).

%F G.f.: -x*(-1+3*x^2) / ( (2*x-1)*(2*x^2-1) ). - _Simon Plouffe_ in his 1992 dissertation

%F G.f.: x*(1+2*x)*(1-3*x^2)/((1-4*x^2)*(1-2*x^2)), not reduced. - _Wolfdieter Lang_, May 08 2001

%F a(n) = 6*a(n-2)-8*a(n-4). a(2*n) = A063376(n-1) = 2*a(2n-1); a(2*n+1) = A007582(n). - _Henry Bottomley_, Jul 14 2001

%F a(n+2) = 2*a(n+1) - A077957(n) with a(1) = 1, a(2) = 2. - _Yosu Yurramendi_, Oct 24 2008

%F a(n) = 2*a(n-1)+2*a(n-2)-4*a(n-3) - _Jaume Oliver Lafont_, Dec 05 2008

%F Union of A007582 and A161168. Union of A007582 and A063376. - _Jaroslav Krizek_, Aug 14 2009

%F G.f.: G(0); G(k) = 1 + 2*x/(1 - x*(1+2^(k+1))/(x*(1+2^(k+1)) + (1+2^k)/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Dec 12 2011

%F a(2*n) = 2*a(2*n-1) and a(2*n+1) = a(2*n) + 4^(n-1) with a(1) = 1. - _Johannes W. Meijer_, Aug 26 2013

%e a(5)=10 because there are 16 compositions of 5 (shown as <vectors>) but only 10 equivalence classes (shown as {sets}): {<5>}, {<4,1>,<1,4>}, {<3,2>,<2,3>}, {<3,1,1>,<1,1,3>}, {<1,3,1>},{<2,2,1>,<1,2,2>}, {<2,1,2>}, {<2,1,1,1>,<1,1,1,2>}, {<1,2,1,1>,<1,1,2,1>}, {<1,1,1,1,1>}. - _Geoffrey Critzer_, Nov 02 2012

%e G.f. = x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 20*x^6 + 36*x^7 + 72*x^8 + ... - _Michael Somos_, Jun 24 2018

%p A005418 := n->2^(n-2)+2^(floor(n/2)-1): seq(A005418(n), n=1..34);

%t LinearRecurrence[{2,2,-4}, {1,2,3}, 40] (* or *) Table[2^(n-2)+2^(Floor[n/2]-1), {n,40}] (* _Harvey P. Dale_, Jan 18 2012 *)

%t k=2; Table[(k^n+k^Ceiling[n/2])/2,{n,0,30}] (*_Robert A. Russell_, Nov 25 2017 *)

%o (Haskell)

%o a005418 n = sum $ a034851_row (n - 1) -- _Reinhard Zumkeller_, Jan 14 2012

%o (PARI) A005418(n)= 2^(n-2) + 2^(n\2-1); \\ _Joerg Arndt_, Sep 16 2013

%Y Column 2 of A277504.

%Y a(n) = (A000079(n-1) + A060546(n-1)) / 2.

%Y Cf. A001998, A001444, A051436, A051437, A007582, A001445, A032085.

%K nonn,easy,nice

%O 1,2

%A _N. J. A. Sloane_, _R. K. Guy_

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 16 08:35 EDT 2018. Contains 313784 sequences. (Running on oeis4.)