Монгол Бодлогын Сан

Заавар: Зөвхөн рекурент харьцааг ол.

Бодолт: $\sigma\in S_n$ нь бодлогын нөхцөлийг хангах сэлгэмэл байг $\sigma(n)=i$, $i\neq n$ байг. Тэгвэл $\sigma(i)=n$ байх бодлогын нөхцөлийг хангах сэлгэмэлийн тоо $N_{n-2}(0)$ байна.

Одоо $\sigma(n)=i$, $\sigma(i)\neq n$ байх бодлогын нөхцөлийг хангах сэлгэмэлийн тоог олъё. $\sigma(j)=n$ байх $j$-ийн хувьд $\sigma^\ast(j)=i$ ба бусад $j\in[n-1]$ тооны хувьд $\sigma^\ast(j)=\sigma(j)\neq j$ гэж тодорхойлогдох $\sigma^\ast\colon[n-1]\to[n-1]$ нь бодлогын нөхцөлийг хангана. Учир нь $\sigma^\ast(j)=i$ ба $j=i$ бол $\sigma(i)=\sigma(j)=n$ болж зөрчил үүснэ.

Нөгөө талаас энэхүү $\sigma\to\sigma^\ast$ буулгалт нь ХНУ-тай байна.

Инъектив болохыг баталъя. Эсрэгээс нь $\sigma\neq\mu$ ба $\sigma^\ast=\mu^\ast$ гэвэл ямар нэг $k$ дугаарын хувьд $\sigma^\ast(k)=\mu^\ast(k)$ ба $\sigma(k)\neq\mu(k)$ байна. $\sigma(i)=\mu(i)=n$ ба $\sigma(j_1)=n$, $\mu(j_2)=n$ гэвэл

1. $k\neq j_1$ ба $k\neq j_2$ гэвэл $$\sigma(k)=\sigma^\ast(k)=\mu^\ast(k)=\mu(k)$$ болж зөрчил үүснэ.
2. $k=j_1=j_2$ гэвэл $\sigma(j_1)=\mu(j_2)=i$ буюу $\sigma(k)=\mu(k)=i$ болж зөрчил үүснэ.
3. $k=j_1$, $k\neq j_2$ гэвэл $(\sigma^\ast)^{-1}(i)=j_1\neq j_2=(\mu^\ast)^{-1}(i)$ болж $\sigma^\ast=\mu^\ast$ гэдэгт зөрчиж байна.

Одоо сюръектив гэдгийг баталъя. $\sigma^\ast\colon[n-1]\to[n-1]$ сэлгэмэл бодлогын нөхцөлийг хангадаг гэе. Тэгвэл $$\sigma(k)=\begin{cases} n, & \sigma^\ast(k)=i\\ i, & k=n\\ \sigma^\ast(k), & \text{бусад} \end{cases}$$ гэж тодорхойлогдох сэлгэмэл нь $\sigma^\ast$-ийн эх дүр болно. Иймд $\sigma(n)=i$, $\sigma(i)\neq n$ байх бодлогын нөхцөлийг хангах сэлгэмэлийн тоо $N_{n-1}(0)$ болов. Эндээс $$N_n(0)=(n-1)\big(N_{n-1}(0)+N_{n-2}(0)\big)$$ болох нь батлагдлаа.