|
|
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.
|
|
20
|
|
|
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
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
|
|
|
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
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
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:
|
|
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
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Joachim Schroeder (schroderjd(AT)qwa.uovs.ac.za), Sep 10 2008
|
|
STATUS
|
approved
|
|
|
|