Arrangements and Combinations · Catalan Numbers: Various Manifestations

Lesson 6

Nikolai Chukhin · Alexander S. Kulikov

Sequences with constraints. Let \(I(n)\) denote the number of sequences of non-negative integers \(a_{0} \le a_{1} \le \dotsb \le a_{n-1}\) such that \(a_{i} \le i\) for all \(0 \le i < n\). One such sequence is:

Let us draw its graph.

The condition \(a_{i} \le i\) means that these points do not fall into the upper triangle. Connecting them with lines yields Dyck paths!