0,6

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.

G.f.: 2/(1 + t*(1 - 4*z)^(1/2) + (1 - 2*z)(1-t)) = Sum_{n>=0, k>=0} T(n, k) z^n t^k satisfies (1-z)*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 non-UD 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/(1-z)^(k+1). This is clear because 1/(1-z) is the gf for all-UD Dyck paths (including the empty one) and a Dyck path with k large components is a product (uniquely) of an all-UD, a non-UD prime, an all-UD, a non-UD prime, ... with k non-UD primes and k+1 all-UDs.

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.

The Fine distribution (A065600) counts Dyck paths by number of small components (= number of low peaks).

Adjacent sequences: A097874 A097875 A097876 this_sequence A097878 A097879 A097880

Sequence in context: A135552 A109088 A060923 this_sequence A019304 A072869 A064279

nonn,tabl

David Callan (callan(AT)stat.wisc.edu), Sep 21 2004