|
|
A135491
|
|
Number of ways to toss a coin n times and not get a run of four.
|
|
17
|
|
|
1, 2, 4, 8, 14, 26, 48, 88, 162, 298, 548, 1008, 1854, 3410, 6272, 11536, 21218, 39026, 71780, 132024, 242830, 446634, 821488, 1510952, 2779074, 5111514, 9401540, 17292128, 31805182, 58498850, 107596160, 197900192, 363995202, 669491554, 1231386948, 2264873704
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
Elena Barcucci, Antonio Bernini, Stefano Bilotta, Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016. See column 2 of Table 2 p. 11.
Elena Barcucci, Antonio Bernini, Stefano Bilotta and Renzo Pinzani, Non-overlapping matrices, Theoretical Computer Science, Vol. 658, Part A (2017), 36-45.
|
|
FORMULA
|
a(n) = a(n-1) + a(n-2) + a(n-3) for n > 3.
G.f.: -(x+1)*(x^2+1)/(x^3+x^2+x-1).
a(n) = nearest integer to b*c^n, where b = 1.2368... and c = 1.839286755... is the real root of x^3-x^2-x-1 = 0. See A058265. - N. J. A. Sloane, Jan 06 2010
G.f.: (1-x^4)/(1-2*x+x^4) and generally to "not get a run of k" (1-x^k)/(1-2*x+x^k). - Geoffrey Critzer, Feb 01 2012
G.f.: Q(0)/x^2 - 2/x- 1/x^2, where Q(k) = 1 + (1+x)*x^2 + (2*k+3)*x - x*(2*k+1 +x+x^2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 04 2013
|
|
MATHEMATICA
|
|
|
PROG
|
(PARI) Vec(1-2*x*(1+x+x^2)/(-1+x+x^2+x^3) + O(x^100)) \\ Altug Alkan, Dec 10 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
James R FitzSimons (cherry(AT)getnet.net), Feb 07 2008
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|