This site is supported by donations to The OEIS Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(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 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

%C The offset should be 0, since the first row of A034851 is row 0. The name would then be: "Number of n bead...". - _Daniel Forgues_, Jul 26 2018

%C a(n) is the number of non-isomorphic generalized rigid ladders with n cells. A generalized rigid ladder with n cells is a graph with vertex set is the union of {u_0, u_1, ..., u_n} and {v_0, v_1, ..., v_n}, and for every 0 <= i <= n-1, the edges are of the form {u_i,u_i+1}, {v_i, v_i+1}, {u_i,v_i} and either {u_i,v_i+1} or {u_i+1,v_i}. - _Christian Barrientos_, Jul 29 2018

%C Also number of non-isomorphic stairs with n+1 cells. A stair is a snake polyomino allowing only two directions for adjacent cells: east and north. - _Christian Barrientos_ and _Sarah Minion_, Jul 29 2018

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

%C There are two different unoriented row colorings using two colors that give us very similar results here, a difference of one in the offset. In an unoriented row, chiral pairs are counted as one.

%C a(n) is the number of color patterns (set partitions) of an unoriented row of length n using two or fewer colors (subsets). Two color patterns are equivalent if the colors are permutable.

%C a(n+1) is the number of ways to color an unoriented row of length n using two noninterchangeable colors (one need not use both colors).

%C See the examples below of these two different colorings. (End)

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

%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 Jacob Crabtree, <a href="https://arxiv.org/abs/1810.11744">Another Enumeration of Caterpillar Trees</a>, arXiv:1810.11744 [math.CO], 2018.

%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 Sahir Gill, <a href="https://doi.org/10.12988/ijma.2018.8537">Bounds for Region Containing All Zeros of a Complex Polynomial</a>, International Journal of Mathematical Analysis (2018), Vol. 12, No. 7, 325-333.

%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 Frank Harary and Allen J. Schwenk, <a href="https://doi.org/10.1016/0012-365X(73)90067-8">The number of caterpillars</a>, Discrete Mathematics, Volume 6, Issue 4, 1973, Pages 359-365

%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^(floor(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

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

%F a(n) = (A131577(n) + A016116(n)) / 2 = A131577(n) - A122746(n-3) = A122746(n-3) + A016116(n), for set partitions with up to two subsets.

%F a(n+1) = (A000079(n) + A060546(n)) / 2 = A000079(n) - A122746(n-2) = A122746(n-2) + A060546(n), for two colors that do not permute.

%F a(n) = Sum_{j=0..k} (S2(n,j) + Ach(n,j)) / 2, where k=2 is the maximum number of colors, S2(n,k) 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) = (k^n + k^ceiling(n/2)) / 2, where k=2 is number of colors we can use. (End)

%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

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

%e For a(5)=10, the 4 achiral patterns (set partitions) are AAAAA, AABAA, ABABA, and ABBBA. The 6 chiral pairs are AAAAB-ABBBB, AAABA-ABAAA, AAABB-AABBB, AABAB-ABABB, AABBA-ABBAA, and ABAAB-ABBAB. The colors are permutable.

%e For n=4 and a(n+1)=10, the 4 achiral colorings are AAAA, ABBA, BAAB, and BBBB. The 6 achiral pairs are AAAB-BAAA, AABA-ABAA, AABB-BBAA, ABAB-BABA, ABBB-BBBA, and BABB-BBAB. The colors are not permutable. (End)

%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 *)

%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 A320750 (set partitions).

%Y Cf. A131577 (oriented), A122746(n-3) (chiral), A016116 (achiral), for set partitions with up to two subsets.

%Y Column 2 of A277504, offset by one (colors not permutable).

%Y Cf. A000079 (oriented), A122746(n-2) (chiral), and A060546 (achiral), for a(n+1).

%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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 12:50 EST 2019. Contains 319330 sequences. (Running on oeis4.)