A119706 -id:A119706 - cp's OEIS frontend

A050227 Triangle of number of n-tosses having a run of r or more heads for a fair coin with r=1 to n across and n=1, 2, ... down.

1, 3, 1, 7, 3, 1, 15, 8, 3, 1, 31, 19, 8, 3, 1, 63, 43, 20, 8, 3, 1, 127, 94, 47, 20, 8, 3, 1, 255, 201, 107, 48, 20, 8, 3, 1, 511, 423, 238, 111, 48, 20, 8, 3, 1, 1023, 880, 520, 251, 112, 48, 20, 8, 3, 1, 2047, 1815, 1121, 558, 255, 112, 48, 20, 8, 3, 1, 4095, 3719

Offset: 1

Eric W. Weisstein

			Triangle begins:
   1;
   3,  1;
   7,  3, 1;
  15,  8, 3, 1;
  31, 19, 8, 3, 1
  ...

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd ed. New York: Wiley, p. 300, 1968.

T. D. Noe, Rows n=1..100 of triangle, flattened
Eric Weisstein's World of Mathematics, Coin Tossing.
Eric Weisstein's World of Mathematics, Run.

Cf. A008466, A119706 (row sums?).

Cf. A050231, A050232, A050233.

Clear[fib]; fib[n_, n_] = 1; fib[n_, k_] /; k > n = 0; fib[n_, k_] := fib[n, k] = If[k == 1, 1, Sum[fib[m, k], {m, n - k , n - 1}]]; Table[ 2^n - fib[n + k + 1 , k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 15 2013 *)

A333394 Total length of all longest runs of 0's in solus bitstrings of length n.

Original entry on oeis.org

0, 1, 4, 9, 18, 34, 62, 110, 192, 331, 565, 958, 1615, 2710, 4531, 7552, 12554, 20823, 34472, 56972, 94020, 154959, 255102, 419532, 689312, 1131632, 1856382, 3043208, 4985674, 8163321, 13359207, 21851594, 35726470, 58386958, 95383471, 155766277, 254288786

Offset: 0

Steven Finch, Mar 18 2020

nonn

A bitstring is solus if all of its 1's are isolated.

The number of these bitstrings is A000045(n+2).

			a(4) = 18 because the A000045(6) = 8 solus bitstrings of length 4 are 0000, 1000, 0100, 0010, 0001, 1010, 0101, 1001 and the longest 0-runs contribute 4+3+2+2+3+1+1+2 = 18.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.

Cf. A000045, A119706, A333395, A333396.

b:= proc(n, w, m, s) option remember; `if`(n=0, m,
      b(n-1, w+1, max(m, w+1), irem(s, 10)*10+0)+
     `if`(s in [01, 21], 0, b(n-1, 0, m, irem(s, 10)*10+1)))
    end:
a:= n-> b(n, 0, 0, 22):
seq(a(n), n=0..39);  # Alois P. Heinz, Mar 18 2020

b[n_, w_, m_, s_] := b[n, w, m, s] = If[n == 0, m, b[n-1, w+1, Max[m, w+1], Mod[s, 10]*10+0]+If[MatchQ[s, 01|21], 0, b[n-1, 0, m, Mod[s, 10]*10+1]]];
a[n_] := b[n, 0, 0, 22];
a /@ Range[0, 39] (* Jean-François Alcover, Aug 21 2020, after Alois P. Heinz *)

G.f.: Sum_{k>=1} (1+x)/(1-x-x^2)-(1+x-x^k-x^(k+1))/(1-x-x^2+x^(k+1)).

A333395 Total length of all longest runs of 1's in multus bitstrings of length n.

Original entry on oeis.org

0, 2, 7, 16, 32, 62, 118, 221, 409, 751, 1371, 2492, 4513, 8148, 14674, 26371, 47304, 84717, 151508, 270622, 482849, 860661, 1532745, 2727483, 4849988, 8618549, 15306204, 27168300, 48199022, 85469639, 151495120, 268418323, 475405955, 841718780, 1489804565, 2636091495

Offset: 1

Steven Finch, Mar 18 2020

nonn

A bitstring is multus if each of its 1's possess at least one neighboring 1.

The number of these bitstrings is A005251(n+2).

			a(4) = 16 because the seven multus bitstrings of length 4 are 0000, 1100, 0110, 0011, 1110, 0111, 1111 and the longest 1-runs contribute 0+2+2+2+3+3+4 = 16.

Alois P. Heinz, Table of n, a(n) for n = 1..985
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.

Cf. A005251, A119706, A333394, A333396.

gf[n_] := x/((x - 1) (1 - x + x^2)) + Sum[((x - 1) x^k)/((x^3 - x^2 + 2 x - 1) (x^(k + 1) - x^3 + x^2 - 2 x + 1)), {k, 1, n}];
ser[n_] := Series[gf[n], {x, 0, n}];
Drop[CoefficientList[ser[36], x], 1] (* Peter Luschny, Mar 19 2020 *)

G.f.: -x/((1-x)*(1-x+x^2)) + x*Sum_{k>=1} (1+x^2)/(1-2*x+x^2-x^3) - (1+x^2-x^(k-1)-x^k)/(1-2*x+x^2-x^3+x^(k+1)).

A209232 a(n) is 2^n times the expected value of the shortest run of 0's in a binary word of length n.

Original entry on oeis.org

0, 1, 4, 11, 25, 52, 103, 199, 380, 724, 1382, 2649, 5103, 9881, 19224, 37559, 73646, 144848, 285623, 564429, 1117396, 2215436, 4398054, 8740266, 17385207, 34607218, 68934319, 137386725, 273942683, 546450648, 1090419638

Offset: 0

Geoffrey Critzer, Jan 12 2013

nonn

a(n) is also the sum of the number of binary words containing at least one 0 and having every consecutive run of 0's of length >= i for i >= 1. In other words, a(n) = A000225(n) + A077855(n) + A130578(n) + A209231(n) + ...

			a(3) = 11. To the length 3 binary words {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 1, 1} we have respectively shortest zero runs of length 3 + 2 + 1 + 1 + 2 + 1 + 1 + 0 = 11.

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, Chapter 7.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A119706.

nn = 30; Apply[Plus, Table[a = x^n/(1 - x); CoefficientList[Series[(a + 1)/((1 - a x/(1 - x)))*1/(1 - x) - 1/(1 - x), {x, 0, nn}], x], {n, 1, nn}]]

O.g.f.: Sum_{k >= 1} (x^k/(1 - x) + 1) / ((1 - x^(k + 1)/(1 - x)^2)) * 1/(1 - x) - 1/(1 - x).

A333396 Total length of all longest runs of 0's in multus bitstrings of length n.

Original entry on oeis.org

1, 2, 5, 11, 23, 45, 87, 165, 309, 573, 1056, 1934, 3527, 6408, 11605, 20960, 37771, 67928, 121949, 218595, 391302, 699610, 1249475, 2229329, 3974083, 7078658, 12599318, 22410548, 39837420, 70775727, 125675525, 223052519, 395702395, 701695820, 1243827018, 2204007329

Offset: 1

Steven Finch, Mar 18 2020

nonn

A bitstring is multus if each of its 1's possess at least one neighboring 1.

The number of these bitstrings is A005251(n+2).

			a(4) = 11 because the seven multus bitstrings of length 4 are 0000, 1100, 0110, 0011, 1110, 0111, 1111 and the longest 0-runs contribute 4+2+1+2+1+1+0 = 11.

Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.

Cf. A005251, A119706, A333394, A333395.

G.f.: x*Sum_{k>=1} (1+x^2)/(1-2*x+x^2-x^3)-(1+x^2-x^(k-1)+x^k-2*x^(k+1))/(1-2*x+x^2-x^3+x^(k+2)).

A209241 3^n times the expected value of the longest run of 0's in all length n words on {0,1,2}.

Original entry on oeis.org

0, 1, 6, 25, 92, 317, 1054, 3425, 10964, 34729, 109162, 341125, 1061132, 3288713, 10161666, 31318201, 96312696, 295632805, 905955146, 2772234385, 8472129040, 25861509393, 78861419302, 240252829461, 731313754312, 2224352781697

Offset: 0

Geoffrey Critzer, Jan 13 2013

nonn

a(n) is also the sum of length n words on {0,1,2} that have no runs of 0's of length >= i for i >= 1. In other words, A000079 + A028859 + A119826 + A209239 + ...

			a(2) = 6 because for such length 2 words: 00, 01, 02, 10, 11, 12, 20, 21, 22 we have respectively longest zero runs of length 2 + 1 + 1 + 1 + 0 + 0 + 1 + 0 + 0 = 6.

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Wesley, 1996, Chapter 7.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A119706.

nn=25; CoefficientList[Series[Sum[1/(1-3x)-(1-x^k)/(1-3x+2x^(k+1)), {k,1,nn}], {x,0,nn}], x]

O.g.f.: Sum_{k=1..n} 1/(1-3x)-(1-x^k)/(1-3x+2x^(k+1)).

a(n) = Sum_{k=1..n} A209240(n,k)*k.

A334833 Total length squared of longest runs of 1's in all bitstrings of length n.

Original entry on oeis.org

1, 6, 21, 61, 158, 386, 902, 2051, 4565, 10006, 21668, 46484, 98958, 209360, 440627, 923299, 1927456, 4010730, 8322242, 17226050, 35578192, 73339778, 150918130, 310073773, 636173403, 1303554560, 2667935114, 5454522188, 11140674850, 22733861902, 46352349432, 94435176992

Offset: 1

Steven Finch, May 15 2020

nonn

a(n) divided by 2^n is the expected value of the longest run, squared, of heads in n tosses of a fair coin.

			a(3)=21 because for the 8(2^3) possible runs 0 is longest run of heads once, 1 four times, 2 two times and 3 once and 0*1+1*4+4*2+9*1 = 21.

Steven Finch, Variance of longest run duration in a random bitstring, arXiv:2005.12185 [math.CO], 2020.

Cf. A119706.

nn = 10; Drop[Apply[Plus, Table[CoefficientList[Series[(2 n - 1) (1/(1 - 2 x) - (1 - x^n)/(1 - 2 x + x^(n + 1))), {x, 0, nn}], x], {n, 1, nn}]], 1]

O.g.f.: Sum_{k>=1} (2*k-1)*(1/(1-2*x) - (1-x^k)/(1-2*x+x^(k+1))).

cp's OEIS Frontend

A050227 Triangle of number of n-tosses having a run of r or more heads for a fair coin with r=1 to n across and n=1, 2, ... down.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

A333394 Total length of all longest runs of 0's in solus bitstrings of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A333395 Total length of all longest runs of 1's in multus bitstrings of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A209232 a(n) is 2^n times the expected value of the shortest run of 0's in a binary word of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A333396 Total length of all longest runs of 0's in multus bitstrings of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A209241 3^n times the expected value of the longest run of 0's in all length n words on {0,1,2}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A334833 Total length squared of longest runs of 1's in all bitstrings of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula