OFFSET
0,2
COMMENTS
These are the 3-Schroeder numbers according to Yang-Jiang (2021). - N. J. A. Sloane, Mar 28 2021
Equals row sums of triangle A104978 which has g.f. F(x,y) that satisfies: F = 1 + x*F^2 + x*y*F^3. - Paul D. Hanna, Mar 30 2005
a(n) counts ordered complete ternary trees with 2*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]. An example is given below. - Peter Bala, Sep 29 2011
a(n) for n >= 1 is the number of compact coalescent histories for matching lodgepole gene trees and species trees with n cherries and 2n+1 leaves. - Noah A Rosenberg, Jun 21 2022
a(n) is the maximum number of distinct sets that can be obtained as complete parenthesizations of "S_1 union S_2 intersect S_3 union S_4 intersect S_5 union ... union S_{2*n} intersect S_{2*n+1}", where n union and n intersection operations alternate, starting with a union, and S_1, S_2, ... , S_{2*n+1} are sets. - Alexander Burstein, Nov 22 2023
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..200
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
Gi-Sang Cheon, Sung-Tae Jin and Louis W. Shapiro, A combinatorial equivalence relation for formal power series, Linear Algebra and its Applications, Available online 30 March 2015.
Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.
Filippo Disanto and Noah A. Rosenberg, Enumeration of compact coalescent histories for matching gene trees and species trees, J. Math. Biol 78 (2019), 155-188.
Brian 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.
V. I. Kachalov, On one nonlinear spectral problem, J. Math. Sci., 2026.
Yvonne Wakuthii Kariuki, Enumeration of skew 2-Dyck paths, non-decreasing 2-plane trees, non-decreasing 2-noncrossing trees and related combinatorial structures, Ph. D. Thesis, Moi Univ. (Kenya, 2025). See p. 17.
Elżbieta Liszewska and Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.
Dean Rubine, Computing the 4D Geode, arXiv:2512.21785 [math.CO], 2025. See p. 4.
Zhen-ji Tian and Shu-ping Dou, Enumerations of 3 di-sk trees, J. Lanzhou Univ. Tech. 50(6) (2024), 144-149. See p. 146. [Broken link]
Joost Winter, Marcello M. Bonsangue and Jan J. M. M. Rutten, Context-free coalgebras, 2013.
Jun Yan, Lattice paths enumerations weighted by ascent lengths, arXiv:2501.01152 [math.CO], 2025. See p. 11.
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. See Table 1.
Sheng-liang Yang and Mei-yang Jiang, Pattern avoiding problems on the hybrid d-trees, J. Lanzhou Univ. Tech. 49(2) (China, 2023), 144-150. (in Mandarin) [Broken link]
Anssi Yli-Jyrä and Carlos Gómez-Rodríguez, Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing, arXiv:1706.03357 [cs.CL], 2017.
Jian Zhou, On Some Mathematics Related to the Interpolating Statistics, arXiv:2108.10514 [math-ph], 2021.
FORMULA
G.f.: (2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3.
a(n) = (1/n) * Sum_{i=0..n-1} 2^(i+1)*binomial(2*n, i)*binomial(n, i+1), n>0.
a(n) = 2*A034015(n-1), n>0.
a(n) = Sum_{k=0..n} C(2*n+k, n+2*k)*C(n+2*k, k)/(n+k+1). - Paul D. Hanna, Mar 30 2005
Given g.f. A(x), y=A(x)x satisfies 0=f(x, y) where f(x, y)=x(x-y)+(x+y)y^2 . - Michael Somos, May 23 2005
Series reversion of x(Sum_{k>=0} a(k)x^k) is x(Sum_{k>=0} A085403(k)x^k).
G.f. A(x) satisfies A(x)=A006318(x*A(x)). - Vladimir Kruchinin, Apr 18 2011
The function B(x) = x*A(x^2) satisfies B(x) = x+x*B(x)^2+B(x)^3 and hence B(x) = compositional inverse of x*(1-x^2)/(1+x^2) = x+2*x^3+10*x^5+66*x^7+.... Let f(x) = (1+x^2)^2/(1-4*x^2+x^4) and let D be the operator f(x)*d/dx. Then a(n) equals 1/(2*n+1)!*D^(2*n)(f(x)) evaluated at x = 0. For a refinement of this sequence see A196201. - Peter Bala, Sep 29 2011
D-finite with recurrence: 2*n*(2*n+1)*a(n) = (46*n^2-49*n+12)*a(n-1) - 3*(6*n^2-26*n+27)*a(n-2) - (n-3)*(2*n-5)*a(n-3). - Vaclav Kotesovec, Oct 08 2012
a(n) ~ sqrt(50+30*sqrt(5))*((11+5*sqrt(5))/2)^n/(20*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 08 2012. Equivalently, a(n) ~ phi^(5*n + 1) / (2 * 5^(1/4) * sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 07 2021
a(n) = 2*hypergeom([1 - n, -2*n], [2], 2) for n >= 1. - Peter Luschny, Nov 08 2021
From Peter Bala, Jun 16 2023: (Start)
P-recursive: n*(2*n + 1)*(5*n - 7)*a(n) = (110*n^3 - 264*n^2 + 181*n - 36)*a(n-1) + (n - 2)*(2*n - 3)*(5*n - 2)*a(n-2) with a(0) = 1 and a(1) = 2.
The g.f. A(x) = 1 + 2*x + 10*x^2 + 66*x^3 + ... satisfies A(x)^2 = (1/x) * the series reversion of x*((1 - x)/(1 + x))^2.
Define b(n) = [x^(2*n)] ( (1 + x)/(1 - x) )^n = (1/2) * [x^n] ((1 + x)/(1 - x))^(2*n) = A103885(n). Then A(x) = exp( Sum_{n >= 1} b(n)*x^n/n ). (End)
a(n) = (1/n) * Sum_{k=0..n-1} (-1)^k * 2^(n-k) * binomial(n,k) * binomial(3*n-k,n-1-k) for n > 0. - Seiichi Manyama, Aug 09 2023
EXAMPLE
a(2) = 10. Internal vertices colored either b(lack) or w(hite); 5 uncolored leaf vertices shown as o.
........b...........b.............w...........w.....
......./|\........./|\.........../|\........./|\....
....../.|.\......./.|.\........./.|.\......./.|.\...
.....b..o..o.....o..b..o.......w..o..o.....o..w..o..
..../|\............/|\......../|\............/|\....
.../.|.\........../.|.\....../.|.\........../.|.\...
..o..o..o........o..o..o....o..o..o........o..o..o..
....................................................
........b...........b.............w...........w.....
......./|\........./|\.........../|\........./|\....
....../.|.\......./.|.\........./.|.\......./.|.\...
.....w..o..o.....o..w..o.......b..o..o.....o..b..o..
..../|\............/|\......../|\............/|\....
.../.|.\........../.|.\....../.|.\........../.|.\...
..o..o..o........o..o..o....o..o..o........o..o..o..
....................................................
........b...........w..........
......./|\........./|\.........
....../.|.\......./.|.\........
.....o..o..w.....o..o..b.......
........../|\........./|\......
........./.|.\......./.|.\.....
........o..o..o.....o..o..o....
...............................
From Alexander Burstein, Feb 14 2025: (Start)
a(2) = 10 as the maximum number of distinct sets obtained as complete parenthesizations of S_1 u(nion) S_2 (i)n(tersect) S_3 u(nion) S_4 (i)n(tersect) S_5:
S_1 u (S_2 n (S_3 u (S_4 n S_5))),
S_1 u (S_2 n ((S_3 u S_4) n S_5)) = S_1 u ((S_2 n (S_3 u S_4)) n S_5),
S_1 u ((S_2 n S_3) u (S_4 n S_5)) = (S_1 u (S_2 n S_3)) u (S_4 n S_5),
S_1 u (((S_2 n S_3) u S_4) n S_5),
(S_1 u S_2) n (S_3 u (S_4 n S_5)),
(S_1 u S_2) n ((S_3 u S_4) n S_5) = ((S_1 u S_2) n (S_3 u S_4)) n S_5,
((S_1 u S_2) n S_3) u (S_4 n S_5),
(S_1 u (S_2 n (S_3 u S_4))) n S_5,
(S_1 u ((S_2 n S_3) u S_4)) n S_5 = ((S_1 u (S_2 n S_3)) u S_4) n S_5,
(((S_1 u S_2) n S_3) u S_4) n S_5. (End)
MATHEMATICA
a[n_] := ((n+1)*(2n)!*Hypergeometric2F1[-n, 2n+1, n+2, -1]) / (n+1)!^2;
Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Nov 14 2011, after Pari *)
a[n_] := If[n == 0, 1, 2*Hypergeometric2F1[1 - n, -2 n, 2, 2]];
Table[a[n], {n, 0, 19}] (* Peter Luschny, Nov 08 2021 *)
PROG
(PARI) a(n)=if(n<1, n==0, sum(i=0, n-1, 2^(i+1)*binomial(2*n, i)*binomial(n, i+1))/n)
(PARI) a(n)=sum(k=0, n, binomial(2*n+k, n+2*k)*binomial(n+2*k, k)/(n+k+1)) \\ Paul D. Hanna
(PARI) a(n)=sum(k=0, n, binomial(n, k)*binomial(2*n+k+1, n)/(2*n+k+1) ) /* Michael Somos, May 23 2005 */
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved