A342352 Expansion of e.g.f. (exp(x)-1)*(exp(x) - x^2/2 - x - 1).

0, 0, 0, 0, 4, 15, 41, 98, 218, 465, 967, 1980, 4016, 8099, 16277, 32646, 65398, 130917, 261971, 524096, 1048364, 2096919, 4194049, 8388330, 16776914, 33554105, 67108511, 134217348, 268435048, 536870475, 1073741357, 2147483150, 4294966766, 8589934029

Offset

0,5

Comments

a(n) is the number of binary strings of length n that contain at least three 0's but not all digits are 0.

a(n) is also the number of proper subsets with at least three elements of an n-element set.

Links

Table of n, a(n) for n=0..33.

Index entries for linear recurrences with constant coefficients, signature (5,-9,7,-2).

Formula

a(n) = 2^n - Sum_{i={0,1,2,n}} binomial(n,i).

G.f.: x^4*(2*x^2-5*x+4)/((2*x-1)*(x-1)^3). - Alois P. Heinz, Mar 09 2021

Example

a(6) = 41 since the strings are the 20 permutations of 000111, the 15 permutations of 000011, and the 6 permutations of 000001.

Crossrefs

Cf. A000079, A000247, A002662.

Sequence in context: A116600 A074033 A093920 * A011844 A075468 A100503

Adjacent sequences: A342349 A342350 A342351 * A342353 A342354 A342355

Keyword

nonn,easy

Author

Enrique Navarrete, Mar 08 2021

Status

approved