A135493 -id:A135493 - cp's OEIS frontend

A135491 Number of ways to toss a coin n times and not get a run of four.

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

Offset: 0

James R FitzSimons (cherry(AT)getnet.net), Feb 07 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
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.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], 2012-2013.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
Emrah Kılıç, Talha Arıkan, Evaluation of Hessenberg determinants with recursive entries: generating function approach, Filomat (2017) Vol. 31, Issue 15, pp. 4945-4962.
A. V. Zharkova, Inaccesible States in Dynamic Systems Associated with Paths and Cycles, Izv. Saratov Univ. (N.S.), Ser. Math. Mech. Inform., 11 (2011), 116-122.
Index entries for linear recurrences with constant coefficients, signature (1, 1, 1).

Cf. A000073. Column 2 of A265624. Cf. A135492, A135493, A000213, A058265.

LinearRecurrence[{1, 1, 1}, {1, 2, 4, 8}, 36] (* Vladimir Joseph Stephan Orlovsky, Jul 23 2011; first term 1 added by Georg Fischer, Apr 02 2019 *)

Vec(1-2*x*(1+x+x^2)/(-1+x+x^2+x^3) + O(x^100)) \\ Altug Alkan, Dec 10 2015

a(n) = 2*A000073(n+2) for n > 0.
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
a(n) = A000213(n+3) - A000213(n+2), n>=1. - Peter M. Chema, Jan 11 2017.

More terms from Robert G. Wilson v, Feb 10 2008

a(0)=1 prepended by Alois P. Heinz, Dec 10 2015

A249530 T(n,k)=Number of length n+5 0..k arrays with no six consecutive terms having five times any element equal to the sum of the remaining five.

Original entry on oeis.org

62, 606, 122, 3492, 1572, 240, 13580, 12156, 4120, 472, 40950, 59720, 42400, 10834, 928, 104562, 217170, 263156, 147984, 28500, 1824, 235196, 655352, 1154444, 1161050, 516652, 74886, 3586, 480912, 1699092, 4116620, 6143828, 5126096

Offset: 1

R. H. Hardin, Oct 31 2014

Table starts
....62.....606......3492......13580........40950........104562.........235196
...122....1572.....12156......59720.......217170........655352........1699092
...240....4120.....42400.....263156......1154444.......4116620.......12297972
...472...10834....147984....1161050......6143828......25889916.......89105036
...928...28500....516652....5126096.....32715172.....162930700......645979544
..1824...74886...1804128...22639594....174242716....1025679026.....4684420552
..3586..196346...6301554...99998070....928056514....6457498056....33973205930
..7050..515066..22009836..441725882...4943294814...40657829724...246394508200
.13860.1352304..76884550.1951405680..26331473568..255999677748..1787038582186
.27248.3552428.268579888.8621117794.140263427946.1611927429578.12961135262872

			Some solutions for n=3 k=4
..1....1....0....1....0....1....1....0....1....0....0....1....0....0....1....1
..0....1....0....3....3....4....4....4....0....0....0....3....2....4....2....2
..1....4....0....3....0....0....1....0....3....3....1....0....0....4....3....0
..2....4....1....1....2....2....1....0....4....1....0....1....4....1....0....3
..2....0....3....1....0....1....0....0....2....1....1....1....1....4....2....4
..4....0....0....3....4....0....3....2....4....4....1....1....0....0....1....3
..2....1....1....2....0....2....3....2....2....3....1....1....1....1....1....3
..0....3....4....1....0....2....0....2....4....0....4....1....1....1....4....0

R. H. Hardin, Table of n, a(n) for n = 1..468

Column 1 is A135493(n+5)

Empirical for column k:
k=1: a(n) = a(n-1) +a(n-2) +a(n-3) +a(n-4) +a(n-5)
k=2: [order 92]
Empirical for row n:
n=1: [linear recurrence of order 16; also a polynomial of degree 6 plus a quasipolynomial of degree 0 with period 60]

A135492 Number of ways to toss a coin n times and not get a run of five.

Original entry on oeis.org

1, 2, 4, 8, 16, 30, 58, 112, 216, 416, 802, 1546, 2980, 5744, 11072, 21342, 41138, 79296, 152848, 294624, 567906, 1094674, 2110052, 4067256, 7839888, 15111870, 29129066, 56148080, 108228904, 208617920, 402123970, 775118874, 1494089668, 2879950432

Offset: 0

James R FitzSimons (cherry(AT)getnet.net), Feb 07 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1).

Cf. A135491, A135493.

a[n_] := a[n] = a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4]; a[1] = 2; a[2] = 4; a[3] = 8; a[4] = 16; Array[a, 33] (* Robert G. Wilson v, Feb 10 2008 *)
LinearRecurrence[{1, 1, 1, 1}, {2, 4, 8, 16}, 25] (* G. C. Greubel, Oct 15 2016 *)

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,1,1,1]^(n-1)*[2;4;8;16])[1,1] \\ Charles R Greathouse IV, Oct 17 2016

