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
Examples
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.
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).
Programs
-
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 *)
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