A338232 Number of ternary strings of length n that contain at least two 0's and at most two 1's.

0, 0, 1, 7, 33, 121, 378, 1065, 2803, 7045, 17148, 40789, 95373, 220065, 502414, 1136977, 2553831, 5699149, 12645504, 27914877, 61337665, 134213065, 292547346, 635430937, 1375724763, 2969559381, 6392110468, 13723752805, 29393671413, 62813884465, 133949278998, 285078439329, 605590372303

Offset

0,4

Links

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (10,-42,96,-129,102,-44,8).

Formula

a(n) = 2^n + n*2^(n-1) + binomial(n,2)*2^(n-2) - 3*binomial(n,2) - 3*binomial(n,3) - 2*n - 1.

E.g.f.: exp(x)*(exp(x) - 1 - x)*(2 + 2*x + x^2)/2.

G.f.: x^2*(1-3*x+5*x^2-11*x^3+11*x^4)/((1-x)^4*(1-2*x)^3). - Stefano Spezia, Jan 31 2021

Example

a(4) = 33 since the strings are composed of 0000, the 4 permutations of 0001, the 4 permutations of 0002, the 6 permutations of 0011, the 6 permutations of 0022, and the 12 permutations of 0012. Thus, the total number of strings is 1 + 4 + 4 + 6 + 6 + 12 = 33.

Mathematica

CoefficientList[Series[Exp[x](Exp[x]-1-x)(2+2x+x^2)/2, {x, 0, 32}], x]Table[i!, {i, 0, 32}] (* Stefano Spezia, Jan 31 2021 *)
LinearRecurrence[{10, -42, 96, -129, 102, -44, 8}, {0, 0, 1, 7, 33, 121, 378}, 40] (* Harvey P. Dale, Jan 31 2025 *)

Crossrefs

Cf. A338229, A338230.

Sequence in context: A375883 A256860 A221036 * A000605 A215054 A350643

Adjacent sequences: A338229 A338230 A338231 * A338233 A338234 A338235

Keyword

nonn,easy

Author

Enrique Navarrete, Jan 30 2021

Status

approved