A035041 a(n) = 2^n - C(n,0) - C(n,1) - ... - C(n,8).

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 11, 67, 299, 1093, 3473, 9949, 26333, 65536, 155382, 354522, 784626, 1695222, 3593934, 7507638, 15505590, 31746651, 64574877, 130712029, 263644133, 530396371, 1065084887, 2136022699, 4279934123, 8570386546, 17154657248, 34327470700

Offset

0,11

Comments

a(n) is the number of binary strings of length n that contain at least five 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 (11,-54,156,-294,378,-336,204,-81,19,-2).

Formula

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

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

Maple

a:=n->sum(binomial(n, j), j=9..n): seq(a(n), n=0..33); # Zerinvary Lajos, Jan 04 2007

Mathematica

a=1; lst={}; s1=s2=s3=s4=s5=s6=s7=s8=s9=0; Do[s1+=a; s2+=s1; s3+=s2; s4+=s3; s5+=s4; s6+=s5; s7+=s6; s8+=s7; s9+=s8; AppendTo[lst, s9]; a=a*2, {n, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Jan 10 2009 *)
Table[Sum[ Binomial[n, k], {k, 9, n}], {n, 0, 33}] (* Zerinvary Lajos, Jul 08 2009 *)

Prog

(Haskell)
a035041 n = a035041_list !! n
a035041_list = map (sum . drop 9) a007318_tabl
-- Reinhard Zumkeller, Jun 20 2015

Crossrefs

Column m=9 of A055248.

Partial sums of A035040.

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

Cf. A007318, A008861.

Sequence in context: A268458 A001808 A258479 * A125591 A092841 A165673

Adjacent sequences: A035038 A035039 A035040 * A035042 A035043 A035044

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved