|
| |
|
|
A005418
|
|
Number of n-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)
|
|
27
| |
|
|
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; 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.
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.
Number of bit strings of length n, 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 (PachaNambi(AT)yahoo.com), May 14 2007
a(n) is union A007582(n-1) and A161168(n-1). a(n) is union A007582(n-1) and A063376(n-1). 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. [From Jaroslav Krizek (jaroslav.krizek(AT)atlas.cz), Aug 14 2009]
Also number of compositions of n up to direction, where a composition is considered equivalent to its reversal. [From Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), 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
|
|
|
REFERENCES
| K. Balasubramanian, "Combinatorial Enumeration of Chemical Isomers", Indian J. Chem., (1978) vol. 16B, pp. 1094-1096. See page 1095.
C. Ceballos, F. Santos and G. M. Ziegler, Many non-equivalent realizations of the associahedron, Arxiv preprint arXiv:1109.5544, 2011
S. J. Cyvin et al., Theory of polypentagons, J. Chem. Inf. Comput. Sci., 33 (1993), 466-474.
N. Hoffman, Binary grids and a related counting problem, 2-Year Coll. Math. J., 9 (1978), 267-272.
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)
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
Joerg Arndt, Fxtbook, p.151, p. 733
C. Ceballos, F. Santos, and G. Ziegler, Many Non-equivalent Realizations of the Associahedron, p. 15 and 26
S. V. Jablan, Geometry of Links, XII Yugoslav Geometric Seminar (Novi Sad, 1998), Novi Sad J. Math. 29 (1999), no. 3, 121-139.
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
N. J. A. Sloane, Classic Sequences
R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), #00.1.
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Eric Weisstein's World of Mathematics, Barker Code
Eric Weisstein's World of Mathematics, Losanitsch's Triangle
Index to sequences with linear recurrences with constant coefficients, signature (2,2,-4)
|
|
|
FORMULA
| 2^(n-2) + 2^([n/2]-1).
G.f.: x*(1+2*x)*(1-3*x^2)/((1-4*x^2)*(1-2*x^2)), not reduced - Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de), May 08 2001
a(n) = 6a(n-2)-8a(n-4). a(2n) = A063376(n-1) = 2*a(2n-1); a(2n+1) = A007582(n). - Henry Bottomley (se16(AT)btinternet.com), Jul 14 2001
a(n+2) = 2*a(n+1) - A077957(n) with a(1)=1, a(2)=2 [From Yosu Yurramendi (yosu.yurramendi(AT)ehu.es), Oct 24 2008]
a(n)=2a(n-1)+2a(n-2)-4a(n-3) [From Jaume Oliver Lafont (joliverlafont(AT)gmail.com), Dec 05 2008]
G.f.: A(x)=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
|
|
|
MAPLE
| A005418 := n->2^(n-2)+2^(floor(n/2)-1);
A005418:=-(-1+3*z**2)/(2*z-1)/(2*z**2-1); [S. Plouffe in his 1992 dissertation for offset 0.]
|
|
|
MATHEMATICA
| LinearRecurrence[{2, 2, -4}, {1, 2, 3}, 40] (* or *) Table[2^(n-2)+2^(Floor[n/2]-1), {n, 40}] (* From Harvey P. Dale, Jan 18 2012 *)
|
|
|
PROG
| (Haskell)
a005418 n = sum $ a034851_row (n - 1) -- Reinhard Zumkeller, Jan 14 2012
|
|
|
CROSSREFS
| Cf. A001998, A001444, A051436, A051437, A007582, A001445.
Cf. A032085 [From Yosu Yurramendi (yosu.yurramendi(AT)ehu.es), Oct 24 2008]
Sequence in context: A052525 A006606 A120421 * A002215 A007562 A171682
Adjacent sequences: A005415 A005416 A005417 * A005419 A005420 A005421
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), R. K. Guy
|
|
|
EXTENSIONS
| Interpretation in terms of walks from Colin Mallows (colinm(AT)research.avayalabs.com).
|
| |
|
|
