A025243 a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ... + a(n-3)*a(3) for n >= 4, with initial terms 1, 2, 1, 1.

1, 2, 1, 1, 3, 6, 14, 33, 79, 194, 482, 1214, 3090, 7936, 20544, 53545, 140399, 370098, 980226, 2607242, 6961462, 18652112, 50133616, 135140598, 365254226, 989614976, 2687312752, 7312725944, 19938170096, 54460115308, 149007155356, 408341969073

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

Comments

a(n) is the number of Dyck (n-1)-paths that contain no DUDU's and no UUDD's (n>=3). For example, a(5)=3 counts UUUDUDDD, UDUUDUDD, UUDUDDUD. - David Callan, Sep 25 2006

Apart from the first three terms, the total number of bargraphs of semiperimeter n with no levels for n>=2. The sequence begins: 1, 3, 6, 14, 33, ... - Arnold Knopfmacher, Nov 01 2016

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..2192
• Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.
• Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.
• Paul Barry, Elliptic Curves, Riordan arrays and Lattice Paths, arXiv:2507.16765 [math.CO], 2025. See p. 6.
• Aubrey Blecher, Charlotte Brennan, and Arnold Knopfmacher, Levels in bargraphs, Ars Mathematica Contemporanea, 9 (2015), 287-300.

Programs

Magma

a:=[1,2,1]; for n in [4..35] do Append(~a,&+[a[k]*a[n-k]:k in [1..n-3]] ); end for; a; // Marius A. Burtea, Jan 02 2020

Mathematica

CoefficientList[Series[(1 + x + 2 x^2 - Sqrt[1 - 2 x - 3 x^2 + 4 x^4]) / 2 / x, {x, 0, 40}], x] (* Vincenzo Librandi, Feb 15 2015 *)

PARI

a(n)=polcoeff((x+2*x^2-sqrt(1-2*x-3*x^2+4*x^4+x*O(x^n)))/2,n)

Formula

G.f.: (1 + x + 2*x^2 - sqrt(1 - 2*x - 3*x^2 + 4*x^4))/2. - Michael Somos, Jun 08 2000

D-finite with recurrence n*(n+1)*a(n) +n*(n+1)*a(n-1) +(n^2+n+12)*a(n-2) +(-29*n^2+85*n+78)*a(n-3) +2*(-13*n^2+56*n+33)*a(n-4) +12*(n+1)*(n-7)*a(n-5) +8*(5*n+3)*(n-8)*a(n-6)=0. - R. J. Mathar, Feb 25 2015