Изменения

<tex dpi="130">(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex> <br\> <tex dpi="130">(2)(1; 4; 3) \qquad (2)(1; 3; 4)</tex> <br\> <tex dpi="130">(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex> <br\> <tex dpi="130">(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex> <br\> <tex dpi="130">(1; 2)(3; 4)</tex> <br\> <tex dpi="130">(1; 4)(2; 3)</tex> <br\> <tex dpi="130">(1; 3)(2; 4)</tex> <br\>

Числа Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода задаются рекуррентным соотношением. Каждое представление <tex dpi="130">n</tex> элементов в виде <tex dpi="130">k</tex> циклов либо помещает последний элемент (<tex dpi="130">n-</tex>ый) в отдельный цикл <tex dpi="130">s(n-1, k-1)</tex> способами, либо вставляет этот элемент в одно из <tex dpi="130">s(n-1, k)</tex> циклических представлений первых <tex dpi="130">(n-1)</tex> элементов. В последнем случае существует <tex dpi="130">(n-1)</tex> различных способов подобной вставки. Например, при вставке элемента <tex>4</tex> в цикл <tex>(1;2;3)</tex> можно получить только <tex> 3 </tex> разных цикла: <tex dpi="130">(1;2;3;4), (1;2;4;3), (1;4;2;3)</tex>. Таким образом, рекуррентность имеет вид:

s(n, k) =\left \{\begin{array}{ll} s(0, 0) = 1 , \\

s(0, k) = 0, & k > 0 \\s(n,k) = s(n-1,k-1)+(n-1)s(n-1,k), & n,k > 0 \end{array} \right.

А коэффициенты <tex dpi="130">x(x)^{n}</tex> — это <tex dpi="130">s(n,k-1)</tex>, так как степени при <tex dpi="130">x</tex> увеличатся на <tex> 1</tex>, а коэффициенты при этом не изменятся.

:#<tex dpi = "160">\left[{0\atop 0}\right]=1</tex> :#<tex dpi = "160">\left[{n\atop 0}\right]=\left[{0\atop k}\right]=0</tex>, в общем случае <tex dpi = "160">\left[{n\atop k}\right]=0</tex>, если <tex>k > n</tex>

:#<tex dpi="160">\left[{n\atop 1}\right]=(n-1)!</tex>#:Зафиксируем один элемент, и переставим оставшиеся всеми возможными способами. Повторений не будет, так как чтобы зафиксированный элемент совпал, нужно сдвинуть всю перестановку на <tex dpi = "160">n</tex>, но тогда мы получим исходную перестановку.:#<tex dpi="160">\left[{n\atop n}\right]=1</tex>, очевидно :#<tex dpi="160">\left[{n\atop n-1}\right]={n \choose 2}</tex>#:Разбить <tex dpi = "160">n</tex> элементов на <tex dpi = "160">n-1</tex> множество можно только одним образом, а именно на множества состоящие из одного элемента и одно множество состоящее из двух. Так как нас интересуют только циклы, получаем выборку двух элементов из всех элементов(множество состоящее из двух элементов всегда является циклом).:#<tex dpi="160">\left[{n\atop n-2}\right]=\frac{1}{4} (3n-1) {n \choose 3}</tex>#:По аналогии с предыдущим тождеством получаем, что нас интересуют виды конкатенации множеств <tex dpi = "160">((n-4)*1+2+2), ((n-3)*1+3)</tex>. Тогда искомая формула получается упрощением выражения <tex dpi = "160">2! \times {n \choose 3} + \frac{{n \choose 2} \times {n-2 \choose 2}}{2!}</tex>, которая учитывает фиксацию элемента в трехэлементном множестве и повторения двухэлементных.:#<tex dpi="160">\left[{n\atop n-3}\right]={n \choose 2}{n \choose 4}</tex>#:Аналогично, учитываем только интересующие нас множества и получаем формулу <tex dpi = "160">2! \times {n \choose 2}{n-2 \choose 3} + \frac{{n \choose 2} \times {n-2 \choose 2} \times {n-4 \choose 2}}{3!} + 3! \times {n \choose 4}={n \choose 2}{n \choose 4}</tex>.

:#<tex dpi="160">\left[{n+1\atop m+1}\right]=\sum\limits_{k=1}^n \left[{n\atop k}\right] {k \choose m}=n! \sum\limits_{k=0}^n \frac{\left[{k\atop m}\right]}{k!} </tex>#:Второе равенство доказывается путем постепенного спуска вниз: #:<tex dpi="160">\left[{n+1\atop m+1}\right]=\left[{n\atop m}\right] + n \cdot \left[{n\atop m+1}\right]=\left[{n\atop m}\right] + n \cdot \left(\left[{n-1\atop m}\right] + (n-1) \cdot \left[{n-1\atop m+1}\right]\right)=...=\sum\limits_{k=0}^n \left[{k\atop m}\right]\frac{n!}{k!}=n! \sum\limits_{k=0}^n \frac{\left[{k\atop m}\right]}{k! }</tex>#:Чтобы доказать первое, будем использовать биекцию(из прошлого раздела) в факториальные степени, а также формулу <tex dpi="160">(x)_{n+1} = x \cdot (x-1)_n \;</tex>.#:Разложим наше искомое выражение, используя формулу для факториальных степеней, и применив бином Ньютона для второго множителя. Тогда: <tex dpi="160">(x)_{n+1}=\sum_{i=0}^{n}\sum_{k=0}^{i} \left[{n\atop i}\right]\binom{i}{k} x^{k+1}</tex>. Немного преобразовав, получим: <tex dpi="160">(x)_{n+1}=\sum_{k=0}^{n}\sum_{i=k}^{n} \left[{n\atop i}\right]\binom{i}{k} x^{k+1} \;</tex>#:C другой стороны: <tex dpi="160">(x)_{n+1}=\sum_{k=0}^{n+1} \left[{n+1\atop k}\right] x^k = \sum_{k=0}^{n} \left[{n+1\atop k+1}\right] x^{k+1}</tex>#:Приравниваем эти два выражения и получаем искомую формулу.#<tex dpi="160">\left[{n\atop m}\right]=\sum\limits_{k=1}^n \left[{n+1\atop k+1}\right] {k \choose m} (-1)^{m-k} </tex>#:Доказательство аналогично предыдущему с учетом знакочередования в убывающих факториальных степенях.#<tex dpi="160">\left[{m+n+1\atop m}\right]=\sum\limits_{k=0}^m (n+k) \left[{n+k\atop k}\right]</tex>#:Постепенно раскладываем и получаем искомую формулу:#:<tex dpi="160">\left[{m+n+1\atop m}\right]=\left[{m+n\atop m-1}\right]+\left[{m+n\atop m}\right]\cdot(m+n)=\left[{m+n-1\atop m-2}\right]+\left[{m+n\atop m}\right]\cdot(m+n)+\left[{m+n-1\atop m-1}\right]\cdot(m+n -1)=...=\sum\limits_{k=0}^m (n+k) \left[{n+k\atop k}\right]</tex>

:<p>  <tex dpi="130">\sum\limits_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = \left \{\begin{array}{ll} 1</tex>, если <tex dpi="130">& n=m \\0, & \text{otherwise} \end{array} \right.</tex>, иначе <tex dpi="130">0</texp>