A102712 -id:A102712 - cp's OEIS frontend

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

1, 4, 11, 27, 62, 138, 300, 643, 1363, 2866, 5988, 12448, 25770, 53168, 109381, 224481, 459742, 939872, 1918418, 3910398, 7961064, 16190194, 32893738, 66772387, 135437649, 274518868, 556061298, 1125679616, 2277559414, 4605810806, 9309804278, 18809961926

Offset: 1

Adam Kertesz, Jun 09 2006, Jun 13 2006

nonn

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

a(n) is also the sum of the number of binary words with at least one run of consecutive 0's of length >= i for i>=1. In other words A000225 + A008466 + A050231 + A050232 + ... . - Geoffrey Critzer, Jan 12 2013

			a(3)=11 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+2*2+3*1 = 11.

A. M. Odlyzko, Asymptotic Enumeration Methods, pp. 136-137
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 372.

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

Cf. A334833.

A038374 := proc(n) local nshft, thisr, resul; nshft := n ; resul :=0 ; thisr :=0 ; while nshft > 0 do if nshft mod 2 <> 0 then thisr := thisr+1 ; else resul := max(resul, thisr) ; thisr := 0 ; fi ; nshft := floor(nshft/2) ; od ; resul := max(resul, thisr) ; RETURN(resul) ; end : A119706 := proc(n) local count, c, rlen ; count := array(0..n) ; for c from 0 to n do count[c] := 0 ; od ; for c from 0 to 2^n-1 do rlen := A038374(c) ; count[rlen] := count[rlen]+1 ; od ; RETURN( sum('count[c]*c','c'=0..n) ); end: for n from 1 to 40 do print(n,A119706(n)) ; od : # R. J. Mathar, Jun 15 2006
# second Maple program:
b:= proc(n, m) option remember; `if`(n=0, 1,
      `if`(m=0, add(b(n-j, j), j=1..n),
      add(b(n-j, min(n-j, m)), j=1..min(n, m))))
    end:
a:= proc(n) option remember;
     `if`(n<2, n, 2*a(n-1) +b(n, 0))
    end:
seq(a(n), n=1..40);  # Alois P. Heinz, Dec 19 2014

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

a(n+1) = 2*a(n) + A007059(n+2)
a(n) > 2*a(n-1). a(n) = Sum_{i=1..(2^n)-1} A038374(i). - R. J. Mathar, Jun 15 2006
From Geoffrey Critzer, Jan 12 2013: (Start)
O.g.f.: Sum_{k>=1} 1/(1-2*x) - (1-x^k)/(1-2*x+x^(k+1)). - Corrected by Steven Finch, May 16 2020
a(n) = Sum_{k=1..n} A048004(n,k) * k.
(End)
Conjecture: a(n) = A102712(n+1)-2^n. - R. J. Mathar, Jun 05 2025

More terms from R. J. Mathar, Jun 15 2006

Name edited by Alois P. Heinz, Mar 18 2020

A336902 Sum of the smallest parts of all compositions of n into distinct parts.

Original entry on oeis.org

0, 1, 2, 5, 6, 11, 18, 25, 32, 53, 84, 107, 156, 205, 302, 497, 618, 863, 1206, 1597, 2228, 3569, 4440, 6191, 8256, 11329, 14642, 20477, 30390, 38555, 52578, 69625, 92696, 122141, 160500, 211955, 310476, 386941, 521102, 678617, 901386, 1155383, 1529742, 1940749

Offset: 0

Alois P. Heinz, Aug 07 2020

nonn

			a(6) = 18 = 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 1 + 1 + 6: (1)23, (1)32, 2(1)3, 23(1), 3(1)2, 32(1), (2)4, 4(2), (1)5, 5(1), (6).

Alois P. Heinz, Table of n, a(n) for n = 0..5000

Cf. A005895, A006128, A046746, A092265, A097939, A102712, A336903.

