A305826 Number of vectors in {0..4}^n with sum divisible by 9.

1, 1, 1, 11, 81, 381, 1673, 8338, 43585, 220037, 1086581, 5401793, 27090649, 135792879, 678626796, 3389980516, 16949548097, 84773530931, 423896384077, 2119296824851, 10596060837121, 52981415499506, 264911698225527, 1324553898108366, 6622726587716561, 33113628115834381, 165568491457714333

Offset

0,4

Comments

For n >= 1, number of terms in A061831 with at most n digits.

Links

Robert Israel, Table of n, a(n) for n = 0..1430

Index entries for linear recurrences with constant coefficients, signature (9, -36, 114, -216, 270, -222, 117, -36, 5)

Formula

G.f.: (1-8*x+28*x^2-76*x^3+120*x^4-120*x^5+74*x^6-26*x^7+4*x^8) / (1 - 9*x + 36*x^2 - 114*x^3 + 216*x^4 - 270*x^5 + 222*x^6 - 117*x^7 + 36*x^8 - 5*x^9).

Example

For n=3, the a(3)=11 vectors are [0, 0, 0], [1, 4, 4], [2, 3, 4], [2, 4, 3], [3, 2, 4], [3, 3, 3], [3, 4, 2], [4, 1, 4], [4, 2, 3], [4, 3, 2], [4, 4, 1].

Maple

T:= Matrix(9, shape=Circulant[[1, 0, 0, 0, 0, 1, 1, 1, 1]]):
seq((T^n)[1, 1], n=0..60);

Crossrefs

Cf. A061831.

Sequence in context: A233176 A156847 A119364 * A252817 A210064 A323223

Adjacent sequences: A305823 A305824 A305825 * A305827 A305828 A305829

Keyword

nonn

Author

Robert Israel, Jun 10 2018

Status

approved