Изменения

Перейти к: навигация, поиск

Формула включения-исключения

2 байта добавлено, 18:30, 14 января 2015
м
Рекурсивная формула нахождения количества беспорядков
Так как <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>
Субфакториалы от <tex dpi = "140"> n-2 </tex> сокращаются, остается верное равенство <tex dpi = "140"> -(-1)^{n-1}=(-1)^{n} </tex>
}}
 
== См. также ==
* [[Производящая функция]]

Навигация