A144097 The 4-Schroeder numbers: 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.

1, 2, 14, 134, 1482, 17818, 226214, 2984206, 40503890, 561957362, 7934063678, 113622696470, 1646501710362, 24098174350986, 355715715691350, 5289547733908510, 79163575684710818, 1191491384838325474

Offset: 0

Author

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

Keywords

• easy
• nonn

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

a(n) equals the number of ordered complete 4-ary trees with 3*n + 1 leaves, where the internal vertices come in two colors and such that each vertex and its rightmost child have different colors. See Drake, Example 1.6.9. - Peter Bala, Apr 30 2023

Examples

			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.
		

References

• Sheng-Liang Yang and Mei-yang Jiang, The m-Schröder paths and m-Schröder numbers, Disc. Math. (2021) Vol. 344, Issue 2, 112209. doi:10.1016/j.disc.2020.112209. See Table 1.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..800
• D. Bevan, D. Levin, P. Nugent, J. Pantone, and L. Pudwell, Pattern avoidance in forests of binary shrubs, arXiv preprint arXiv:1510.08036 [math.CO], 2015.
• B. Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.6.9), A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.
• Gi-Sang Cheon, S.-T. Jin, and 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.
• Jun Yan, Lattice paths enumerations weighted by ascent lengths, arXiv:2501.01152 [math.CO], 2025. See p. 11.
• Lin Yang, Yu-Yuan Zhang, and Sheng-Liang Yang, The halves of Delannoy matrix and Chung-Feller properties of the m-Schröder paths, Linear Alg. Appl. (2024).
• Sheng-liang Yang and Mei-yang Jiang, Pattern avoiding problems on the hybrid d-trees, J. Lanzhou Univ. Tech., (China, 2023) Vol. 49, No. 2, 144-150. (in Mandarin; improperly cited as A144079)

Crossrefs

Cf. A027307 (the case y=2x), A008288 (Delannoy numbers), A008412 (4-dimensional coordination numbers).

This appears to equal 2*A243675. - N. J. A. Sloane, Mar 28 2021

The sequences listed in Yang-Jiang's Table 1 appear to be A006318, A001003, A027307, A034015, A144097, A243675, A260332, A243676. - N. J. A. Sloane, Mar 28 2021

Programs

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

PARI

{a(n) = sum(k=0, n, binomial(n, k) * binomial(3*n+k+1, n)/(3*n+k+1))} \\ Seiichi Manyama, Jul 25 2020

PARI

{a(n) = if(n==0, 1, sum(k=1, n, 2^k*binomial(n, k) * binomial(3*n, k-1)/n))} \\ Seiichi Manyama, Jul 25 2020

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, i.e., 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, i.e., the number of paths with N, E and D steps from (0,0) to (a,b).

D-finite with recurrence 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

From Seiichi Manyama, Jul 25 2020: (Start)

a(n) = Sum_{k=0..n} binomial(n,k) * binomial(3*n+k+1, n)/(3*n+k+1).

a(n) = (1/n) * Sum_{k=1..n} 2^k * binomial(n,k) * binomial(3*n,k-1) for n > 0. (End)

a(n) ~ sqrt(12160 + 3853*sqrt(10)) * 3^(3*n - 9/2) / (2*sqrt(5*Pi) * n^(3/2) * (223 - 70*sqrt(10))^(n - 1/2)). - Vaclav Kotesovec, Jul 31 2021

Series reversion of x*(1 - x^3)/(1 + x^3) = x + 2*x^4 + 14*x^7 + 134*x^10 + ... = Sum_{n >= 0} a(n)*x^(3*n+1). - Peter Bala, Apr 30 2023

From Peter Bala, Jun 16 2023: (Start)

The g.f. A(x) = 1 + 2*x + 14*x^2 + 134*x^3 + ... satisfies A(x)^3 = (1/x) * the series reversion of ((1 - x)/(1 + x))^3.

Define b(n) = [x^(3*n)] ( (1 + x)/(1 - x) )^n = (1/3) * [x^n] ((1 + x)/(1 - x))^(3*n) = A333715(n). Then A(x) = exp( Sum_{n >= 1} b(n)*x^n/n ).

a(n) = 2*hypergeom([1 - n, -3*n], [2], 2) for n >= 1. (End)

a(n) = (1/n) * Sum_{k=0..n-1} (-1)^k * 2^(n-k) * binomial(n,k) * binomial(4*n-k,n-1-k) for n > 0. - Seiichi Manyama, Aug 09 2023