|
| |
|
|
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)
|
|
69
|
|
|
|
1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, 8256, 16512, 32896, 65792, 131328, 262656, 524800, 1049600, 2098176, 4196352, 8390656, 16781312, 33558528, 67117056, 134225920, 268451840, 536887296, 1073774592, 2147516416, 4295032832
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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
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]
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
The formula given in page 1095 of the Balasubramanian reference can be used to derive this sequence. - Parthasarathy Nambi, May 14 2007
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
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
Number of fibonacenes with n+2 hexagons. See the Balaban and the Dobrynin references. - Emeric Deutsch, Apr 21 2013
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
Number of n-vertex difference graphs (bipartite 2K_2-free graphs) [Peled & Sun, Thm. 9]. - Falk Hüffner, Jan 10 2016
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
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
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
From Robert A. Russell, Oct 28 2018: (Start)
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.
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.
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).
See the examples below of these two different colorings. (End)
Also arises from the enumeration of types of based polyhedra with exactly two triangular faces [Rademacher]. - N. J. A. Sloane, Apr 24 2020
|
|
|
REFERENCES
|
K. Balasubramanian, "Combinatorial Enumeration of Chemical Isomers", Indian J. Chem., (1978) vol. 16B, pp. 1094-1096. See page 1095.
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)
Jablan S. and Sazdanovic R., LinKnot: Knot Theory by Computer, World Scientific Press, 2007.
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)
C. A. Pickover, Keys to Infinity, Wiley 1995, p. 75.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
M. Archibald, A. Blecher, A. Knopfmacher, M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 151 and 733.
Andrei Asinowski, Alon Regev, Triangulations with Few Ears: Symmetry Classes and Disjointness, Integers 16 (2016), #A5.
A. T. Balaban, Chemical graphs. Part 50. Symmetry and enumeration of fibonacenes (unbranched catacondensed benzenoids isoarithmic with helicenes and zigzag catafusenes), MATCH: Commun. Math. Comput. Chem., 24 (1989) 29-38.
Burger, A. P. ; Van Der Merwe, M.; Van Vuuren, J. H. An asymptotic analysis of the evolutionary spatial prisoner’s dilemma on a path, Discrete Appl. Math. 160, No. 15, 2075-2088 (2012), Table 3.1.
C. Ceballos, F. Santos, and G. Ziegler, Many Non-equivalent Realizations of the Associahedron, arXiv:1109.5544 [math.MG], 2011-2013; pp. 15 and 26.
Jacob Crabtree, Another Enumeration of Caterpillar Trees, arXiv:1810.11744 [math.CO], 2018.
S. J. Cyvin, B. N. Cyvin, J. Brunvoll, E. Brendsdal, Zhang Fuji, Guo Xiaofeng, and R. Tosic, Theory of polypentagons, J. Chem. Inf. Comput. Sci., 33 (1993), 466-474.
A. A. Dobrynin, On the Wiener index of fibonacenes, MATCH: Commun. Math. Comput. Chem, 64 (2010), 707-726.
Sahir Gill, Bounds for Region Containing All Zeros of a Complex Polynomial, International Journal of Mathematical Analysis (2018), Vol. 12, No. 7, 325-333.
T. A. Gittings, Minimum braids: a complete invariant of knots and links, arXiv:math/0401051 [math.GT], 2004. - N. J. A. Sloane, Jan 18 2013
R. K. Guy, Letter to N. J. A. Sloane, Nov 1978.
Frank Harary and Allen J. Schwenk, The number of caterpillars, Discrete Mathematics, Volume 6, Issue 4, 1973, 359-365.
N. Hoffman, Binary grids and a related counting problem, Two-Year College Math. J. 9 (1978), 267-272.
S. V. Jablan, Geometry of Links, XII Yugoslav Geometric Seminar (Novi Sad, 1998), Novi Sad J. Math. 29 (1999), no. 3, 121-139.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926. (Annotated scanned copy)
Isaac B. Michael and M. R. Sepanski, Net regular signed trees, Australasian Journal of Combinatorics, Volume 66(2) (2016), 192-204.
U. N. Peled and F. Sun, Enumeration of difference graphs, Discrete Appl. Math., 60 (1995), 311-318.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Hans Rademacher, On the number of certain types of polyhedra, 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.
A. Regev, Remarks on two-eared triangulations, arXiv preprint arXiv:1309.0743 [math.CO], 2013-2014.
N. J. A. Sloane, Classic Sequences
R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), Article #00.1.1.
Eric Weisstein's World of Mathematics, Barker Code.
Eric Weisstein's World of Mathematics, Bishops Problem.
Eric Weisstein's World of Mathematics, Caterpillar Graph.
Eric Weisstein's World of Mathematics, Losanitsch's Triangle.
A. Yajima, How to calculate the number of stereoisomers of inositol-homologs, Bull. Chem. Soc. Jpn. 87 (2014), 1260-1264; see Tables 1 and 2 (and text). - N. J. A. Sloane, Mar 26 2015
Index entries for linear recurrences with constant coefficients, signature (2,2,-4).
|
|
|
FORMULA
|
a(n) = 2^(n-2) + 2^(floor(n/2) - 1).
G.f.: -x*(-1 + 3*x^2) / ( (2*x - 1)*(2*x^2 - 1) ). - Simon Plouffe in his 1992 dissertation
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
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
a(n+2) = 2*a(n+1) - A077957(n) with a(1) = 1, a(2) = 2. - Yosu Yurramendi, Oct 24 2008
a(n) = 2*a(n-1) + 2*a(n-2) - 4*a(n-3). - Jaume Oliver Lafont, Dec 05 2008
Union of A007582 and A161168. Union of A007582 and A063376. - Jaroslav Krizek, Aug 14 2009
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
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
From Robert A. Russell, Oct 28 2018: (Start)
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.
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.
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)).
a(n+1) = (k^n + k^ceiling(n/2)) / 2, where k=2 is number of colors we can use. (End)
|
|
|
EXAMPLE
|
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
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
From Robert A. Russell, Oct 28 2018: (Start)
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.
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)
|
|
|
MAPLE
|
A005418 := n->2^(n-2)+2^(floor(n/2)-1): seq(A005418(n), n=1..34);
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(Haskell)
a005418 n = sum $ a034851_row (n - 1) -- Reinhard Zumkeller, Jan 14 2012
(PARI) A005418(n)= 2^(n-2) + 2^(n\2-1); \\ Joerg Arndt, Sep 16 2013
|
|
|
CROSSREFS
|
Column 2 of A320750 (set partitions).
Cf. A131577 (oriented), A122746(n-3) (chiral), A016116 (achiral), for set partitions with up to two subsets.
Column 2 of A277504, offset by one (colors not permutable).
Cf. A000079 (oriented), A122746(n-2) (chiral), and A060546 (achiral), for a(n+1).
Cf. A001998, A001444, A051436, A051437, A007582, A001445, A032085.
Sequence in context: A052525 A006606 A120421 * A329699 A002215 A007562
Adjacent sequences: A005415 A005416 A005417 * A005419 A005420 A005421
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane, R. K. Guy
|
|
|
STATUS
|
approved
|
| |
|
|
