Каталаны тоо¶

Каталаны тоо бол хэд хэдэн комбинаторикийн бодлогод, ихэвчлэн рекурсив тодорхойлогдсон объект агуулсан бодлогод ашигтай байдаг тооны дараалал юм.

Энэ дарааллыг 19-р зуунд амьдарч байсан Бельгийн математикч Каталан-ы нэрээр нэрлэсэн. (Үнэн хэрэгтээ үүнийг Каталанаас нэг зууны өмнө амьдарч байсан Эйлер мэддэг байсан).

Эхний хэдэн Каталаны тоо $C_n$ (тэгээс эхлэн):

$1, 1, 2, 5, 14, 42, 132, 429, 1430, \ldots$

Зарим комбинаторикийн бодлого дахь хэрэглээ¶

Каталаны тоо $C_n$ нь дараах зүйлсийн шийд юм

$n$ нээх ба $n$ хаах хаалтаас тогтох зөв хаалтын дарааллын тоо.
$n + 1$ навчтай үндэстэй бүрэн хоёртын модны тоо (оройнууд дугаарлагдаагүй). Хэрэв орой бүр нь хоёр хүүхэдтэй эсвэл хүүхэдгүй бол үндэстэй хоёртын мод бүрэн гэнэ.
$n + 1$ үржигдэхүүнийг бүрэн хаалтад авах аргын тоо.
$n + 2$ талтай гүдгэр олон өнцөгтийн гурвалжинчлалын тоо (өөрөөр хэлбэл диагональ ашиглан олон өнцөгтийг огтлолцохгүй гурвалжнуудад хуваах хуваалтын тоо).
Тойрог дээрх $2n$ цэгийг холбож $n$ огтлолцохгүй хөвч үүсгэх аргын тоо.
$n$ дотоод зангилаатай (өөрөөр хэлбэл дор хаяж нэг хүүхэдтэй зангилаа) изоморф биш бүрэн хоёртын модны тоо.
$n \times n$ хэмжээтэй квадрат торонд $(0, 0)$ цэгээс $(n, n)$ цэг хүртэлх, гол диагоналийн (өөрөөр хэлбэл $(0, 0)$-г $(n, n)$-тэй холбох) дээгүүр гарахгүй монотон торон замын тоо.
Стекээр эрэмбэлэгдэх боломжтой $n$ урттай сэлгэмэлийн тоо (өөрөөр хэлбэл $a_k < a_i < a_j$ байх $i < j < k$ индекс байхгүй бол, зөвхөн тэр үед л дахин байрлуулалт стекээр эрэмбэлэгддэгийг харуулж болно).
$n$ элементтэй олонлогийн огтлолцохгүй хуваалт-ын тоо.
$1 \ldots n$ шатыг $n$ тэгш өнцөгт ашиглан бүрхэх аргын тоо (Шат нь $n$ баганаас тогтох ба $i$-р багана $i$ өндөртэй).

Тооцоолол¶

Каталаны тооны хоёр томьёо бий: Рекурсив ба аналитик. Дээр дурдсан бүх бодлого эквивалент (ижил шийдтэй) гэж бид үздэг тул доорх томьёонуудын баталгааны хувьд хийхэд хамгийн хялбар даалгаврыг сонгоно.

Рекурсив томьёо¶

$$C_0 = C_1 = 1$$

$$C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} , {n} \geq 2$$

Рекуррент томьёог зөв хаалтын дарааллын бодлогоос амархан гаргаж болно.

Хамгийн зүүн талын нээх хаалт $l$ нь дарааллыг 2 хэсэгт хуваах тодорхой хаах хаалт $r$-т харгалзах ба эдгээр нь эргээд зөв хаалтын дараалал байх ёстой. Тиймээс томьёо мөн 2 хэсэгт хуваагдана. Хэрэв бид $k = {r - l - 1}$ гэж тэмдэглэвэл тогтмол $r$-ийн хувьд яг $C_k C_{n-1-k}$ ийм хаалтын дараалал байна. Үүнийг зөвшөөрөгдөх бүх $k$-ээр нийлбэрлэвэл бид $C_n$-ийн рекуррент хамаарлыг олж авна.

Үүнийг мөн дараах байдлаар бодож болно. Тодорхойлолтоор $C_n$ нь зөв хаалтын дарааллын тоог илэрхийлнэ. Одоо дарааллыг $k$ ба ${n - k}$ урттай 2 хэсэгт хувааж болох ба тус бүр нь зөв хаалтын дараалал байх ёстой. Жишээ:

$( ) ( ( ) )$-г $( )$ ба $( ( ) )$ болгон хувааж болох боловч $( ) ($ ба $( ) )$ болгон хувааж болохгүй. Дахин зөвшөөрөгдөх бүх $k$-ээр нийлбэрлэвэл бид $C_n$-ийн рекуррент хамаарлыг олж авна.

C++ implementation¶

const int MOD = ....
const int MAX = ....
int catalan[MAX];
void init() {
    catalan[0] = catalan[1] = 1;
    for (int i=2; i<=n; i++) {
        catalan[i] = 0;
        for (int j=0; j < i; j++) {
            catalan[i] += (catalan[j] * catalan[i-j-1]) % MOD;
            if (catalan[i] >= MOD) {
                catalan[i] -= MOD;
            }
        }
    }
}

Аналитик томьёо¶

$$C_n = \frac{1}{n + 1} {\binom{2n}{n}}$$

(энд $\binom{n}{k}$ нь ердийн биномын коэффициент буюу $n$ объектын олонлогоос $k$ объект сонгох аргын тоог илэрхийлнэ).

Дээрх томьёог квадрат тор дахь монотон замын бодлогоос амархан гаргаж болно. $n \times n$ хэмжээтэй тор дахь монотон замын нийт тоог $\binom{2n}{n}$ өгнө.

Одоо бид гол диагоналийг гатлах монотон замын тоог тоолно. Гол диагоналийг гатлах ийм замуудыг авч үзэж, тэдгээрт диагоналийн дээгүүр байгаа эхний ирмэгийг ол. Энэ ирмэгийн дараа замыг диагональ тухайд бүрэн тусгал. Үр дүн нь үргэлж $(n - 1) \times (n + 1)$ тор дахь монотон зам байна. Нөгөө талаас $(n - 1) \times (n + 1)$ тор дахь дурын монотон зам заавал диагоналийг огтлох ёстой. Иймээс бид $n \times n$ тор дахь гол диагоналийг гатлах бүх монотон замыг тоолов.

$(n - 1) \times (n + 1)$ тор дахь монотон замын тоо нь $\binom{2n}{n-1}$. Ийм замуудыг "муу" зам гэж нэрлэе. Үр дүнд нь гол диагоналийг гатлахгүй монотон замын тоог олохын тулд бид дээрх "муу" замуудыг хасаж, томьёог олж авна:

$$C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n + 1} \binom{2n}{n} , {n} \geq 0$$