A179865 Number of n-bit binary numbers containing one run of 0's.

1, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431

Offset: 1

Author

Vladimir Shevelev, Jul 30 2010, Aug 03 2010

Keywords

• nonn
• base
• easy

Examples

			G.f. = x + x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 15*x^6 + 21*x^7 + 28*x^8 + ...
For n = 4, the 6 numbers are 1000, 1001, 1011, 1100, 1101, 1110.
		

Links

• Gennady Eremin, Table of n, a(n) for n = 1..500
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Crossrefs

Cf. A000217.

Programs

Python

def A179865(n):
    if n==1: return 1
    return n*(n-1)//2  # Gennady Eremin, Mar 14 2021

Formula

For n>=2, a(n) = A000217(n-1).

G.f.: x*(1 + x/(1-x)^3). - Gennady Eremin, Feb 23 2021

For n > 1, a(n+1) = a(n) + n. - Gennady Eremin, Mar 12 2021

E.g.f.: x*(2 + x*exp(x))/2. - Stefano Spezia, Jan 29 2023

Extensions

Edited by N. J. A. Sloane, Aug 08 2010

More terms from Michel Marcus, Feb 23 2021