login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(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)
52
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 (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-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

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. - Jaroslav Krizek, Aug 14 2009

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

REFERENCES

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.

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

S. J. Cyvin et al., Theory of polypentagons, J. Chem. Inf. Comput. Sci., 33 (1993), 466-474.

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

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)

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

Joerg Arndt, Matters Computational (The Fxtbook), p.151, p. 733

C. Ceballos, F. Santos, and G. Ziegler, Many Non-equivalent Realizations of the Associahedron, p. 15 and 26

A. A. Dobrynin, On the Wiener index of fibonacenes, MATCH: Commun. Math. Comput. Chem, 64 (2010) 707-726.

T. A. Gittings, Minimum braids: a complete invariant of knots and links. - N. J. A. Sloane, Jan 18 2013

S. V. Jablan, Geometry of Links, XII Yugoslav Geometric Seminar (Novi Sad, 1998), Novi Sad J. Math. 29 (1999), no. 3, 121-139.

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 and Conjectures, Université du Québec à Montréal, 1992.

A. Regev, Remarks on two-eared triangulations, arXiv preprint arXiv:1309.0743, 2013

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, Bishops Problem.

Eric Weisstein's World of Mathematics, Caterpillar Graph.

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

a(n) = 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, May 08 2001

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

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

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

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

MAPLE

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

A005418:=-(-1+3*z**2)/(2*z-1)/(2*z**2-1); # Simon 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}] (* 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

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

Sequence in context: A052525 A006606 A120421 * A002215 A007562 A222855

Adjacent sequences:  A005415 A005416 A005417 * A005419 A005420 A005421

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, R. K. Guy

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 25 05:55 EDT 2014. Contains 248518 sequences.