Монгол Бодлогын Сан
Эх хэлээрээ суралцаж, эх хэлээрээ мэдлэгээ түгээе.
Хосын тухай бодлого
а) Гэр бүлийн $n$ хосыг дугуй ширээ тойруулан суулгахад нэг гэр бүлийн хос зэрэгцэж суугаагүй байх боломжийн тоог ол ($n=6$ үед тоон хариуг ол).
б) а) тохиолдлыг эрэгтэйчүүд ба эмэгтэйчүүд нь сөөлжлөн суусан байх үед бод.
Бодлогын төрөл: Уламжлалт
Бодлогыг оруулсан: Балхүүгийн Батбаясгалан
Бодолт
Заавар: Үүнийг шууд 5.9-18 шиг бодож чадна. Одоо бол рх-аар бодох нь чухал байна.
Бодолт: $A_n$ аль ч хос зэрэгцээгүй, $B_n$ яг 1 хос зэрэгцсэн, $C_n$ яг 2 хос зэрэгцсэн
гэвэл $n\ge2$ үед
$$\left\{\begin{array}{l}{
A_{n+1}=2n(2n-1)A_n+2(2n-1)B_n+2C_n\\
B_{n+1}=4n(n+1)A_n+2(n+1)B_n+2(n+1)C_n\\
C_{n+1}=(4n-2)B_n+\big(4+(2n-2)(2n-3)\big)C_n}
\end{array}\right.$$
болно. $A_2=2$, $B_2=0$, $C_2=4$ тул $A_6=12771840$.
Заавар:
Бодолт: $f(n,m)$ нь $n$ хосыг дугуй ширээнд суулгахад яг $m$
хос нь зэрэгцсэн байх тоо гэе. $f(n+1,m)$-г бодохын тулд $n$ хос
$f(n,k)$, $k=\overline{m-1,m+2}$ байдалтай байраа эзэлсний дараа шинэ
хос ирж $f(n+1,m)$-ийн $2(2n-m+1)f(n,m-1)$,
$(2m+A_{2n-m}^2)f(n,m)$, $2(m+1)(2n-m-1)f(n,m+1)$,
$A_{n+2}^2f(n,m+2)$ үл огтлолцох байрлалуудыг үүсгэж чадах тул
$f(n+1,m)$ нь энэ 4 тооны нийлбэртэй тэнцүү ба $f(2,0)=2$,
$f(2,1)=0$, $f(2,2)=4$, $f(n,n)=2^n(n-1)!$ байх тул $f(6,0)$-г
бодож олно.