A245996 Number of length 1+2 0..n arrays with no pair in any consecutive three terms totaling exactly n.

2, 8, 28, 64, 126, 216, 344, 512, 730, 1000, 1332, 1728, 2198, 2744, 3376, 4096, 4914, 5832, 6860, 8000, 9262, 10648, 12168, 13824, 15626, 17576, 19684, 21952, 24390, 27000, 29792, 32768, 35938, 39304, 42876, 46656, 50654, 54872, 59320, 64000, 68922

Offset: 1

Author

R. H. Hardin, Aug 09 2014

Keywords

• nonn

Comments

From Pontus von Brömssen, Jan 10 2022: (Start)

Proof of the empirical observations in the Formula section:

For k = 1, 2, 3, let N_k be the number of triples (x, y, z) with x, y, and z in 0..n, that satisfy x+y = n (if k=1), x+y = y+z = n (if k=2), or x+y = y+z = z+x = n (if k=3).

By inclusion-exclusion (and symmetry between x, y, and z), a(n) = (n+1)^3 - 3*N_1 + 3*N_2 - N_3. The unique solution to x+y = y+z = z+x = n is x = y = z = n/2, so N_3 = 1 if n is even, otherwise N_3 = 0. We write this as N_3 = [n even]. It is easily seen that N_1 = (n+1)^2 (x and z can be chosen freely and y = n-x) and that N_2 = n+1 (y can be chosen freely and x = z = n-y), so a(n) = (n+1)^3 - 3*(n+1)^2 + 3*(n+1) - [n even] = n^3 + [n odd] = 2*ceiling(n^3/2) = 2*A036486(n).

The recurrence and the generating function follow from this. (End)

Examples

			Some solutions for n=10:
  6   9   5   8   0   5   8   6   9   8   5   0   4   8   5   2
  3   8   3   0   0   7   9   5   0   4   7   5   2   4   7   6
  6   9   6   9   5   9   7   3   7   4   1   7  10   0   2   6
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..210
• Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).

Crossrefs

Row 1 of A245995.

Cf. A036486.

Formula

Empirical: a(n) = 3*a(n-1) - 2*a(n-2) - 2*a(n-3) + 3*a(n-4) - a(n-5).

From R. J. Mathar, Aug 10 2014: (Start)

Empirical: a(n) = 2*A036486(n).

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