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,1

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)

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).

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)

Example

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

Crossrefs

Row 1 of A245995.

Cf. A036486.

Sequence in context: A299640 A197932 A170871 * A229935 A082107 A135263

Adjacent sequences: A245993 A245994 A245995 * A245997 A245998 A245999

Keyword

nonn

Author

R. H. Hardin, Aug 09 2014

Status

approved