%I #17 Mar 12 2024 09:51:55
%S 1,2,4,8,17,36,80,176,403,910,2128,4896,11628,27132,65208,153824,
%T 373175,888030,2170740,5202600,12797265,30853680,76292736,184863168,
%U 459162452,1117370696,2786017120,6804995008,17024247304,41717833740,104673837384
%N Sum of integers generated by n-1 substitutions, starting with 1, k -> k+1, k-1, .., 1.
%C Substitutions 1 -> {2}, 2 -> {3,1}, 3 -> {4,2}, 4 -> {5,3,1}, 5 -> {6,4,2}, 6 -> {7,5,3,1}, 7 -> {8,6,4,2}, etc. The function f(n) gives determinant of (I_{n} - x * A(n)) where I_{n} is the identity matrix and A(n) = 0 if j > i + 1 otherwise (i+j) mod 2, for i = 1, ..., n and j = 1, ..., n, and can be written in terms of Dickson polynomials as g(w) = x*D_(w-1)(1+x, x*(1+x)) + (1-2*x)*E_(w-1)(1+x, x*(1+x)). - Francisco Salinas (franciscodesalinas(AT)hotmail.com), Apr 13 2004
%C Count of integers is A047749.
%C Sum of integers with substitution starting from 0 is A084081.
%H G. C. Greubel, <a href="/A093951/b093951.txt">Table of n, a(n) for n = 1..1000</a>
%F a(n) = [x^n] GF(n) with GF(n) = g(n)/f(n) and f(1)=1, f(2)=1-x^2, f(3)=1-2*x^2, f(n) = f(n-1) - x^2*f(n-3) and g(1)=1, g(2)=1+2*x, g(3)=1+2*x+2*x^2, g(n) = g(n-1) - x^2*g(n-3) + 2*x^(n-1).
%F From _Paul D. Hanna_, Apr 24 2006: (Start)
%F a(2*n) = 4*binomial(3*n, n-1)/(n+1) = 2*A006629(n-1).
%F a(2*n+1) = 6*binomial(3*n+2, n)/(2*n+3) - binomial(3*n+1, n)/(n+1) = A056096(n+3). (End)
%e GF(12) = (1 + 2*x - 7*x^2 - 14*x^3 + 9*x^4 + 20*x^5 + 2*x^6 - 2*x^7 + 2*x^11)/(1 - 11*x^2 + 36*x^4 - 35*x^6 + 5*x^8) produces a(1) to a(12).
%e a(4)=8 since 4-1 = 3 substitutions on 1 produce 1 -> 2 -> 3+1 -> 4 + 2 + 2 = 8.
%t Plus@@@Flatten/@NestList[ #/.k_Integer:>Range[k+1, 1, -2]&, {1}, 8];(*or for n>16 *); f[1]=1; f[2]=1-x^2; f[3]=1-2x^2; f[n_]:=f[n]=Expand[f[n-1]-x^2 f[n-3]]; g[1]=1; g[2]=1+2x; g[3]=1+2x+2x^2; g[n_]:=g[n]=Expand[g[n-1] -x^2 g[n-3]+2 x^(n-1)]; GF[n_]:=g[n]/f[n]; CoefficientList[Series[GF[36], {x, 0, 36}], x]
%o (PARI) {a(n)=if(n%2==0,4*binomial(3*n/2,n/2-1)/(n/2+1), 6*binomial(3*(n\2)+2, n\2)/(2*(n\2)+3) - binomial(3*(n\2)+1,n\2)/(n\2+1))} \\ _Paul D. Hanna_, Apr 24 2006
%o (Magma)
%o function A093951(n)
%o if (n mod 2) eq 0 then return 8*Binomial(Floor(3*n/2), Floor((n-2)/2))/(n+2);
%o else return 6*Binomial(Floor((3*n+1)/2), Floor((n-1)/2))/(n+2) - 2*Binomial(Floor((3*n-1)/2), Floor((n-1)/2))/(n+1);
%o end if; return A093951;
%o end function;
%o [A093951(n): n in [1..40]]; // _G. C. Greubel_, Oct 17 2022
%o (SageMath)
%o def A093951(n):
%o if (n%2==0): return 8*binomial(3*n/2, (n-2)/2)/(n+2)
%o else: return 6*binomial((3*n+1)/2, (n-1)/2)/(n+2) - 2*binomial((3*n-1)/2, (n-1)/2)/(n+1)
%o [A093951(n) for n in range(1,40)] # _G. C. Greubel_, Oct 17 2022
%Y Cf. A006629, A047749, A056096, A084081.
%K nonn
%O 1,2
%A _Wouter Meeussen_, Apr 18 2004