A056096 -id:A056096 - cp's OEIS frontend

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

Wouter Meeussen, Apr 18 2004

nonn

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.

			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.

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

Cf. A006629, A047749, A056096, A084081.

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

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]

{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

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

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)

A056098 Minimum value in the distribution by first value of Prufer code of noncrossing spanning trees on a circle of n+2 points.

Original entry on oeis.org

1, 2, 5, 17, 68, 267, 1230, 5564, 27575, 136644, 714772, 3743265, 20353789, 110723361, 619347223, 3464770044, 19801412122, 113178582936

Offset: 3

David S. Hough (hough(AT)gwu.edu), Aug 04 2000

nonn

Total in distribution is # t_n of ternary trees and one can prove first and last values in each distribution is t_{n-1}. Maximum appears to occur at 2, minimum near end; perhaps monotone between first, max, min, last. Distributions of Prufer code initial values, starting with 3 points: [1,1,1], [3,4,2,3], [12,17,9,5,12], [55,80,44,22,17,55], [273,403,227,112,68,72,273], [1428,2128,1218,613,335,267,345,1428].

First 200 values (n=3 to 202) of min occur at k=floor((n+5)/2); first 200 values of max (series A056096) occur at k=2.

			There are 12 noncrossing spanning trees on a circle of 4 points. The first values of their Prufer codes have distribution [3,4,2,3], e.g. 3 start with 1, 4 with 2, 2 with 3 and 3 with 4. The minimum value is a(4) = 2.

Cf. A056096.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula