|
%I M0771 #310 Feb 21 2024 08:26:27
%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+2 vertices.
%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 observes that this is also the number of rational knots and links with n+2 crossings (cf. A018240). See reference. [Corrected by _Andrey Zabolotskiy_, Jun 18 2020]
%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)
%C Also arises from the enumeration of types of based polyhedra with exactly two triangular faces [Rademacher]. - _N. J. A. Sloane_, Apr 24 2020
%C a(n) is the number of (unlabeled) 2-paths with n+4 vertices. (A 2-path with order n at least 4 can be constructed from a 3-clique by iteratively adding a new 2-leaf (vertex of degree 2) adjacent to an existing 2-clique containing an existing 2-leaf.) - _Allan Bickle_, Apr 05 2022
%C a(n) is the number of caterpillars with a perfect matching and order 2n+2. - _Christian Barrientos_, Sep 12 2023
%D K. Balasubramanian, "Combinatorial Enumeration of Chemical Isomers", Indian J. Chem., (1978) vol. 16B, pp. 1094-1096. See page 1095.
%D Wayne M. Dymacek, 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 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 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 M. Archibald, A. Blecher, A. Knopfmacher, and M. E. Mays, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Archibald/arch3.html">Inversions and Parity in Compositions of Integers</a>, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 151 and 733.
%H Andrei Asinowski and 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 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 A. P. Burger, M. Van Der Merwe, and J. H. Van Vuuren, <a href="https://doi.org/10.1016/j.dam.2012.04.022">An asymptotic analysis of the evolutionary spatial prisoner’s dilemma on a path</a>, Discrete Appl. Math. 160, No. 15, 2075-2088 (2012), Table 3.1.
%H C. Ceballos, F. Santos, and G. Ziegler, <a href="http://arxiv.org/abs/1109.5544">Many Non-equivalent Realizations of the Associahedron</a>, arXiv:1109.5544 [math.MG], 2011-2013; pp. 15 and 26.
%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, B. N. Cyvin, J. Brunvoll, E. Brendsdal, Zhang Fuji, Guo Xiaofeng, and R. Tosic, <a href="http://dx.doi.org/10.1021/ci00013a027">Theory of polypentagons</a>, J. Chem. Inf. Comput. Sci., 33 (1993), 466-474.
%H Miroslav Marinov Dimitrov, <a href="http://www.math.bas.bg/IMIdocs/ZRASRB/docs/Miroslav_Dimitrov_phd/MDimitrov-avtoreferat-EN.pdf">Designing Boolean Functions and Digital Sequences for Cryptology and Communications</a>, Ph. D. Dissertation, Bulgarian Acad. Sci. (Sofia, Bulgaria 2023).
%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 J. Eckhoff, <a href="https://doi.org/10.1002/jgt.3190170112">Extremal interval graphs</a>, J. Graph Theory 17 1 (1993), 117-127.
%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, 359-365.
%H N. Hoffman, <a href="http://www.jstor.org/stable/3026472">Binary grids and a related counting problem</a>, Two-Year College 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 and 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), 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 Paulo Renato da Costa Pereira, Lilian Markenzon and Oswaldo Vernet, <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 à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H Hans Rademacher, <a href="https://doi.org/10.1215/ijm/1256068140">On the number of certain types of polyhedra</a>, Illinois Journal of Mathematics 9.3 (1965): 361-380. Reprinted in Coll. Papers, Vol II, MIT Press, 1974, pp. 544-564. See Theorem 8, Eq. 14.3.
%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 Suthee Ruangwises, <a href="https://arxiv.org/abs/2306.13551">The Landscape of Computing Symmetric n-Variable Functions with 2n Cards</a>, arXiv:2306.13551 [cs.CR], 2023.
%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), Article #00.1.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/CaterpillarGraph.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://doi.org/10.1246/bcsj.20140204">How to calculate the number of stereoisomers of inositol-homologs</a>, Bull. Chem. Soc. Jpn. 87 (2014), 1260-1264; 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(2*n - 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)
%F E.g.f.: (cosh(2*x) + 2*cosh(sqrt(2)*x) + sinh(2*x) + sqrt(2)*sinh(sqrt(2)*x) - 3)/4. - _Stefano Spezia_, Jun 01 2022
%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
%o (Python)
%o def A005418(n): return 1 if n == 1 else 2**((m:= n//2)-1)*(2**(n-m-1)+1) # _Chai Wah Wu_, Feb 03 2022
%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_
|
