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,3

Links

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

Index entries for linear recurrences with constant coefficients, signature (9,-33,63,-66,36,-8).

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

Example

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.

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 *)

Crossrefs

Cf. A338230, A338232.

Sequence in context: A189714 A128638 A036630 * A102841 A036637 A036644

Adjacent sequences: A338226 A338227 A338228 * A338230 A338231 A338232

Keyword

nonn,easy

Author

Enrique Navarrete, Jan 30 2021

Status

approved