b:= proc(n, i, p) option remember; `if`(i*(i+1)/2 b(n$2, 1):
seq(a(n), n=0..50);

b[n_, i_, p_] := b[n, i, p] = If[i(i+1)/2 < n || i < 1, 0,
     If[i == n, i*p!, b[n-i, Min[n-i, i-1], p+1]] + b[n, i-1, p]];
a[n_] := b[n, n, 1];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jul 12 2021, after Alois P. Heinz *)

a(n) == n (mod 2).

A336903 Sum of the largest parts of all compositions of n into distinct parts.

Original entry on oeis.org

0, 1, 2, 7, 10, 19, 42, 61, 98, 151, 304, 403, 654, 925, 1400, 2431, 3328, 4903, 7056, 10117, 13952, 23419, 30406, 44683, 61308, 87289, 116822, 164359, 247774, 327715, 457542, 624445, 855062, 1148023, 1559188, 2058643, 3043506, 3906637, 5375732, 7111975, 9679852

Offset: 0

Alois P. Heinz, Aug 07 2020

nonn

			a(6) = 42 = 3 + 3 + 3 + 3 + 3 + 3 + 4 + 4 + 5 + 5 + 6: 12(3), 1(3)2, 21(3), 2(3)1, (3)12, (3)21, 2(4), (4)2, 1(5), (5)1, (6).

Alois P. Heinz, Table of n, a(n) for n = 0..5000

Cf. A005895, A006128, A046746, A092265, A097939, A102712, A336902.

b:= proc(n, i, p) option remember; `if`(i*(i+1)/2 `if`(n=0, 0, b(n$2, 0)):
seq(a(n), n=0..50);

b[n_, i_, p_] := b[n, i, p] = If[i(i + 1)/2 < n, 0,
     If[n == 0, p!, b[n - i, Min[n - i, i - 1], p + 1]*
     If[p == 0, i, 1] + b[n, i - 1, p]]];
a[n_] := If[n == 0, 0, b[n, n, 0]];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jul 12 2021, after Alois P. Heinz *)

a(n) == n (mod 2).

A109435 Triangle read by rows: T(n,m) = number of binary numbers n digits long, which have m 0's as a substring.

Original entry on oeis.org

1, 2, 1, 4, 3, 1, 8, 7, 3, 1, 16, 15, 8, 3, 1, 32, 31, 19, 8, 3, 1, 64, 63, 43, 20, 8, 3, 1, 128, 127, 94, 47, 20, 8, 3, 1, 256, 255, 201, 107, 48, 20, 8, 3, 1, 512, 511, 423, 238, 111, 48, 20, 8, 3, 1, 1024, 1023, 880, 520, 251, 112, 48, 20, 8, 3, 1, 2048, 2047, 1815, 1121, 558

Offset: 0

Robert G. Wilson v, Jun 28 2005

Column 0 is A000079, column 2 is A000225, column 3 is A008466, column 4 is A050231
Column 5 is A050232, column 6 is A050233, the last column is A001792.
A050227 with a leading column of powers of 2. - R. J. Mathar, Mar 25 2014

			Triangle begins:
n\m_0__1__2__3__4__5
0|  1  0  0  0  0  0
1|  2  1  0  0  0  0
2|  4  3  1  0  0  0
3|  8  7  3  1  0  0
4| 16 15  8  3  1  0
5| 32 31 19  8  3  1
T(5,3)=8 because there are 8 length 5 binary words that contain 000 as a contiguous substring:  00000, 00001, 00010, 00011, 01000, 10000, 10001, 11000. - _Geoffrey Critzer_, Jan 07 2014

Cf. A109433, A001792, A109436, A102712 (row sums ?).

A109435 := proc(n,k)
    option remember ;
    if n< k then
        0;
    elif n = k then
        1;
    else
        2*procname(n-1,k)+2^(n-1-k)-procname(n-1-k,k) ;
    end if;
end proc:
seq(seq( A109435(n,k),k=0..n),n=0..12) ; # R. J. Mathar, Jun 05 2025

