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,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

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

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.

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)

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

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

Prog

(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

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

Sequence in context: A052641 A157085 A073553 * A306081 A326886 A111424

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