Монгол Бодлогын Сан
Эх хэлээрээ суралцаж, эх хэлээрээ мэдлэгээ түгээе.
Бодлого №16277
Тойрог дээр $2n$ цэг авав. Тэднийг үл огтлолцох $n$ хөвчөөр нь хэчнээн янзаар холбож болох вэ?
Бодлогын төрөл: Уламжлалт
Бодлогыг оруулсан: Балхүүгийн Батбаясгалан
Бодолт
Заавар:
Бодолт: 1-г зөвхөн тэгш дугаартай хөвчтэй л холбож чадна, тэр нь
$A_1A_{2k}$ хөвч байг $A_1A_{2k}$-ийн нэг нум дээр $2k-2$ цэг,
нөгөө нум дээр нь $2n-2k$ цэг байх тул $F_{2n}=\sum\limits_{k=1}^n
F_{2k-2}F_{2n-2k}$ болно. $F_0=1$.
$c_n=F_{2n}$ гэвэл $$c_n=\sum_{k=1}^{n}c_{k-1}c_{n-k}=\sum_{k=0}^{n-1}c_{k}c_{n-k-1}$$ гээд Каталаны тоо болно. Иймд $F_{2n}=\dfrac{1}{n+1}\dbinom{2n}{n}$.
$c_n=F_{2n}$ гэвэл $$c_n=\sum_{k=1}^{n}c_{k-1}c_{n-k}=\sum_{k=0}^{n-1}c_{k}c_{n-k-1}$$ гээд Каталаны тоо болно. Иймд $F_{2n}=\dfrac{1}{n+1}\dbinom{2n}{n}$.