T[n_, m_] := Length[ Select[ StringPosition[ #, StringDrop[ ToString[10^m], 1]] & /@ Table[ ToString[ FromDigits[ IntegerDigits[i, 2]]], {i, 2^n, 2^(n + 1) - 1}], # != {} &]]; Flatten[ Table[ T[n, m], {n, 0, 11}, {m, 0, n}]]
nn=15;Map[Select[#,#>0&]&,Transpose[Table[CoefficientList[Series[x^m/(1-Sum[x^k,{k,1,m}])/(1-2x),{x,0,nn}],x],{m,0,nn}]]]//Grid (* Geoffrey Critzer, Jan 07 2014 *)

G.f. for column m: x^m/( (1 - Sum_{k=1..m} x^k)*(1-2*x) ). - Geoffrey Critzer, Jan 07 2014

A322428 Sum T(n,k) of k-th largest parts of all compositions of n; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 3, 1, 8, 3, 1, 19, 8, 4, 1, 43, 20, 11, 5, 1, 94, 48, 27, 16, 6, 1, 202, 110, 64, 42, 22, 7, 1, 428, 245, 149, 100, 64, 29, 8, 1, 899, 533, 341, 228, 163, 93, 37, 9, 1, 1875, 1142, 765, 512, 383, 256, 130, 46, 10, 1, 3890, 2420, 1683, 1144, 859, 638, 386, 176, 56, 11, 1

Offset: 1

Alois P. Heinz, Dec 07 2018

			The 4 compositions of 3 are: 111, 12, 21, 3.  The sums of k-th largest parts for k=1..3 give: 1+2+2+3 = 8, 1+1+1+0 = 3, 1+0+0+0 = 1.
Triangle T(n,k) begins:
     1;
     3,    1;
     8,    3,   1;
    19,    8,   4,   1;
    43,   20,  11,   5,   1;
    94,   48,  27,  16,   6,   1;
   202,  110,  64,  42,  22,   7,   1;
   428,  245, 149, 100,  64,  29,   8,  1;
   899,  533, 341, 228, 163,  93,  37,  9,  1;
  1875, 1142, 765, 512, 383, 256, 130, 46, 10, 1;
  ...

Alois P. Heinz, Rows n = 1..50, flattened

Column k=1 gives A102712.
Row sums give A001787.
T(n+1,1+ceiling(n/2)) gives A027306.
Cf. A322427.

b:= proc(n, l) option remember; `if`(n=0, add(l[-i]*x^i,
      i=1..nops(l)), add(b(n-j, sort([l[], j])), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(b(n, [])):
seq(T(n), n=1..12);

b[n_, l_] := b[n, l] = If[n == 0, Sum[l[[-i]] x^i, {i, 1, Length[l]}], Sum[b[n - j, Sort[Append[l, j]]], {j, 1, n}]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, Exponent[p, x]}]][ b[n, {}]];
Array[T, 12] // Flatten (* Jean-François Alcover, Dec 29 2018, after Alois P. Heinz *)

A336579 Sum of prime parts, counted without multiplicity, in all compositions of n.

Original entry on oeis.org

0, 0, 2, 7, 14, 38, 83, 193, 421, 917, 1969, 4210, 8908, 18763, 39287, 81940, 170270, 352726, 728663, 1501711, 3088326, 6339424, 12991312, 26583389, 54323352, 110876435, 226057023, 460432903, 936963134, 1905110662, 3870698364, 7858803605, 15945759386

Offset: 0

Alois P. Heinz, Jul 26 2020

nonn

			a(4) = 2 + 2 + 2 + 2 + 3 + 3 = 14: 1111, 11(2), 1(2)1, (2)11, (2)2, 1(3), (3)1, 4.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A000040, A097939, A102712, A309561, A336516, A336632.

b:= proc(n, i, p) option remember; `if`(n=0, [p!, 0],
      `if`(i<1, 0, add((p-> [0, `if`(j>0 and isprime(i),
       p[1]*i, 0)]+p)(b(n-i*j, i-1, p+j)/j!), j=0..n/i)))
    end:
a:= n-> b(n$2, 0)[2]:
seq(a(n), n=0..38);

b[n_, i_, p_] := b[n, i, p] = If[n == 0, {p!, 0},
     If[i < 1, {0, 0}, Sum[Function[q, {0, If[j > 0 && PrimeQ[i],
     q[[1]]*i, 0]} + q][b[n - i*j, i - 1, p + j]/j!], {j, 0, n/i}]]];
a[n_] := b[n, n, 0][[2]];
Table[a[n], {n, 0, 38}] (* Jean-François Alcover, Mar 17 2022, after Alois P Heinz *)

A228250 Total sum A(n,k) of lengths of longest contiguous subsequences with the same value over all s in {1,...,n}^k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 6, 3, 0, 0, 4, 16, 12, 4, 0, 0, 5, 38, 45, 20, 5, 0, 0, 6, 86, 156, 96, 30, 6, 0, 0, 7, 188, 519, 436, 175, 42, 7, 0, 0, 8, 404, 1680, 1916, 980, 288, 56, 8, 0, 0, 9, 856, 5349, 8232, 5345, 1914, 441, 72, 9, 0

Offset: 0

Alois P. Heinz, Aug 18 2013

			A(4,1) = 4 = 1+1+1+1: [1], [2], [3], [4].
A(1,4) = 4: [1,1,1,1].
A(3,2) = 12 = 2+1+1+1+2+1+1+1+2: [1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3].
A(2,3) = 16 = 3+2+1+2+2+1+2+3: [1,1,1], [1,1,2], [1,2,1], [1,2,2], [2,1,1], [2,1,2], [2,2,1], [2,2,2].
Square array A(n,k) begins:
  0, 0,  0,   0,    0,     0,      0,       0, ...
  0, 1,  2,   3,    4,     5,      6,       7, ...
  0, 2,  6,  16,   38,    86,    188,     404, ...
  0, 3, 12,  45,  156,   519,   1680,    5349, ...
  0, 4, 20,  96,  436,  1916,   8232,   34840, ...
  0, 5, 30, 175,  980,  5345,  28610,  151115, ...
  0, 6, 42, 288, 1914, 12450,  79716,  504492, ...
  0, 7, 56, 441, 3388, 25571, 190428, 1403689, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Project Euler, Problem 427: n-sequences

Columns k=0-3 give: A000004, A001477, A002378, A152618(n+1).
Rows n=0-2 give: A000004, A001477, 2*A102712.
Main diagonal gives: A228194.
Cf. A228275.

b:= proc(n, m, s, i) option remember; `if`(m>i or s>m, 0,
      `if`(i=0, 1, `if`(i=1, n, `if`(s=1, (n-1)*add(
         b(n, m, h, i-1), h=1..m), b(n, m, s-1, i-1)+
      `if`(s=m, b(n, m-1, s-1, i-1), 0)))))
    end:
A:= (n, k)-> add(m*add(b(n, m, s, k), s=1..m), m=1..k):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[n_, m_, s_, i_] := b[n, m, s, i] = If[m>i || s>m, 0, If[i == 0, 1, If[i == 1, n, If[s == 1, (n-1)*Sum[b[n, m, h, i-1], {h, 1, m}], b[n, m, s-1, i-1] + If[s == m, b[n, m-1, s-1, i-1], 0]]]]]; A[n_, k_] := Sum[m*Sum[b[n, m, s, k], {s, 1, m}], {m, 1, k}]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Jan 19 2015, after Alois P. Heinz *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A336902 Sum of the smallest parts of all compositions of n into distinct parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A336903 Sum of the largest parts of all compositions of n into distinct parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A109435 Triangle read by rows: T(n,m) = number of binary numbers n digits long, which have m 0's as a substring.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A322428 Sum T(n,k) of k-th largest parts of all compositions of n; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A336579 Sum of prime parts, counted without multiplicity, in all compositions of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A228250 Total sum A(n,k) of lengths of longest contiguous subsequences with the same value over all s in {1,...,n}^k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica