

A097877


Triangle read by rows: T(n,k) is the number of Dyck npaths with k large components, 0 <= k <= n/2.


0



1, 1, 1, 1, 1, 4, 1, 12, 1, 1, 34, 7, 1, 98, 32, 1, 1, 294, 124, 10, 1, 919, 448, 61, 1, 1, 2974, 1576, 298, 13, 1, 9891, 5510, 1294, 99, 1, 1, 33604, 19322, 5260, 583, 16, 1, 116103, 68206, 20595, 2960, 146, 1, 1, 406614, 242602, 78954, 13704, 1006, 19, 1, 1440025
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

A prime Dyck path is one with exactly one return to ground level. Every nonempty Dyck path decomposes uniquely as a concatenation of prime Dyck paths, called its components. For example, UUDDUD has 2 components: UUDD and UD, of semilength 2 and 1 respectively. A large component is one of semilength >= 2.


LINKS

Table of n, a(n) for n=0..57.


FORMULA

G.f.: 2/(1 + t*(1  4*z)^(1/2) + (1  2*z)(1t)) = Sum_{n>=0, k>=0} T(n, k) z^n t^k satisfies (1z)*G = 1 + z*t*(CatalanGF[z]1)*G. The gf for Dyck paths (A000108) with z marking semilength is CatalanGF[z]:=(1  sqrt[1  4*z])/(2*z). Hence the gf for prime Dyck paths is z*CatalanGF[z] and the gf for nonUD prime Dyck paths is S(z):= z*CatalanGF[z]z. For fixed k, the gf for (T(n, k))_{n>=0} is S(z)^k/(1z)^(k+1). This is clear because 1/(1z) is the gf for allUD Dyck paths (including the empty one) and a Dyck path with k large components is a product (uniquely) of an allUD, a nonUD prime, an allUD, a nonUD prime, ... with k nonUD primes and k+1 allUDs.


EXAMPLE

Example: Table begins
\ k 0, 1, 2, ...
n
0  1
1  1
2  1, 1
3  1, 4,
4  1, 12, 1
5  1, 34, 7
6  1, 98, 32, 1
7  1, 294, 124, 10
8  1, 919, 448, 61, 1
T(3,1)=4 because each of the 5 Dyck paths of semilength 3 has one
large component except for UDUDUD, which has none.


CROSSREFS

The Fine distribution (A065600) counts Dyck paths by number of small components (= number of low peaks).
Sequence in context: A060923 A298362 A143952 * A225770 A019304 A072869
Adjacent sequences: A097874 A097875 A097876 * A097878 A097879 A097880


KEYWORD

nonn,tabl


AUTHOR

David Callan, Sep 21 2004


STATUS

approved



