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

• Суша ВО0Х биномиальных коэ®щи0Нтов равна X " . Если 0 2 - F , ^ , Х С - О ' ^ С С И . К )= 0 . Ш . 8 ) К ^ О Знакочареда-.щаяоя сумш всех йиномиалышх ксайнЕциеи. в •раяиа нули. Непосредственно ив формулы (13.4) олвдуат свойст­ во с/.ммвтрш: С с и , к ) = СС и ,и - к ) . (М.9) Б качества щ :лвра рассмотрим следуидую задачу: найти число поданожеств ^ -множества V . Заиятим', что любое К - подмножество является К -оочетаггаем. Следовательно, число К -поданожеств IMBHO С ( И, '< ) . Пользуясь правилом сушш и свойством (13.7), находа«м реювнпв; х=о §13.4. Раайиания К -разбиеггаем и -множества V' называется оиотвма множеотв i V i I , удовлетворяющих условиям: 1 ) \ / i - \^C^V • 2)UVi'^y . . Пусть ц еше числа, такие, '•"о = ' Тогда данное К-равбиенио {.Vt К } называетоя('К1,..»,' £ н;~ разбиением, если IVcl =t i ' , L-i,K .Обозначим чи'^ю Ct-i, ' г ) - разбиений из I't -мноквот^^ ва ч е р а з ) • Выбор ( t i ) -разбиения предотавляетоя как пооледо- вателъный выбор -ггодмнокества и з v9 -множества, -подмно­ жества иs(И-'г^) -множества оотавшихся элементов и т.д. Так как -каждое -подмножеотво являетоя -сочетанием, то до прави­ лу произведения и ;аем рав-^чство: ПОЛ1,вуЯ0Ь формулой (13.4), получим H'l 4i(^'tr4)i (П'±.г^)1гк1 х l's4 Видно, что числитель каждой олеАующей дроби уничтожаетоя о чам'ью чнаменат m иредыд.. ;цвй дроби. Учитывая также, что - j , С И ~ ) J ^ • получим ОКОМ" . чательную формулу; . Ы