Дискретная математика

113 3) возвратить (прибавить) сумму весов элементов, имеющих не менее двух свойств и т.д. Обобщением предыдущей теоремы является следующая. Теорема 4.4. Сумма весов элементов п — множества S, удовлетворяющих г - выборке из т - множества свойств pj, р,„ находится по формуле Vm f J = vf г j - с'^.1vf /•+1; + Cl^.iV(r + 2j -... + и""'" vffflJ. Без доказательства. § 7. Задача о беспорядках и встречах Пусть задано конечное (упорядоченное) множество чисел {1,2,3,,..,п}. Из них мотуг быть образованы различные перестановки. Число всех перестановок рано п! Среди этих перестановок имеются такие, что ни один элемент не сохранил своего первоначального места: а , - / , i=l,2,...,n. Такие перестановки называют беспорядками. Сколько существует беспорядков? Введем свойства pi, р2, р„ такие, что свойство р,- означает, что элемент Uj остался на своём месте; а,- = i, Пусть Nfk) - число перестановок, для которых к элементов находятся н а своих местах. Ясно, что число N(k) равно (п-к)! Число беспорядков, т. е. число N(0), находится с помощью метода включения и исключен11я. Тогда имеем; N(0) = п!-С1(п-1)!+С'^„{п - 2)!-.., + (-]/ СЦ (п~к)!+... ^ 2! 3! п! Это число является целым числом, ближайшим к (п! е'). Например, если и •= 7, ToN (0) = \?.54. Если нас интересует число перестановок, для которых ai=i точно в г местах (О < г < п), то возникает задача, известная под названием «задачи о встречах». В этом случае получим следующее: г чисел из 1.2 п можно выбрать С,^ способами и, выбрав их, умножим на число беспорядков из оставшихся п - г символов. В результате получим: г!^ 2! (п-г)!