A338229 Number of ternary strings of length n that contain at least one 0 and at most two 1's.
0, 1, 5, 19, 61, 176, 474, 1219, 3035, 7378, 17608, 41405, 96177, 221092, 503702, 1138567, 2555767, 5701478, 12648276, 27918145, 61341485, 134217496, 292552450, 635436779, 1375731411, 2969566906, 6392118944, 13723762309, 29393682025, 62813896268, 133949292078, 285078453775, 605590388207
Offset: 0
Examples
a(3) = 19 since the strings are composed of 000, the 6 permutations of 012, and the 3 permutations of 001, 002, 011 and 022. The total number of strings is then 1 + 6 + 3 + 3 + 3 + 3 = 19.
Links
- Index entries for linear recurrences with constant coefficients, signature (9,-33,63,-66,36,-8).
Programs
-
Mathematica
CoefficientList[Series[Exp[x](Exp[x]-1)(2+2x+x^2)/2,{x,0,32}],x]Table[i!,{i,0,32}] (* Stefano Spezia, Jan 31 2021 *) LinearRecurrence[{9,-33,63,-66,36,-8},{0,1,5,19,61,176},40] (* Harvey P. Dale, Mar 23 2022 *)
Formula
a(n) = 2^n + n*2^(n-1) + binomial(n,2)*2^(n-2) - binomial(n,2) - n - 1.
E.g.f.: exp(x)*(exp(x) - 1)*(2 + 2*x + x^2)/2.
G.f.: x*(1 - 4*x + 7*x^2 - 8*x^3 + 5*x^4)/(1 - 3*x + 2*x^2)^3. - Stefano Spezia, Jan 31 2021