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)
From Nikolai Kotov, Oct 09 2025: (Start)
Geometric interpretation giving an index-shifted version of this sequence. Let ABC be a triangle. On each side place n equally spaced interior points (vertices excluded), and form a triangle by choosing one marked point on each side. Forbid any side of the small triangle to be parallel to a side of ABC. Let T(n) be the number of such triangles. Then T(n) = a(n-1).
Sketch of bijection. Index the chosen points by i on AB from A, j on AC from A, k on BC from B, with i,j,k in {1,...,n}. Put m = n-1 and write i' = i-1, j' = j-1, k' = k-1, so i',j',k' in {0,...,m}. The three parallelism bans are: i' = j' (AB-AC side parallel to BC), k' = j' (AC-BC side parallel to AB), and i' + k' = m (AB-BC side parallel to AC). Map (i',j',k') to (x,y,z) = (i', m - j', k') in {0,...,m}^3. Under this map the bans become x + y = m, y + z = m, and x + z = m. Therefore T(n) equals the number of triples in 0..m with no pair summing to m, which is a(m) with m = n-1. (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)
a(n) ~ n^3. - Charles R Greathouse IV, May 28 2026
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
PROG
(PARI) a(n)=n^3+n%2 \\ Charles R Greathouse IV, May 28 2026
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
R. H. Hardin, Aug 09 2014
STATUS
approved