OFFSET
0,3
COMMENTS
Without its first term, it is the binomial transform of 1,1,1,1,2,2,2,2,2...
Number of binary strings of length n except those with exactly one 0 or with exactly three 0's. For example, a(6) = 38 since from the 64 strings of length 6 we subtract the 6 permutations of 011111 and the 20 permutations of 000111. - Enrique Navarrete, Nov 16 2025
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,-14,16,-9,2).
FORMULA
a(n) = 2^n - n*(n^2 - 3*n + 8)/6.
a(n) = 1 + C(n,2) + Sum_{k=4..n} C(n,k).
O.g.f.: (1-5*x+10*x^2-10*x^3+5*x^4)/((1-x)^4*(1-2*x)). - R. J. Mathar, Apr 02 2008
a(n) = A000225(n) - (n-1) - binomial(n,3). - G. C. Greubel, Mar 19 2023
From Elmo R. Oliveira, Nov 14 2025: (Start)
E.g.f.: exp(x)*(exp(x) - (x + x^3/6)).
a(n) = 6*a(n-1) - 14*a(n-2) + 16*a(n-3) - 9*a(n-4) + 2*a(n-5). (End)
a(n) = 2^n - A000125(n-1). - Enrique Navarrete, Nov 16 2025
MATHEMATICA
Table[2^n -n -Binomial[n, 3], {n, 0, 50}] (* G. C. Greubel, Mar 19 2023 *)
PROG
(Magma) [2^n -n*(n^2-3*n+8)/6: n in [0..50]]; // G. C. Greubel, Mar 19 2023
(SageMath) [2^n -n*(n^2-3*n+8)/6 for n in range(51)] # G. C. Greubel, Mar 19 2023
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Paul Barry, Jun 06 2003
STATUS
approved