login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A144097 a(n) = number of lattice paths (Schroeder paths) from (0,0) to (3n,n) with unit steps N=(0,1), E=(1,0) and D=(1,1) staying weakly above the line y = 3x. 2
1, 2, 14, 134, 1482, 17818, 226214, 2984206, 40503890, 561957362, 7934063678, 113622696470, 1646501710362, 24098174350986, 355715715691350, 5289547733908510, 79163575684710818, 1191491384838325474 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

a(n) is also the number of lattice path from (0,0) to (4n,0) with unit steps (1,3), (2,2) and (1,-1) staying weakly above the x-axis

Also, the number of planar rooted trees with n non-leaf vertices such that each non-leaf vertex has either 3 or 4 children. - Cameron Marcott, Sep 18 2013

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..800

D. Bevan, D. Levin, P. Nugent, J. Pantone, L. Pudwell, Pattern avoidance in forests of binary shrubs, arXiv preprint arXiv:1510.08036 [math.CO], 2015.

Gi-Sang Cheon, S.-T. Jin, L. W. Shapiro, A combinatorial equivalence relation for formal power series, Linear Algebra and its Applications, Available online 30 March 2015.

J. Schroeder, Generalized Schroeder numbers and the rotation principle, Journal of Integer Sequences 10(7).

R. A. Sulanke, A recurrence restricted by a diagonal condition: generalized Catalan arrays, Fibonacci Q., 27 (1989), 33-46.

FORMULA

G.f. A(z) satisfies A(z) = 1 + z(A(z)^3 + A(z)^4) a(n)= S_{3n+1}(n) - 3S_n(3n + 1), where S_a(b) are coordination numbers, ie the number of points in the a-dimensional cubic lattice Z^a having distance b in the L_1 norm.

Also a(n) = D(3n,n) - 3D(3n + 1,n-1) - 2D(3n,n-1), where D(a,b) are the Delannoy numbers, ie the number of paths with N, E and D steps from (0,0) to (a,b).

Conjecture: 3*n*(3*n-1)*(3*n+1)*(35*n^2-98*n+68) *a(n) +(-15610*n^5+67123*n^4-106824*n^3+77633*n^2-25514*n+3000)*a(n-1) +3*(n-2) *(3*n-4) *(3*n-5) *(35*n^2-28*n+5) *a(n-2)=0. - R. J. Mathar, Sep 06 2016

EXAMPLE

a(2)=14, because

01: NNNENNNE,

02: NNDNNNE,

03: NNNENND,

04: NNDNND,

05: NNNDNNE,

06: NNNDND,

07: NNNNENNE,

08: NNNNEND,

09: NNNNDNE,

10: NNNNDD,

11: NNNNNENE,

12: NNNNNED,

13: NNNNNDE,

14: NNNNNNEE

are all the paths from (0,0) to (2,6) with steps N,E and D weakly above y=3x.

MAPLE

Schr:=proc(n, m, l)(n-l*m+1)/m*sum(2^v*binomial(m, v)*binomial(n, v-1), v=1..m) end proc; where n=3m and l=3, also

Schr:=proc(n, m, l)(n-l*m+1)/(n+1)*sum(2^v*binomial(m-1, v-1)*binomial(n+1, v), v=0..m) end proc; where n=3m and l=3, also

Schr:=proc(n, m, l)(n-l*m+1)/m*sum(binomial(m, v)*binomial(n+v, m-1), v=0..m) end proc; where n=3m and l=3, also

Schr:=proc(n, m, l)(n-l*m+1)/(n+1)*sum(binomial(n+1, v)*binomial(m-1+v, n), v=0..n+1) end proc; where n=3m and l=3.

# alternative Maple program:

a:= proc(n) option remember; `if`(n<2, n+1,

      ((15610*n^5 -67123*n^4 +106824*n^3 -77633*n^2

       +25514*n-3000)*a(n-1) -(3*(n-2))*(3*n-4)*

       (3*n-5)*(35*n^2-28*n+5)*a(n-2)) / ((3*(3*n-1))

       *(3*n+1)*n*(35*n^2-98*n+68)))

    end:

seq(a(n), n=0..20);  # Alois P. Heinz, May 26 2015

MATHEMATICA

d[n_, k_] := Binomial[n+k, k] Hypergeometric2F1[-k, -n, -n-k, -1]; a[0] = 1; a[n_] = d[3n, n] - 3d[3n+1, n-1] - 2d[3n, n-1]; Table[a[n], {n, 0, 20}] (* Jean-Fran├žois Alcover, Feb 25 2017 *)

CROSSREFS

Cf. A027307 (the case y=2x).

Cf. A008288 (Delannoy numbers).

Cf. A008412 (4-dimensional coordination numbers).

Sequence in context: A052641 A157085 A073553 * A306081 A111424 A317356

Adjacent sequences:  A144094 A144095 A144096 * A144098 A144099 A144100

KEYWORD

easy,nonn

AUTHOR

Joachim Schroeder (schroderjd(AT)qwa.uovs.ac.za), Sep 10 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 19 02:01 EST 2018. Contains 317332 sequences. (Running on oeis4.)