OFFSET
0,7
COMMENTS
a(n) is the number of binary strings of length n that contain at least five 0's but not all digits are 0.
a(n) is also the number of proper subsets with at least five elements of an n-element set.
LINKS
Index entries for linear recurrences with constant coefficients, signature (7,-20,30,-25,11,-2).
FORMULA
a(n) = 2^n - Sum_{i={0..4,n}} binomial(n,i).
G.f.: x^6*(2*x^4-9*x^3+16*x^2-14*x+6)/((2*x-1)*(x-1)^5). - Alois P. Heinz, Mar 09 2021
EXAMPLE
a(9) = 255 since the strings are the 126 permutations of 000001111, the 84 permutations of 000000111, the 36 permutations of 000000011, and the 9 permutations of 000000001.
MATHEMATICA
LinearRecurrence[{7, -20, 30, -25, 11, -2}, {0, 0, 0, 0, 0, 0, 6, 28, 92, 255, 637}, 40] (* Harvey P. Dale, Jun 11 2024 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Enrique Navarrete, Mar 09 2021
STATUS
approved