A385407 Number of strings of length n defined on {0, 1, 2, 3} that contain one or no 1's, two or no 2's, three or no 3's and any number of 0's.
1, 2, 4, 11, 31, 86, 282, 939, 2781, 7186, 16496, 34387, 66299, 119926, 205766, 337731, 533817, 816834, 1215196, 1763771, 2504791, 3488822, 4775794, 6436091, 8551701, 11217426, 14542152, 18650179, 23682611, 29798806, 37177886, 46020307, 56549489, 69013506, 83686836, 100872171
Offset: 0
Examples
a(2) = 4 since the strings are 01, 10, 22, 00. a(3) = 11 since the strings are 333, 000, the 3 permutations of 122, the 3 permutations of 100, and the 3 permutations of 220.
Links
- Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).
Crossrefs
Cf. A385312.
Programs
-
Mathematica
LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {1, 2, 4, 11, 31, 86, 282}, 36] (* Amiram Eldar, Jun 28 2025 *) -
Python
def A385407(n): return n*(n*(n*(n*(n*(n-14)+77)-194)+228)-86)//12+1 # Chai Wah Wu, Jul 02 2025
Formula
a(n) = 60*binomial(n,6) + 10*binomial(n,5) + 4*binomial(n,4) + 4*binomial(n,3) + binomial(n,2) + n + 1.
a(n) = 1 - (43/6)*n + 19*n^2 - (97/6)*n^3 + (77/12)*n^4 - (7/6)*n^5 + (1/12)*n^6.
G.f.: (51*x^6 + 9*x^5 + 3*x^4 - 10*x^3 + 11*x^2 - 5*x + 1)/(1-x)^7.
E.g.f.: exp(x)*(1+x)*(1+x^2/2)*(1+x^3/6).
Comments