A084075 -id:A084075 - cp's OEIS frontend

A084076 Length of list created by n substitutions k -> Range[-1-abs(k), abs(k)+1] starting with {1}.

1, 5, 27, 157, 963, 6141, 40323, 270845, 1852419, 12857341, 90337283, 641286141, 4592533507, 33139654653, 240723001347, 1758796578813, 12916805074947, 95300512382973, 706044251602947, 5250379998560253, 39176121681444867

Offset: 0

Wouter Meeussen, May 11 2003

nonn

2*a(n-1) is the second diagonal of the triangle A115195.

Row sums of A167432. Hankel transform is A167435. - Paul Barry, Nov 03 2009

			{1}
{-2,-1,0,1,2}
{-3,-2,-1,0,1,2,3,-2,-1,0,1,2,-1,0,1,-2,-1,0,1,2,-3,-2,-1,0,1,2,3}

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Third column (m=2) of triangle A115193, called C(1, 2).
Cf. A000108, A115139, A115195, A167432, A167435.
Cf. A084075, A084077, A084078.

R:=PowerSeriesRing(Rationals(), 40); Coefficients(R!( (1-5*x -(1- x)*Sqrt(1-8*x))/(4*x^2*(1+x)) )); // G. C. Greubel, Nov 23 2022

Rest@CoefficientList[InverseSeries[Series[ -((1+5*n+2*n^2-(1+2*n)*Sqrt[1+6*n+n^2] )/(4*n^2)), {n, 0, 28}]], n] or Length/@Flatten/@NestList[ # /. k_Integer :> Range[ -1-Abs[k], Abs[k]+1]&, {1}, 8]
Flatten[{1,RecurrenceTable[{(n+2)*(7*n-5)*a[n] == (7*n-2)*(7*n-1)*a[n-1] + 4*(2*n-1)*(7*n+2)*a[n-2],a[1]==5,a[2]==27},a,{n,20}]}] (* Vaclav Kotesovec, Oct 14 2012 *)

{a(n) = my(L); L = [1]; if(n < 0, 0, for(i = 1, n, L = concat([ vector(3 + 2*abs(k), i, i - abs(k) - 2) | k <- L])); #L)}; /* Michael Somos, Nov 23 2022 */

def A084076_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1-5*x -(1-x)*sqrt(1-8*x))/(4*x^2*(1+x)) ).list()
A084076_list(40) # G. C. Greubel, Nov 23 2022

G.f. is the series reversion of -((1 + 5*x + 2*x^2 - (1 + 2*x)*sqrt(1 + 6*x + x^2))/(4*x^2)).
G.f.: 2*((c(2*x))^3)/(1+c(2*x)) with the o.g.f. c(x) of A000108 (Catalan numbers).
a(n) = Sum_{j=1..n+1} A115195(n, j), n >= 0.
G.f.: (-1 + (1-x)*c(2*x))/(x*(1+x)); cf. A115139. - Wolfdieter Lang, Feb 23 2006
D-finite with recurrence: (n+2)*(7*n-5)*a(n) = (7*n-2)*(7*n-1)*a(n-1) + 4*(2*n-1)*(7*n+2)*a(n-2). - Vaclav Kotesovec, Oct 14 2012
a(n) ~ 7*2^(3n+3)/(9*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 14 2012
D-finite with recurrence (n+2)*a(n) = 2*(4*n+1)*a(n-1) + (n+16)*a(n-2) - 4*(2*n-3)*a(n-3). - R. J. Mathar, Mar 10 2022
a(n) = ( (7*n-1)*(7*n-2)*a(n-1) + 4*(2*n-1)*(7*n+2)*a(n-2) )/((n+2)*(7*n-5)), with a(0) = 1, a(1) = 5. - G. C. Greubel, Nov 23 2022

A084078 Length of list created by n substitutions k -> Range[-abs(k+1), abs(k-1), 2] starting with {0}.

Original entry on oeis.org

1, 2, 4, 10, 24, 66, 172, 498, 1360, 4066, 11444, 34970, 100520, 312066, 911068, 2862562, 8457504, 26824386, 80006116, 255680170, 768464312, 2471150402, 7474561164, 24161357010, 73473471344, 238552980386, 728745517972

Offset: 0

Wouter Meeussen, May 11 2003

nonn

			{0}, {-1,1}, {0,2,-2,0}, {-1,1,-3,-1,1,-1,1,3,-1,1}

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

Cf. A027307, A084075.

I:=[1,2,4,10]; [n le 4 select I[n] else (6*(35*n^2-125*n+14)*Self(n-1) + (275*n^4 -1870*n^3 +3757*n^2 -1268*n -1806)*Self(n-2) -6*(5*n^2-5*n-28)*Self(n-3) + (n-5)*(n-3)*(25*n^2-45*n-28)*Self(n-4))/((n-1)*(n+1)*(25*n^2-95*n+42)): n in [1..41]]; // G. C. Greubel, Nov 24 2022

Join[{1}, 2*Rest@CoefficientList[InverseSeries[Series[(-1 -6*n -8*n^2 + (1+ 2*n)^2*Sqrt[1+4*n])/(2*(n +4*n^2 +4*n^3)), {n, 0, 40}]], n]]
Length/@ Flatten/@ NestList[# /. k_Integer :> Range[-Abs[k+1], Abs[k-1], 2] &, {0}, 12]

def replace(L): return [i for k in L for i in range(-abs(k + 1), 1 + abs(k - 1), 2)]
def aList(upto, L=[0]): return [1] + [len((L := replace(L))) for _ in range(upto)]
print(aList(12))  # Peter Luschny, Nov 16 2024

@CachedFunction
def a(n): # a = A084078
    if (n<4): return (1,2,4,10)[n]
    else: return (6*(35*n^2 -55*n -76)*a(n-1) +(275*n^4-770*n^3-203*n^2+1736*n-912)*a(n-2) -6*(5*n^2+5*n-28)*a(n-3) +(n-4)*(n-2)*(25*n^2+5*n-48)*a(n-4))/(n*(n+2)*(25*n^2-45*n-28))
[a(n) for n in range(41)] # G. C. Greubel, Nov 24 2022

a(2*n-1) = A027307(n), n >= 1.
a(n) = 2*A084075(n-1), n >= 1.
a(n) = ( 6*(35*n^2 -55*n -76)*a(n-1) + (275*n^4 -770*n^3 -203*n^2 +1736*n -912)*a(n-2) - 6*(5*n^2 +5*n -28)*a(n-3) + (n-4)*(n-2)*(25*n^2+5*n-48)*a(n-4) )/(n*(n+2)*(25*n^2 -45*n -28)), for n >= 4. - G. C. Greubel, Nov 24 2022
a(2*n) = A032349(n+1), n >= 0. - Alexander Burstein, Nov 19 2023

A084077 Length of list created by n substitutions k -> Range(-abs(k+1), abs(k-1)) starting with {1}.

Original entry on oeis.org

1, 3, 11, 41, 159, 633, 2575, 10657, 44735, 190017, 815231, 3527681, 15378687, 67478401, 297777407, 1320753665, 5884652543, 26326301697, 118211192831, 532574203905, 2406726828031, 10906541371393

Offset: 0

Wouter Meeussen, May 11 2003

nonn

			{1}, {-2,-1,0}, {-1,0,1,2,3,0,1,2,-1,0,1}

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A084075, A084076, A084078.

I:=[1,3,11]; [n le 3 select I[n] else (3*(7*n^2 -11*n +6)*Self(n-1) + 2*(28*n^2 -51*n +14)*Self(n-2) + 4*(n-2)*(7*n-4)*Self(n-3))/((n+2)*(7*n-11)): n in [1..41]]; // G. C. Greubel, Nov 23 2022

Length/@Flatten/@NestList[ # /. k_Integer:>Range[ -Abs[k+1], Abs[k-1]]&, {1}, 8]
Flatten[{1,RecurrenceTable[{(n+3)*(7*n-4)*a[n] == 3*(7*n^2+3*n+2)*a[n-1] + 2*(28*n^2+5*n-9)*a[n-2] + 4*(n-1)*(7*n+3)*a[n-3],a[1]==3,a[2]==11,a[3]==41},a,{n,20}]}] (* Vaclav Kotesovec, Oct 14 2012 *)

@CachedFunction
def a(n):  # a = A084077
    if (n<3): return (1,3,11)[n]
    else: return (3*(7*n^2 +3*n +2)*a(n-1) + 2*(28*n^2 +5*n -9)*a(n-2) + 4*(n-1)*(7*n+3)*a(n-3))/((n+3)*(7*n-4))
[a(n) for n in range(31)] # G. C. Greubel, Nov 23 2022

invOGF satisfies n - (1+3*n)*a(n) - 2*n*(1+n)*a(n)^2 - 2*n^2*a(n)^3 = 0. [Is it true?]
Recurrence: (n+3)*(7*n-4)*a(n) = 3*(7*n^2+3*n+2)*a(n-1) + 2*(28*n^2+5*n-9)*a(n-2) + 4*(n-1)*(7*n+3)*a(n-3). - Vaclav Kotesovec, Oct 14 2012
a(n) ~ sqrt(52+34*sqrt(2))*(2+2*sqrt(2))^n/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 14 2012

A215067 Number of Motzkin n-paths avoiding odd-numbered steps that are up steps.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 10, 21, 37, 80, 146, 322, 602, 1347, 2563, 5798, 11181, 25512, 49720, 114236, 224540, 518848, 1027038, 2384538, 4748042, 11068567, 22150519, 51817118, 104146733, 244370806, 493012682, 1159883685, 2347796965, 5536508864, 11239697816, 26560581688, 54061835288

Offset: 0

David Scambler, Aug 02 2012

nonn

This sequence interleaves the counts of the closely related sequences A109081 and A106228.

a(n) is the number of (peakless) Motzkin paths of length n where every pair of matching up and down edges occupies positions of the same parity. Equivalently, the number of RNA secondary structures on n vertices where only vertices of the same parity can be matched. - Alexander Burstein, May 17 2021

			a(5) = 6: fUfFd, fUfDf, fUdUd, fUdFf, fFfUd, fFfFf showing odd-numbered steps in lower case.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.

Cf. A109081, A106228, A114465, A084075.

b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, b(x-1, y) +b(x-1, y+1) +
      `if`(irem(x, 2)=1, 0, b(x-1, y-1)) ))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Apr 04 2013

f[n_,x_,y_]:=f[n,x,y] = If[x>n||y<0,0,If[x==n&&y==0,1, If[EvenQ[x],0,f[n,x+1,y+1]] +f[n,x+1,y-1] + f[n,x+1,y]]]; Table[f[n,0,0],{n,0,35}]

{a(n)=polcoeff((1/x)*serreverse(x*(3+2*x+x^2 - sqrt((1+x^2)*(1+4*x+x^2)+x^2*O(x^n)))/(2*(1+x+x^2+x^2*O(x^n)))),n)} \\ Paul D. Hanna, Aug 02 2012

from mpmath import mp
mp.dps = 25; mp.pretty = True
def A215067(n) :
    m = n%2; r = n//2 if n>0 else 1
    return r^(1-m)*mp.hyper([-r,1-r-2*m,1+r+m],[(3-m)/2,(4-m)/2],1/4)
[int(A215067(i)) for i in (0..32)]  # Peter Luschny, Aug 03 2012

a(2*n) = Sum_{k=0..n} binomial(n+k-1,n-k) * binomial(n,k)/(n-k+1);
a(2*n+1) = Sum_{k=0..n} binomial(n+k+1,n-k) * binomial(n,k)/(n-k+1).
G.f.: (1/x)*Series_Reversion( x*(3+2*x+x^2 - sqrt((1+x^2)*(1+4*x+x^2)))/(2*(1+x+x^2)) ). - Paul D. Hanna, Aug 02 2012
G.f. satisfies: A(x) = G(x*A(x)) where G(x) = A(x/G(x)) = (3+2*x+x^2 + sqrt((1+x^2)*(1+4*x+x^2)))/4. - Paul D. Hanna, Aug 02 2012
G.f. satisfies: Series_Reversion(x*A(x)) = x - x^2*F(-x) where F(x) = g.f. of A114465. - Paul D. Hanna, Aug 02 2012
a(n) = 3_F_2([-r,1-r-2*m,1+r+m],[(3-m)/2,(4-m)/2],1/4)*r^(1-m) for n>0 where m = n mod 2 and r = floor(n/2). - Peter Luschny, Aug 03 2012

A084079 Sum of absolute values of lists created by n substitutions k -> Range[ -Abs[k+1],Abs[k-1],2] starting with {1}.

Original entry on oeis.org

1, 2, 7, 16, 53, 130, 431, 1104, 3689, 9730, 32775, 88288, 299501

Offset: 0

Wouter Meeussen, May 11 2003

nonn

Sums of absolute of sublists from A084075.

			Sums of absolute values of {1}, {-2,0}, {-1,1,3,-1,1}, {0,2,-2,0,-4,-2,0,2,0,2,-2,0} are 1,2,7,16

Cf. A084075.

Plus@@@Abs/@Flatten/@NestList[ # /. k_Integer :> Range[ -Abs[k+1], Abs[k-1], 2]&, {1}, 12]

cp's OEIS Frontend

A084076 Length of list created by n substitutions k -> Range[-1-abs(k), abs(k)+1] starting with {1}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A084078 Length of list created by n substitutions k -> Range[-abs(k+1), abs(k-1), 2] starting with {0}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Python

SageMath

Formula

A084077 Length of list created by n substitutions k -> Range(-abs(k+1), abs(k-1)) starting with {1}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A215067 Number of Motzkin n-paths avoiding odd-numbered steps that are up steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A084079 Sum of absolute values of lists created by n substitutions k -> Range[ -Abs[k+1],Abs[k-1],2] starting with {1}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica