A363256 Number of length n strings on the alphabet {0,1,2,3} with digit sum at most 4.

1, 4, 13, 32, 66, 121, 204, 323, 487, 706, 991, 1354, 1808, 2367, 3046, 3861, 4829, 5968, 7297, 8836, 10606, 12629, 14928, 17527, 20451, 23726, 27379, 31438, 35932, 40891, 46346, 52329, 58873, 66012, 73781, 82216, 91354, 101233, 111892, 123371, 135711

Offset: 0

Author

Daniel T. Martin, May 23 2023

Keywords

• nonn
• easy

Examples

			For n=2, the 13 strings are all possible 2-character strings of '0', '1', '2' and '3' except the four strings '33', '32', '23'.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Crossrefs

Cf. A227259 (the same for {0,1,2} with digit sum <= 4).

Cf. A105163 (the same for {0,1,2} with digit sum <= 3, shifted by 2).

Cf. A005718.

Programs

Mathematica

f[n_, r_, l_] := If[r < 0, 0, If[r==0, 1, If[l < 0, 0, If[l == 0, 1, Sum[f[n, r-j, l-1], {j, 0, n}]]]]]; Table[f[3, 4,x], {x, 0, 40}]

Formula

a(n) = (((n + 10)*n + 35)*n + 26)*n/24 + 1.

G.f.: -(x^4 - 3*x^3 + 3*x^2 - x + 1)/(x - 1)^5.

a(n) = 1 + A005718(n-1) for n>=1.