Теория графов и комбинаторика

.^оолодияч сумма равна нулю как зш..;оч0релующг эя сумма^воех Ояномизлышх KOSfl^auHeHTOB в разложении бянома (0:+^) (свой­ ство (13.8)). Таким ойразом, рарвнотво (13.16) доказано. Paooi. грим чаотдае вариаг-^ы Формулы (13.16). Пуоть И(Рй , " ' , Pi »<,) - число элементсв, обладающих свойствами р,- ; S t , - чполс элементов сбладамщях t свойот- рймй; - число элементов, обладающих ровно t- ОВОЙОТВР" Ч . Очешдяо, если веса воех йлемантов равны единице, тс fix)} оЗСг)~В^; S-b, В 9Т0М случае формула (13.16) приобретает вид •S/G,- ( 1 3 Д З ) 1^=0 2сли овда'ать, что 11/1=50 , то фсрь7'ла (13,18) псаволяет вычиолить So число элементов, не обладающих ня одним из свойств >^^0 (13.19) Ш , А , Р^ОВОРЙТО; Я ОО^Д9Д?Я!1Я В качеотва npimepa нрименеяся фори!улы вклхяешя та ясклю- ченяя рассмотрим задачу о беспорядках и оовпаденпях. Пусть имеется Ю члредметов к И хгеренумероваяннх числами 1 , 2 , . . И . В ка5;!дув ячейку чожет быт: уложен только один предмет. Требуется раалолгать предметы по ячейкам так, чтс- <iu номер квздой ячейки не совпадал о номером предмета, иаходя- .згося в этой ячейке. Каждо' раскладке предметов по ячейкам ооотватствует И -переотановк.. предметов. Перестановка, в кото­ рой для любого элеменга номер элемента не совпадаат с его по­ рядковым нод-'пом в перестановка f называется беспорядком. Най- Д9М чйоло беопорядаов. liyoTb V - миожестчо воех -переотановок из множества {i,t, .•>, \ , Тогда 6o=/YI = —H j . На множеотве V'введем свойства \>i ,.i » означай^;,, что в данной пе--". реотановке элемент о номерсм i находится на L -м месте. Тогда вопрос о числе беспорядков своди.ая к нахождению числа So , которое опредяляетоя по формуле (13.19). Произвед-м вычгполения: