A005689 Number of Twopins positions. (Formerly M1042)

1, 2, 4, 7, 11, 16, 22, 30, 42, 61, 91, 137, 205, 303, 443, 644, 936, 1365, 1999, 2936, 4316, 6340, 9300, 13625, 19949, 29209, 42785, 62701, 91917, 134758, 197548, 289547, 424331, 621816, 911218, 1335378, 1957086, 2868341, 4203927, 6161329

Offset

6,2

Comments

a(n) is the number of binary strings of length n-2 that are devoid of runs of ones (i.e., maximal runs of ones) of length <= 4. - Félix Balado, Sep 09 2025

References

R. K. Guy, ``Anyone for Twopins?,'' in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=6..45.

Richard Austin and Richard K. Guy, Binary sequences without isolated ones, Fib. Quart., 16 (1978), 84-86.

Félix Balado and Guénolé C. M. Silvestre, Systematic Enumeration of Fundamental Quantities Involving Runs in Binary Strings, arXiv:2602.10005 [math.CO], 2026. See p. 24.

Richard K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]

V. C. Harris and Carolyn C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,4,2).

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,0,1).

Formula

G.f.: x^6*(1+x^2+x^3+x^4+x^5)/(1-2*x+x^2-x^6). - Ralf Stephan, Apr 20 2004

Sum{k=0..floor(n/6), binomial(n-4k, 2k)} is 1, 1, 1, 1, 1, 1, 2, 4, 7, 11, ... - Paul Barry, Sep 16 2004

Maple

A005689:=-(1+z**2+z**3+z**4+z**5)/(z**3+z-1)/(z**3-z+1); # Conjectured by Simon Plouffe in his 1992 dissertation.

Mathematica

LinearRecurrence[{2, -1, 0, 0, 0, 1}, {1, 2, 4, 7, 11, 16}, 40] (* Harvey P. Dale, Feb 02 2019 *)

Prog

(Python)
from sympy import Matrix
def A005689(n):
    A = Matrix([[2, -1]+[0]*3+[1]]+[[0]*i+[1]+[0]*(5-i) for i in range(5)])
    return (A**(n-6)*Matrix([1]*6))[0] # Chai Wah Wu, Jun 11 2026

Crossrefs

Sequence in context: A334251 A175776 A177176 * A212365 A131075 A365698

Adjacent sequences: A005686 A005687 A005688 * A005690 A005691 A005692

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved