A330635 Array read by rows: T(n,k) is the number of solutions to the equation Sum_{i=1..n} x_i^2 == k (mod 6) with x_i in 0..5, where n >= 0 and 0 <= k <= 5.

1, 0, 0, 0, 0, 0, 1, 2, 0, 1, 2, 0, 2, 8, 8, 2, 8, 8, 36, 24, 48, 36, 24, 48, 264, 192, 192, 264, 192, 192, 1296, 1440, 1152, 1296, 1440, 1152, 7200, 8064, 8064, 7200, 8064, 8064, 46656, 44928, 48384, 46656, 44928, 48384, 286848, 276480, 276480, 286848, 276480, 276480

Offset: 0

Author

Petros Hadjicostas, Dec 21 2019

Keywords

• nonn
• tabf

Comments

Let v(n) = [T(n,0), T(n,1), T(n,2), T(n,3), T(n,4), T(n,5)]' for n >= 0, where ' denotes transpose, and M = [[1, 0, 2, 1, 0, 2], [2, 1, 0, 2, 1, 0], [0, 2, 1, 0, 2, 1], [1, 0, 2, 1, 0, 2], [2, 1, 0, 2, 1, 0], [0, 2, 1, 0, 2, 1]]. We claim that v(n+1) = M*v(n) for n >= 0.

To see why this is the case, let j in 0..5, and consider the expressions 0^2 + j, 1^2 + j, 2^2 + j, 3^2 + j, 4^2 + j, and 5^2 + j modulo 6. It can be easily proved that these six numbers contain M[0,j] 0's, M[1,j] 1's, M[2,j] 2's, M[3,j] 3's, M[4,j] 4's, and M[5,j] 5's. (This is how the transfer matrix M was constructed. The idea is similar to Jianing Song's ideas for sequences A101990, A318609, and A318610.)

It follows that v(n) = M^n * v(0), where v(0) = [1,0,0,0,0,0]'.

The minimal polynomial for M is z*(z - 6)*(z^2 + 12) = z^4 - 6*z^3 + 12*z^2 - 72*z. Thus, M^4 - 6*M^3 + 12*M^2 - 72*M = 0, and so M^n*v(0) - 6*M^(n-1)*v(0) + 12*M^(n-2)*v(0) - 72*M^(n-3)*v(0) = 0 for n >= 4. This implies v(n) - 6*v(n-1) + 12*v(n-2) - 72*v(n-3) = 0 for n >= 4. Hence each sequence (T(n,k): n >= 0) satisfies the same recurrence b(n) - 6*b(n-1) + 12*b(n-2) - 72*b(n-3) = 0 for n >= 4.

Clearly, for each k in 0..5, we may find constants c_k, d_k, e_k such that T(n,k) = c_k*(2*sqrt(3)*i)^n + d_k*(-2*sqrt(3)*i)^n + e_k*6^n for n >= 0, where i = sqrt(-1). We omit the details.

Examples

			Array T(n,k) (with rows n >= 0 and columns 0 <= k <= 5) begins as follows:
     1,    0,    0,    0,    0,    0;
     1,    2,    0,    1,    2,    0;
     2,    8,    8,    2,    8,    8;
    36,   24,   48,   36,   24,   48;
   264,  192,  192,  264,  192,  192;
  1296, 1440, 1152, 1296, 1440, 1152;
  7200, 8064, 8064, 7200, 8064, 8064;
  ...
T(n=2,k=0) = 2 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 0 (mod 6) (with x_1, x_2 in 0..5): (0,0) and (3,3).
T(n=2,k=1) = 8 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 1 (mod 6) (with x_1, x_2 in 0..5): (0,1), (0,5), (1,0), (2,3), (3,2), (3,4), (4,3), and (5,0).
T(n=2,k=2) = 8 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 2 (mod 6) (with x_1, x_2 in 0..5): (1,1), (1,5), (2,2), (2,4), (4,2), (4,4), (5,1), and (5,5).
T(n=2,k=3) = 2 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 3 (mod 6) (with x_1, x_2 in 0..5): (0,3) and (3,0).
T(n=2,k=4) = 8 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 4 (mod 6) (with x_1, x_2 in 0..5): (0,2), (0,4), (1,3), (2,0), (3,1), (3,5), (4,0), and (5,3).
T(n=2,k=5) = 8 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 5 (mod 6) (with x_1, x_2 in 0..5): (1,2), (1,4), (2,1), (2,5), (4,1), (4,5), (5,2), and (5,4).
		

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,6,0,0,0,0,0,-12,0,0,0,0,0,72).

Crossrefs

Cf. A101990, A228920, A228921, A229136, A229138, A318609, A318610, A330607, A330619.

Programs

Maple

with(LinearAlgebra);
v := proc(n) local M, v0;
   M := Matrix([[1,0,2,1,0,2],[2,1,0,2,1,0],[0,2,1,0,2,1],[1,0,2,1,0,2],[2,1,0,2,1,0],[0,2,1,0,2,1]]);
   v0 := Matrix([[1], [0], [0], [0], [0], [0]]);
   if n = 0 then v0; else MatrixMatrixMultiply(MatrixPower(M, n), v0); end if;
end proc;
seq(seq(v(n)[k, 1], k = 1..6), n = 0..10);

PARI

Vec((1 - 5*x^6 + 2*x^7 + x^9 + 2*x^10 + 8*x^12 - 4*x^13 + 8*x^14 - 4*x^15 - 4*x^16 + 8*x^17 - 36*x^18 + 36*x^21) / ((1 - 6*x^6)*(1 + 12*x^12)) + O(x^60)) \\ Colin Barker, Jan 17 2020

Formula

T(n,k) = T(n, k+3) for k = 0,1,2 and n >= 0.

T(n,k) = 6*T(n-1,k) - 12*T(n-2,k) + 72*T(n-3,k) for n >= 4 and each k in 0..5. (This is not true for k = 0 or 3 when n = 3 because of the presence of z in the minimal polynomial for M.)

Sum_{k=0..5} T(n,k) = 6^n.

T(n,k) = -12*T(n-2,k) + 8*6^(n-2) for n >= 3 and k = 0..5.

T(n,k) ~ 6^(n-1) for each k in 0..5.

From Colin Barker, Jan 12 2020: (Start)

If we consider this array as a single sequence (a(n): n >= 0), then:

a(n) = 6*a(n-6) - 12*a(n-12) + 72*a(n-18) for n > 21.

G.f.: (1 - 5*x^6 + 2*x^7 + x^9 + 2*x^10 + 8*x^12 - 4*x^13 + 8*x^14 - 4*x^15 - 4*x^16 + 8*x^17 - 36*x^18 + 36*x^21) / ((1 - 6*x^6)*(1 + 12*x^12)).

(End)