|
%I #92 Jan 09 2024 11:03:25
%S 1,2,14,134,1482,17818,226214,2984206,40503890,561957362,7934063678,
%T 113622696470,1646501710362,24098174350986,355715715691350,
%U 5289547733908510,79163575684710818,1191491384838325474
%N 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.
%C 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.
%C 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
%C 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
%D 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.
%H Alois P. Heinz, <a href="/A144097/b144097.txt">Table of n, a(n) for n = 0..800</a>
%H D. Bevan, D. Levin, P. Nugent, J. Pantone, and L. Pudwell, <a href="http://arxiv.org/abs/1510.08036">Pattern avoidance in forests of binary shrubs</a>, arXiv preprint arXiv:1510.08036 [math.CO], 2015.
%H B. Drake, <a href="http://people.brandeis.edu/~gessel/homepage/students/drakethesis.pdf">An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.6.9)</a>, A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.
%H Gi-Sang Cheon, S.-T. Jin, and L. W. Shapiro, <a href="http://dx.doi.org/10.1016/j.laa.2015.03.015">A combinatorial equivalence relation for formal power series</a>, Linear Algebra and its Applications, Available online 30 March 2015.
%H J. Schroeder, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Schroder/schroder45.html">Generalized Schroeder numbers and the rotation principle</a>, Journal of Integer Sequences 10(7).
%H R. A. Sulanke, <a href="http://www.fq.math.ca/Scanned/27-1/sulanke.pdf">A recurrence restricted by a diagonal condition: generalized Catalan arrays</a>, Fibonacci Q., 27 (1989), 33-46.
%H Lin Yang, Yu-Yuan Zhang, and Sheng-Liang Yang, <a href="https://doi.org/10.1016/j.laa.2023.12.021">The halves of Delannoy matrix and Chung-Feller properties of the m-Schröder paths</a>, Linear Alg. Appl. (2024).
%H Sheng-liang Yang and Mei-yang Jiang, <a href="https://journal.lut.edu.cn/EN/abstract/abstract528.shtml">Pattern avoiding problems on the hybrid d-trees</a>, J. Lanzhou Univ. Tech., (China, 2023) Vol. 49, No. 2, 144-150. (in Mandarin; improperly cited as A144079)
%F 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.
%F 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).
%F 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
%F From _Seiichi Manyama_, Jul 25 2020: (Start)
%F a(n) = Sum_{k=0..n} binomial(n,k) * binomial(3*n+k+1, n)/(3*n+k+1).
%F a(n) = (1/n) * Sum_{k=1..n} 2^k * binomial(n,k) * binomial(3*n,k-1) for n > 0. (End)
%F 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
%F 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
%F From _Peter Bala_, Jun 16 2023: (Start)
%F 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.
%F 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 ).
%F a(n) = 2*hypergeom([1 - n, -3*n], [2], 2) for n >= 1. (End)
%F 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
%e a(2)=14, because
%e 01: NNNENNNE,
%e 02: NNDNNNE,
%e 03: NNNENND,
%e 04: NNDNND,
%e 05: NNNDNNE,
%e 06: NNNDND,
%e 07: NNNNENNE,
%e 08: NNNNEND,
%e 09: NNNNDNE,
%e 10: NNNNDD,
%e 11: NNNNNENE,
%e 12: NNNNNED,
%e 13: NNNNNDE,
%e 14: NNNNNNEE
%e are all the paths from (0,0) to (2,6) with steps N,E and D weakly above y=3x.
%p 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
%p 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
%p 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
%p 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.
%p # alternative Maple program:
%p a:= proc(n) option remember; `if`(n<2, n+1,
%p ((15610*n^5 -67123*n^4 +106824*n^3 -77633*n^2
%p +25514*n-3000)*a(n-1) -(3*(n-2))*(3*n-4)*
%p (3*n-5)*(35*n^2-28*n+5)*a(n-2)) / ((3*(3*n-1))
%p *(3*n+1)*n*(35*n^2-98*n+68)))
%p end:
%p seq(a(n), n=0..20); # _Alois P. Heinz_, May 26 2015
%t 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 *)
%o (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
%o (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
%Y Cf. A027307 (the case y=2x), A008288 (Delannoy numbers), A008412 (4-dimensional coordination numbers).
%Y This appears to equal 2*A243675. - _N. J. A. Sloane_, Mar 28 2021
%Y 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
%K easy,nonn
%O 0,2
%A Joachim Schroeder (schroderjd(AT)qwa.uovs.ac.za), Sep 10 2008
|
