A345954 a(n) is the number of ternary strings of length n with at least three 0's.
0, 0, 0, 1, 9, 51, 233, 939, 3489, 12259, 41385, 135675, 435185, 1373139, 4279161, 13210219, 40490817, 123438531, 374772041, 1134343131, 3425442705, 10326135475, 31088506905, 93507741771, 281053804769, 844319042211, 2535473709033, 7611873722299, 22847398772529, 68567563468179
Offset: 0
Examples
a(5)=51 since the strings are the 10 permutations of 11000, the 10 permutations of 22000, the 20 permutations of 12000, the 5 permutations of 10000, the 5 permutations of 20000, and 00000.
Links
- Index entries for linear recurrences with constant coefficients, signature (9,-30,44,-24).
Formula
a(n) = 3^n - (2^(n-3))*(n^2 + 3*n + 8).
E.g.f: exp(2x)*(exp(x)-x^2/2-x-1).
G.f.: x^3/((1 - 2*x)^3*(1 - 3*x)). - Stefano Spezia, Jul 01 2021