Монгол Бодлогын Сан
Эх хэлээрээ суралцаж, эх хэлээрээ мэдлэгээ түгээе.
Бодлого №16226
$1,2,\ldots,n$ тоонуудын сэлгэмэл $(x_1,\ldots,x_n)$-д дурын $k$ бүрийн хувьд $x_k\not=k$ бол түүнийг эрэмбэгүй гэж нэрлэе. Бүх эрэмбэгүйн тоо $N_n(0)$-г ол.
Бодлогын төрөл: Уламжлалт
Бодлогыг оруулсан: Batbayasgalan
Бодолт
Заавар:
Бодолт: $X_i=\{(x_1,x_2,\dots, x_n)\mid x_i=i\}$ гэе. Тэгвэл ядаж нэг тоо байрандаа байх сэлгэмэлийн тоо
\begin{align*}
\big|\bigcup_{i=1}^n X_i\big|&=\sum|X_i|-\sum|X_iX_j|+\sum|X_iX_jX_k|-\dots -(-1)^t\sum|X_{i_1}X_{i_2}\dots X_{i_t}|+\dots-(-1)^{n}|X_1X_2\dots X_n|\\
&=C_n^1 (n-1)!-C_n^2 (n-2)!+C_n^3(n-3)!-\cdots-(-1)^tC_n^t(n-t)!+\cdots+(-1)^{n+1}\\
&=n!\left(\dfrac{1}{1!}-\dfrac{1}{2!}+\dfrac{1}{3!}-\dots-(-1)^t\dfrac{1}{t!}+\cdots+(-1)^{n+1}\dfrac{1}{n!}\right)
\end{align*}
Нөгөө талаас нийт сэлгэмэлийн тоо $n!$ тул эрэмбэгүйн тоо
$$N_n(0)=n!-n!\left(\dfrac{1}{1!}-\dfrac{1}{2!}+\dfrac{1}{3!}-\dots-(-1)^t\dfrac{1}{t!}+\cdots+(-1)^{n+1}\dfrac{1}{n!}\right)\approx n!/e$$
буюу $n!/e$-д хамгийн ойр бүхэл тоо байна.