Изменения
Нет описания правки
<tex>|A_i| = (n - 1)!</tex> (т.к. <tex>i</tex>-ая позиция занята числом <tex>i</tex>). <math>\binom{n}{1}</math> — количество спосбов выбрать одну <tex>i</tex>-ую позицию <math>\Rightarrow</math> <tex>\sum \limits_{i = 1}^{n} |A_i| = </tex> <math>\binom{n}{1}</math><tex> (n-1)!</tex>
Рассмотрим <tex> |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| </tex>, где <tex> 1\le i_1 < i_2 < ... < i_k \le n </tex>. Так как некоторые <tex>k</tex> позиций <tex>i_1, i_2, ... , i_k </tex> заняты соответствующими числами, то количество спосбов способов расставить остальные <tex>n-k</tex> чисел равно <tex>(n-k)!</tex>. То есть <tex> |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = (n - k)! </tex> Количество всех способов выбрать <tex>k</tex> позиций <tex>i_1, i_2, ... , i_k </tex> равно <math>\binom{n}{k} </math>. Таким образом получаем, что:
<tex>\sum \limits_{1\le i_1 < i_2 < ... < i_k \le n}^{} |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = </tex> <math>\binom{n}{k}</math><tex>\cdot(n-k)!</tex>
