Изменения
Нет описания правки
{{Теорема
|id=идентификатор (необязательно), пример: th1.
|statement= Количество беспорядков порядка <tex>n</tex> равно субфакториалу <ref>[http://ru.wikipedia.org/wiki/%D0%A1%D1%83%D0%B1%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB Википедия {{---}} Субфакториал]</ref> числа <tex>n</tex> (обозначение: <tex>!n</tex>) и вычисляется по формуле:
<tex dpi = "140"> равно !n = n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + ... + (-1)^{n}\frac{n!}{n!} = \sum_{k=0}^n(-1)^{k}\frac{n!}{k!} </tex>
}}
<tex dpi = "140"> d(n)=(n-1)[d(n-1)+d(n-2)] </tex>
где <tex dpi = "140"> d(1)=0 </tex>, а <tex dpi = "140"> d(2)=1 </tex>
|proof =1) Сначала докажем второе соотношение: Так как <tex dpi = Примечание "140"> d(n)=!n </tex>, то можно переписать эту формулу, как <tex dpi = "140"> !n=n!(n-1)+(-1)^{n} </tex>По формуле субфакториала <tex dpi = "140"> !n=n!(\sum \limits_{k = 0}^{n-1} \frac {(-1)^{k}}{k!} + \frac {(-1)^{n}}{n!})=n!\sum \limits_{k = 0}^{n-1} \frac {(-1)^{k}}{k!}+(-1)^{n}=n \times !(n-1)+(-1)^{n}</tex> 2) Теперь, используя вторую формулу, докажем первую: }}== См. также ==* [[Производящая функция]]* [[Лемма Бёрнсайда и Теорема Пойа]] ==Примечания== <references />== Источники информации ==
* [[wikipedia:ru:Беспорядок_(перестановка)|Википедия — Беспорядок]]
* [http://en.wikipedia.org/wiki/Derangement Wikipedia — Derangement]
* Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика, Изд. 4-е, исправленное - МЦНМО, 2013 ISBN 978-5-4439-0052-0
* Р. Стенли, Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107-108.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
