где <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) Теперь, используя вторую формулу, докажем первуюДокажем первое соотношение:
Так же, как и первом случае, напишем формулу через субфакториал:У нас есть <tex dpi = "140"> !n=(n-1)[!(n-1)+!(n-2)] </tex>чисел и столько же мест. Мы должны найти количество способов разместить эти числа так, что ни одно из чисел не оказалось на месте с таким же номером.ЗаметимПредположим, что если умножить первое число оказалось на месте с номером <tex dpi = "140"> n i </tex> на . Это можно сделать <tex dpi = "140"> !(n-1) </tex>способами. Теперь есть 2 варианта, то получим часть второй формулызависящие от того, а значит оставшиеся части формул будут равны:окажется ли число с номером <tex dpi = "140"> !n=n \times !(n-i </tex> на первом месте или нет. 1)-!(n-1)+(n-1) \times !(n-2) Число <tex> i </tex>Распишем субфакториалы от на первом месте. Остается <tex dpi = "140"> n-2 </tex> мест и <tex dpi = "140"> n-1 2 </tex>: чисел. То есть количество беспорядков от <tex dpi = "140"> (n-1) \times (n-2)!\sum \limits_{k = 0}^{n-2} \frac {(-1)^{k}}{k!}-(n-1)!\sum \limits_{k = 0}^{n-1} \frac {(-1)^{k}}{k!}=(-1)^{n} </tex>2) Число <tex dpi = "140"> (n-1)!\sum \limits_{k = 0}^{n-2} \frac {(-1)^{k}}{k!}-(n-1)!\sum \limits_{k = 0}^{n-2} \frac {(-1)^{k}}{k!}+ \frac {(-1)^{n-1}}{(n-1)!}=(-1)^{n} i </tex>Субфакториалы от не на первом месте. Это эквивалентно решению задачи с <tex dpi = "140"> n-2 1 </tex>, умноженные на местами и <tex dpi = "140"> n-1 </tex>числами (первое число уже заняло место, сокращаются, остается верное равенство а остальные еще нет). Получается количество беспорядков от <tex dpi = "140"> -(-1)^{n-1}=(-1)^{n} </tex>. В итоге получается необходимая формула.
}}
