A034015 Small 3-Schroeder numbers: a(n) = A027307(n+1)/2.

1, 5, 33, 249, 2033, 17485, 156033, 1431281, 13412193, 127840085, 1235575201, 12080678505, 119276490193, 1187542872989, 11909326179841, 120191310803937, 1219780566014657, 12440630635406245, 127446349676475425, 1310820823328281561, 13530833791486094769

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Series reversion of x*(Sum_{k>=0} a(k)(-x^2)^k) is Sum_{k odd} C(k)x^k where C() is Catalan numbers A000108.

Series reversion of x*(Sum_{k>=0} a(k)(-x)^k) is A000337(x). (Michael Somos)

This sequence should really have started with a(0)=1, a(1)=1, a(2)=5, a(3)=33, ..., but the present offset is too well-established. - N. J. A. Sloane, Mar 28 2021

This is the number of hypoplactic classes of 2-parking functions of size n+1. - Jun Yan, Apr 13 2024

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..500
• J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014-2020.
• Jun Yan, Results on pattern avoidance in parking functions, arXiv preprint arXiv:2404.07958 [math.CO], 2024. See Theorem 4.4.

Crossrefs

Part of a family indexed by m: m=2 (A001003), m=3 is this sequence, m=4 is A243675, ....

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

Apart from the first term, this is A027307/2. - N. J. A. Sloane, Mar 28 2021

Programs

Maple

a:= proc(n) option remember; `if`(n<2, 4*n+1,
      ((110*n^3+66*n^2-17*n-9) *a(n-1)
       +(n-1)*(2*n-1)*(5*n+3) *a(n-2)) /
      ((2*n+3)*(5*n-2)*(n+1)))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 22 2014

Mathematica

a[n_] := If[n<0, 0, Sum[2^i*Binomial[2*n+2, i]*Binomial[n+1, i+1]/(n+1), {i, 0, n}]]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Oct 13 2014, after PARI *)
a[n_] := Hypergeometric2F1[-n, -2 (n + 1), 2, 2];
Table[a[n], {n, 0, 20}]  (* Peter Luschny, Nov 08 2021 *)

PARI

a(n)=if(n<0,0,sum(i=0,n,2^i*binomial(2*n+2,i)*binomial(n+1,i+1))/(n+1))

Formula

a(n) = Sum_{i=0..n} Sum_{j=0..i} (-2)^(n-i)*binomial(i,j)*binomial(2i+j, n)*binomial(n+1,i)/(n+1) (conjectured). - Michael D. Weiner, May 25 2017

Yang & Jiang (2021) give an explicit formula for a(n) in Theorems 2.4 and 2.9. - N. J. A. Sloane, Mar 28 2021 [This formula is: a(n) = (1/(n + 1)) * Sum_{k=1..n+1} binomial(2*n + 2, k - 1) * binomial(n + 1, k)*2^(k - 1). - Jun Yan, Apr 13 2024]

a(n) = hypergeom([-n, -2*(n + 1)], [2], 2). - Peter Luschny, Nov 08 2021

a(n) ~ phi^(5*n + 6) / (4 * 5^(1/4) * sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Nov 08 2021

D-finite with recurrence +2*(2*n+3)*(n+1)*a(n) +(-46*n^2-43*n-9)*a(n-1) +3*(6*n^2-14*n+7)*a(n-2) +(2*n-3)*(n-2)*a(n-3)=0. - R. J. Mathar, Aug 01 2022

Let D(n) be the set of 2-Dyck paths that have n up-steps of size 2 and 2n down-steps of size 1 and never go below the x-axis. For every d in D(n), let peak(d) be the number of peaks in d. Then a(n) = Sum_{d in D(n+1)}2^(peak(d) - 1). - Jun Yan, Apr 13 2024

a(n) = (-1)^(n) * Jacobi_P(n, 1, n+2, -3)/(n+1). - Peter Bala, Sep 08 2024