a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4).
a(n) = 2*A000078(n+3) for n>=1.
G.f.: 1-2*x*(x+1)*(1+x^2)/(x^4+x^3+x^2+x-1). - Colin Barker, Jun 12 2012

Corrected and extended by Robert G. Wilson v, Feb 10 2008

a(0)=1 prepended by Alois P. Heinz, May 22 2025

A277828 Least number of tosses of a fair coin needed to have an even chance or better of getting a run of at least m consecutive heads or consecutive tails.

Original entry on oeis.org

1, 2, 5, 11, 23, 45, 90, 179, 357, 712, 1422, 2842, 5681, 11360, 22716, 45430, 90856, 181709, 363413, 726822, 1453640, 2907276, 5814546, 11629086, 23258166, 46516327, 93032647

Offset: 1

Tim Miles, Nov 01 2016

There are a family of sequences that represent the number of sequences of tosses of a fair coin to n tosses where there are no runs of m or more consecutive heads or consecutive tails. Some are given in this Encyclopedia. Their general form is given as part of the formula below. As n increases, the proportion of sequences of tosses that meet this condition decreases. When that proportion becomes a half or less of the total number of sequences of tosses, there is an even or better chance that a run of m consecutive heads or m consecutive tails occurs.
There is actually a family of sequences of which the above sequence is an instance: those in which, for successive values of m, r*g(n) <= 2^n for r > 1.
a(n) - ceiling((log 2)*2^n + (1-log 2)*n + (log 2)/2-2) equals 0 or (almost never) 1 for all n. Obtained using Weisstein's exact formula for Fibonacci k-step number seeing that the function g(N) described in the Formula section is 2*A092921(n-1,N+1). - Andrey Zabolotskiy, Nov 01 2016

Marcus du Sautoy, The Number Mysteries, Fourth Estate, 2011, pages 126 - 127.

Eric Weisstein's World of Mathematics, Coin Tossing

Cf. A135491, A135492, A135493.

a:= proc(n) option remember; local l, j; Digits:= 50;
      if n<3 then n else l:= 0$n;
        for j from 0 while l[n]<1/2 do l:= seq(
          (`if`(i=1, 1.0, l[i-1])+l[n-1])/2, i=1..n)
        od; j
      fi
    end:
seq(a(n), n=1..16);  # Alois P. Heinz, Nov 01 2016

a[n_] := a[n] = Module[{l, j}, If[n < 3, n, l = Table[0, {n}]; For[j = 0, l[[n]] < 1/2, j++, l = Table[(If[i == 1, 1, l[[i - 1]]] + l[[n - 1]])/2, {i, n}]]; j]];
Array[a, 16] (* Jean-François Alcover, May 31 2019, after Alois P. Heinz *)

step(v)=my(n=#v); concat([sum(i=1,n-1,v[i])], concat(vector(n-2,i, v[i]), 2*v[n]+v[n-1]))
a(n)=if(n<3, return(n)); my(v=vector(n), flips=1, needed=1/2); v[1]=1; while(v[n]Charles R Greathouse IV, Nov 02 2016

a(n)=if(n<3, return(n)); my(M=2^(n-1),v=powers(2,n-1)[2..n],i=1,m=n); while(1, v[i]=vecsum(v); if(v[i]<=M, return(m)); if(i++>#v, i=1); M*=2; m++) \\ Charles R Greathouse IV, Nov 02 2016

def a(m):
    if m == 1:
        return 1
    g = [2**i for i in range(1, m)]
    sg, lim, n = sum(g), 2**(m-1), m
    while True:
        g.append(sg)
        sg <<= 1
        sg -= g.pop(0)
        if g[-1] <= lim:
            return n
        lim <<= 1
        n += 1
print([a(i) for i in range(1, 15)])
# Andrey Zabolotskiy, Nov 01 2016

For successive integers m, where g(n) is the number of sequences of tosses of a fair coin with runs of fewer than m consecutive heads or tails out of all possible sequences of tosses to n tosses, g(n) = 2^n where n <= m-1, and thereafter g(n) = g(n-1) + g(n-2) + ... + g(n-m+1) and a(m) = the least value of n for which 2g(n) <= 2^n.

a(11)-a(22) from Andrey Zabolotskiy, Nov 01 2016

a(23)-a(27) from Alois P. Heinz, Nov 02 2016

cp's OEIS Frontend

A135491 Number of ways to toss a coin n times and not get a run of four.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A249530 T(n,k)=Number of length n+5 0..k arrays with no six consecutive terms having five times any element equal to the sum of the remaining five.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A135492 Number of ways to toss a coin n times and not get a run of five.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A277828 Least number of tosses of a fair coin needed to have an even chance or better of getting a run of at least m consecutive heads or consecutive tails.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions