Изменения

*#<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>