A023425 Generalized Catalan numbers: a(0) = 1, a(n) = a(n-1) + Sum_{k=1..n-4} a(k) * a(n-k).

1, 1, 1, 1, 1, 2, 5, 13, 34, 90, 241, 652, 1780, 4899, 13581, 37893, 106340, 299978, 850187, 2419788, 6913658, 19822439, 57015620, 164476023, 475752469, 1379553027, 4009532279, 11678165796, 34081307147, 99646051271, 291845778020, 856147139606, 2515368741707, 7400713869808, 21803597196231

Offset: 0

Author

Olivier Gérard

Keywords

• nonn
• easy

Comments

a(n) = number of bargraphs of semiperimeter n-2 with no valleys of width 1 (i.e., no DHU configurations, where U=(0,1), H=(1,0), D=(0,-1)). Example: a(8) = 34 because among the 35 (=A082582(6)) bargraphs of semiperimeter 6 only the one corresponding to the composition [2,1,2] has a valley of width 1. - Emeric Deutsch, Aug 11 2016

Crossrefs

Cf. A000108, A001006, A004148, A006318, A082582.

Programs

Maple

A023425 := proc(n)
    option remember;
    if n = 0 then
        1;
    else
        procname(n-1)+add(procname(k)*procname(n-k),k=1..n-4) ;
    end if;
end proc: # R. J. Mathar, May 01 2015

Mathematica

a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-k ], {k, 1, n-4} ];

Formula

The sequence a(n-3) (for n>=3) has the g.f. 1/G(0) where G(k) = 1 - q/(1 - q - q^2 - q^3 / G(k+1) ). - Joerg Arndt, Dec 06 2014

n*a(n) +2*(-2*n+3)*a(n-1) +2*(n-3)*a(n-2) +(2*n-9)*a(n-3) +(n-6)*a(n-4) +(2*n-15)*a(n-5) +(n-9)*a(n-6)=0. - R. J. Mathar, May 01 2015

G.f.: (3+z^2+z^3-sqrt((1-2*z-3*z^2-z^3)*(1-2*z+z^2-z^3)))/2. - Emeric Deutsch, May 24 2016

The g.f. g(x) satisfies g(x) = 1+x*g(x)+(g(x)-1)*(g(x)-x^3-x^2-x-1) and 3*x^5+5*x^4+7*x^3+6*x^2+2*x-3+(-3*x^5-5*x^4-2*x^3-3*x^2-2*x+2)*g(x)+(x^6+2*x^5+x^4+2*x^3+2*x^2-4*x+1)*g'(x). - Robert Israel, May 25 2016