|
| |
|
|
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.
|
|
4
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
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.
|
|
|
LINKS
|
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).
|
|
|
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.
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)
|
|
|
EXAMPLE
|
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).
|
|
|
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);
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
