A035039 a(n) = 2^n - C(n,0) - C(n,1) - ... - C(n,6).

0, 0, 0, 0, 0, 0, 0, 1, 9, 46, 176, 562, 1586, 4096, 9908, 22819, 50643, 109294, 230964, 480492, 988116, 2014992, 4084248, 8243109, 16587165, 33308926, 66794952, 133820134, 267936278, 536249296, 1072973612, 2146540999, 4293818279, 8588542750, 17178193068

Offset

0,9

Comments

Partial sums of A035038.

a(n) is the number of binary strings of length n that contain at least four runs of ones. - Félix Balado, Sep 16 2025

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

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. 27.

Jürgen Eckhoff, Der Satz von Radon in konvexen Produktstrukturen II, Monat. f. Math., 73 (1969), 7-30.

Ângela Mestre and José Agapito, Square Matrices Generated by Sequences of Riordan Arrays, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.

Index entries for linear recurrences with constant coefficients, signature (9,-35,77,-105,91,-49,15,-2).

Formula

a(n) = A055248(n,7).

G.f.: x^7/((1-2*x)*(1-x)^7).

a(n) = Sum_{k=0..n}, C(n, k+7) = Sum_{k=7..n} C(n, k); a(n) = 2a(n-1) + C(n-1, 6). - Paul Barry, Aug 23 2004

a(n) = A000079(n) - A008859(n). - Alois P. Heinz, Feb 23 2026

Maple

a:=n->sum(binomial(n, j), j=7..n): seq(a(n), n=0..31); # Zerinvary Lajos, Feb 12 2007

Mathematica

a=1; lst={}; s1=s2=s3=s4=s5=s6=s7=0; Do[s1+=a; s2+=s1; s3+=s2; s4+=s3; s5+=s4; s6+=s5; s7+=s6; AppendTo[lst, s7]; a=a*2, {n, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Jan 10 2009 *)
Table[2^n-Total[Binomial[n, Range[0, 6]]], {n, 40}] (* or *) LinearRecurrence[ {9, -35, 77, -105, 91, -49, 15, -2}, {0, 0, 0, 0, 0, 0, 0, 1}, 40] (* Harvey P. Dale, Apr 22 2016 *)

Prog

(Haskell)
a035039 n = a035039_list !! n
a035039_list = map (sum . drop 7) a007318_tabl
-- Reinhard Zumkeller, Jun 20 2015

Crossrefs

Cf. A000079, A000225, A000295, A002663, A002664, A008859, A035038-A035042.

Cf. A007318.

Sequence in context: A053308 A201458 A034487 * A001926 A213749 A085385

Adjacent sequences: A035036 A035037 A035038 * A035040 A035041 A035042

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved