A093951 Sum of integers generated by n-1 substitutions, starting with 1, k -> k+1, k-1, .., 1.

1, 2, 4, 8, 17, 36, 80, 176, 403, 910, 2128, 4896, 11628, 27132, 65208, 153824, 373175, 888030, 2170740, 5202600, 12797265, 30853680, 76292736, 184863168, 459162452, 1117370696, 2786017120, 6804995008, 17024247304, 41717833740, 104673837384

Offset: 1

Author

Wouter Meeussen, Apr 18 2004

Keywords

• nonn

Comments

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

Count of integers is A047749.

Sum of integers with substitution starting from 0 is A084081.

Examples

			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).
a(4)=8 since 4-1 = 3 substitutions on 1 produce 1 -> 2 -> 3+1 -> 4 + 2 + 2 = 8.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A006629, A047749, A056096, A084081.

Programs

Magma

function A093951(n)
  if (n mod 2) eq 0 then return 8*Binomial(Floor(3*n/2), Floor((n-2)/2))/(n+2);
  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);
  end if; return A093951;
end function;
[A093951(n): n in [1..40]]; // G. C. Greubel, Oct 17 2022

Mathematica

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]

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

SageMath

def A093951(n):
    if (n%2==0): return 8*binomial(3*n/2, (n-2)/2)/(n+2)
    else: return 6*binomial((3*n+1)/2, (n-1)/2)/(n+2) - 2*binomial((3*n-1)/2, (n-1)/2)/(n+1)
[A093951(n) for n in range(1,40)] # G. C. Greubel, Oct 17 2022

Formula

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

From Paul D. Hanna, Apr 24 2006: (Start)

a(2*n) = 4*binomial(3*n, n-1)/(n+1) = 2*A006629(n-1).

a(2*n+1) = 6*binomial(3*n+2, n)/(2*n+3) - binomial(3*n+1, n)/(n+1) = A056096(n+3). (End)