Dyck paths

1. Definition

A Dyck path of size $n$ is

Clearly equivalently, one can see a Dyck path as

A Dyck path can also be identified with its Dyck word being $(0,1)$-sequence with $1$'s representing up steps and $0$'s representing down steps. Denote all Dyck paths of size $n$ by $\mathfrak{D}_n$.

2. Examples

3. Properties

4. Remarks

5. Statistics

Let $D$ be a Dyck path of size $n$.

The following statistics have individual pages with further explanations:

6. Maps

The following maps have individual pages with further explanations:

7. References

[Ath04]   C.A. Athanasiadis, Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes, Bull. London Math. Soc., 36 (2004), pp. 294-392.

[Deu99a]   E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999).

[Deu99b]   E. Deutsch, An involution on Dyck paths and its consequences, Discrete Math. 204 (1999), pp. 163-166.

[DS92]   A. Denise, R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math 137 (1992), 155-176.

[FH85]   J. Fürlinger, J. Hofbauer, q-Catalan numbers, J. Combin. Theory Ser. A 40 (1985), no. 2, 248-264.

[Hag08]   J. Haglund, The q,t-Catalan Numbers and the Space of Diagonal Harmonics, University Lecture Series, Amer. Math. Soc. 41 (2008) [ pdf ].

[Kra89]   C. Krattenthaler, Counting lattice paths with a linear boundary II, Sitz.ber. d. ÖAW Math.-naturwiss. Klasse 198 (1989), 171-199.

[LW02]   N. Loehr, G. Warrington, Square q, t-lattice paths and $\nabla(p_n)$, Transactions of the AMS 359(2) (2007).

[Mah15]   P.A. MacMahon, Combinatory analysis vol. 1, Cambridge University Press (1915).

[Sul99]   R.A. Sulanke, Constraint-sensitive Catalan path statistics having the Narayana distribution, Discrete Math. 204 (1999).

8. Sage examples

DyckPaths (last edited 2014-07-30 14:12:02 by ChristianStump)