cp's OEIS Frontend

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

%I A245996 #21 Jan 11 2022 08:26:18
%S A245996 2,8,28,64,126,216,344,512,730,1000,1332,1728,2198,2744,3376,4096,
%T A245996 4914,5832,6860,8000,9262,10648,12168,13824,15626,17576,19684,21952,
%U A245996 24390,27000,29792,32768,35938,39304,42876,46656,50654,54872,59320,64000,68922
%N A245996 Number of length 1+2 0..n arrays with no pair in any consecutive three terms totaling exactly n.
%C A245996 From _Pontus von Brömssen_, Jan 10 2022: (Start)
%C A245996 Proof of the empirical observations in the Formula section:
%C A245996 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).
%C A245996 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).
%C A245996 The recurrence and the generating function follow from this. (End)
%H A245996 R. H. Hardin, <a href="/A245996/b245996.txt">Table of n, a(n) for n = 1..210</a>
%H A245996 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-2,3,-1).
%F A245996 Empirical: a(n) = 3*a(n-1) - 2*a(n-2) - 2*a(n-3) + 3*a(n-4) - a(n-5).
%F A245996 From _R. J. Mathar_, Aug 10 2014: (Start)
%F A245996 Empirical: a(n) = 2*A036486(n).
%F A245996 G.f.: 2*x*(1+x+4*x^2) / ( (1+x)*(x-1)^4 ). (End)
%e A245996 Some solutions for n=10:
%e A245996   6   9   5   8   0   5   8   6   9   8   5   0   4   8   5   2
%e A245996   3   8   3   0   0   7   9   5   0   4   7   5   2   4   7   6
%e A245996   6   9   6   9   5   9   7   3   7   4   1   7  10   0   2   6
%Y A245996 Row 1 of A245995.
%Y A245996 Cf. A036486.
%K A245996 nonn
%O A245996 1,1
%A A245996 _R. H. Hardin_, Aug 09 2014