cp's OEIS Frontend

T(n+k,n) = Sum_{sigma = (sigma_1, ..., sigma_n) in S_n} (( Product_{i=1..n} L_{i}(sigma))( Product_{j=1..k} sigma_j mod n )), where k>0 and L_{i}(sigma) is the largest index h with i= sigma_N for all N in {i-j, i-j+1, ..., i-1, i}.

T(m,n) = (n-m+2)^2*(m-1)^(m-3) + Sum_{k=n-m+3...n} binomial(m-2, n-k)*(n-k+1)^(n-k-1)*[binomial(k+1,2)*(n+m+2)*k^(m-n+k-3) + (k*(n-m+1) - binomial(n-m+2,2))*(k-n+m-1)^(k-n+m-3) + Sum_{j=n-m+2} (jk - binomial(j+1,2))*binomial(m-2-n+k, k-1-j)*(n-m+1)*j^(j+m-2-n)*(k-j)^(k-j-2)].

T(m,n) = (n*(n+sqrt(n^2 - 4))-2)/(n*(n+sqrt(n^2 - 4))-4)*((n+sqrt(n^2-4))/2)^m + (n*(n-sqrt(n^2 - 4))-2)/(n*(n-sqrt(n^2 - 4))-4)*((n-sqrt(n^2-4))/2)^m.

T(m,n) = n*T(m-1,n) - T(m-2,n) with T(0,n) = 1.

Note that mex is the minimum excluded function and (+) is bitwise exclusive or. This is an obvious construction given the symmetry of the graph. We define a three-connected path graph P_{n}(3) as the path graph P_{n} with vertices labeled sequentially from 1 to n and additional edges E'={{i, j} : |i-j|=3}. The Sprague-Grundy value of P_{n}(3) is given by the function a(n).

The B-Variant of length n of P_{n}(3) (denoted P_{n}^{B}(3)) is exactly P_{n}(3) with one additional vertex -1 and one additional edge {-1,2}. The degree of vertex -1 is one. The Sprague-Grundy value of P_{n}^{B}(3) is given by the function b(n).

The C-Variant of length n of P_{n}(3) (denoted P_{n}^{C}(3)) is exactly P_{n}(3) with two additional vertices -1 and n+2 and additional edges {-1,2} and {n-1,n+2}. The degree of vertices -1 and n+2 is one. The Sprague-Grundy value of P_{n}^{C}(3) is given by the function c(n).

Then

a(n) = mex({b(i) (+) b(n-7-i) : -3 <= i <= ceiling(n/2)-4});

b(n) = mex({b(n-2)} union {c(i) (+) b(n-7-i): -3 <= i <= n-4});

c(n) = mex({c(n-2)} union {c(i) (+) c(n-7-i): -3 <= i <= ceiling(n/2)-4}). [Edited and extended by Eugene Fiorini, May 14 2019]

The Sprague-Grundy value of the Node-Kayles game on the graph of n linked diamonds, a(n), can be calculated recursively using the Sprague-Grundy values of the Node-Kayles game on two variants, K and X, of the linked diamond graph. We will denote these variant values as K(n) and X(n), and provide their recursive definition as well.

The K variant graph of n linked diamonds has the vertex set {v_0, v_1, ..., v_n, u_1, u_2, ..., u_n, u_{n+1}, w_1, w_2, ..., w_n, w_{n+1}} and the edge set {{v_0, v_1}, {v_1, v_2}, ..., {v_{n-1}, v_n}, {v_0, u_1}, {v_0, w_1}, {u_1, v_1}, {w_1, v_1}, {v_1, u_2}, {v_1, w_2}, {u_2, v_2}, {w_2, v_2},...,{v_{n-1}, u_n}, {v_{n-1}, w_n}, {u_n, v_n}, {w_n, v_n}, {v_n, u_{n+1}}, {v_n, w_{n+1}}}.

The X variant graph of n linked diamonds has the vertex set {v_0, v_1, ..., v_n, u_0, u_1, u_2, ..., u_n, u_{n+1}, w_0, w_1, w_2, ..., w_n, w_{n+1}} with edge set {{v_0, v_1}, {v_1, v_2}, ..., {v_{n-1}, v_n}, {u_0, v_0}, {w_0, v_0}, {v_0, u_1}, {v_0, w_1}, {u_1, v_1}, {w_1, v_1}, {v_1, u_2}, {v_1, w_2}, {u_2, v_2}, {w_2, v_2},...,{v_{n-1}, u_n}, {v_{n-1}, w_n}, {u_n, v_n}, {w_n, v_n}, {v_n, u_{n+1}}, {v_n, w_{n+1}}}.

