|
| |
|
|
A245996
|
|
Number of length 1+2 0..n arrays with no pair in any consecutive three terms totaling exactly n.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
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
|
|
|
|
FORMULA
|
Empirical: a(n) = 3*a(n-1) - 2*a(n-2) - 2*a(n-3) + 3*a(n-4) - a(n-5).
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
