Монгол Бодлогын Сан
Эх хэлээрээ суралцаж, эх хэлээрээ мэдлэгээ түгээе.
Бодлого №16255
$C_n^k$-ийн рекурент харьцааг бич. $a_n=C_n^k$, $b_k=C_n^k$ дарааллуудын уламжлагч функцийг ол.
Бодлогын төрөл: Уламжлалт
Бодлогыг оруулсан: Балхүүгийн Батбаясгалан
Бодолт
Заавар:
Бодолт: $C_n^k$-ээр $A=\{1,2,\dots,n\}$ олонлогийн $k$ элементтэй дэд
олонлогууд ($k$-дэд олонлог гэе)-ын тоог тэмдэглэдэг.
$x$-г агуулдаг $k$-дэд олонлогийн тоо $C_{n-1}^{k-1}$, $x$-г агуулдаггүй $k$-дэд олонлогийн тоо $C_{n-1}^k$ тул $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$ болно.
$$A_k(x)=\sum_{n} C_n^k x^n=\sum_{n} C_{n-1}^{k-1} x^n+\sum_{n} C_{n-1}^{k} x^n=A_{k-1}(x)x+A_k(x)x$$ тул $$A_k(x)=\dfrac{x}{1-x}A_{k-1}(x)$$ болно. $A_0(x)=\sum\limits_{n} C_n^0 x^n=\sum\limits_n x^n=\dfrac{1}{1-x}$ болохыг тооцвол $$A_k(x)=\dfrac{x^k}{(1-x)^{k+1}}$$ байна.
$$B_n(x)=\sum\limits_k C_n^k x^k=\sum\limits_k (C_{n-1}^k+C_{n-1}^{k-1}) x^k=B_{n-1}(x)+B_{n-1}(x)x$$ тул $$B_n(x)=(1+x)B_{n-1}(x)$$ $B_0(x)=1$ тул $B_n(x)=(1+x)^n$ болно.
$x$-г агуулдаг $k$-дэд олонлогийн тоо $C_{n-1}^{k-1}$, $x$-г агуулдаггүй $k$-дэд олонлогийн тоо $C_{n-1}^k$ тул $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$ болно.
$$A_k(x)=\sum_{n} C_n^k x^n=\sum_{n} C_{n-1}^{k-1} x^n+\sum_{n} C_{n-1}^{k} x^n=A_{k-1}(x)x+A_k(x)x$$ тул $$A_k(x)=\dfrac{x}{1-x}A_{k-1}(x)$$ болно. $A_0(x)=\sum\limits_{n} C_n^0 x^n=\sum\limits_n x^n=\dfrac{1}{1-x}$ болохыг тооцвол $$A_k(x)=\dfrac{x^k}{(1-x)^{k+1}}$$ байна.
$$B_n(x)=\sum\limits_k C_n^k x^k=\sum\limits_k (C_{n-1}^k+C_{n-1}^{k-1}) x^k=B_{n-1}(x)+B_{n-1}(x)x$$ тул $$B_n(x)=(1+x)B_{n-1}(x)$$ $B_0(x)=1$ тул $B_n(x)=(1+x)^n$ болно.