In the following recursive formulae, "mex{}" is used to denote the "minimum-excluded nonnegative integer" and "(+)" represents the bitwise exclusive OR. To simplify the recursive formulae, we further define K(-2) = K(-1) = X(-2) = X(-1) = 0 and K(0) = X(0) = 2, which also serve as our base cases.

a(n) = mex { K(i-3) (+) K(n-i-1), K(j-2) (+) 1 (+) K(n-j-1) : 1 <= i <= n+1, 1 <= j <= n }.

K(n) = mex { K(i-3) (+) X(n-i-1), K(j-2) (+) 1 (+) X(n-j-1) : 1 <= i <= n+1, 1 <= j <= n+1 }.

X(n) = mex { X(i-3) (+) X(n-i-1), X(j-2) (+) 1 (+) X(n-j-1) : 1 <= i <= n+1, 0 <= j <= n+1 }.

We define b(n) and c(n), as well as their recurrence relations, to be used in the recurrence relation for a(n).

Let b(n) be the Sprague-Grundy value of the Node-Kayles game on the graph of n linked 4-cycles with vertex set {u_1, u_2, ..., u_n, u_{n+1}, u_{n+2}, u_{n+3}, v_1, w_1, v_2, w_2, ..., v_n, w_n}. In this graph, u_1, u_2, ..., u_n, u_{n+1}, u_{n+2}, and u_{n+3} form a path, and additional edges are given by {u_i, v_i}, {v_i, w_i}, and {w_i, u_{i+1}} for all i=1,2,...,n.

Let c(n) be the Sprague-Grundy value of the Node-Kayles game on the graph of n linked 4-cycles with vertex set {u_{-1}, u_0, u_1, u_2, ..., u_n, u_{n+1}, u_{n+2}, u_{n+3}, v_1, w_1, v_2, w_2, ..., v_n, w_n}. In this graph, u_{-1}, u_0, u_1, u_2, ..., u_n, u_{n+1}, u_{n+2}, and u_{n+3} form a path, and additional edges are given by {u_i, v_i}, {v_i, w_i}, and {w_i, u_{i+1}} for all i=1,2,...,n.

In the following recurrence relations, '+' is the bitwise XOR operator.

Recurrence relation for a(n):

a(n) = mex{a(n-1), a(n-2)+b(0), a(n-3)+b(1), ..., a(1)+b(n-3), b(n-3), b(n-2)+1, b(n-4)+b(0), b(n-5)+b(1), ..., b(n-4-floor((n-4)/2))+b(floor((n-4)/2))}, where mex is the minimum excluded function.

Initial conditions for a(n): a(1)=0, a(2)=1, a(3)=3.

Recurrence relation for b(n):

b(n) = mex{a(n), a(n-1)+c(-1), b(n-1), b(n-2), c(n-2)+1, c(n-3), a(1)+c(n-3), a(n-2)+c(0), a(n-3)+c(1), ..., a(2)+c(n-4), b(n-2)+b(0), b(n-3)+b(1), ..., b(floor((n-1)/2))+b(n-2-floor((n-1)/2)), b(n-3)+c(-1), b(n-4)+c(0), b(0)+c(n-4), b(1)+c(n-5), ..., b(n-5)+c(1)}

Initial conditions for b(n): b(0)=2, b(1)=1, b(2)=3, b(3)=2, b(4)=5.

Recurrence relation for c(n):

c(n) = mex{c(n-2), b(n-1)+c(-1), b(n), c(n-1), b(n-2)+c(0), b(n-3)+c(1), ..., b(floor(n/2))+c(n-2-floor((n-2)/2)), c(n-3)+c(-1), c(n-4)+c(0), ..., c(floor((n-3)/2))+c(n-4-floor((n-3)/2))}

Note that c(-1), for convenience, refers to the Sprague-Grundy value of the Node-Kayles game on the path graph on two vertices.

Initial conditions for c(n): c(-1)=1, c(0)=3, c(1)=0, c(2)=1.