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

Author

Enrique Navarrete, Jun 27 2025

Keywords

• nonn
• easy

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