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

Пуотг) d - ^-сочвтаннв о по. .'ораниями у -множестваV лобан:!:.: элементы множества V к элементам R, . Получим И f t 'iOB, среди которых аоть одинаковые. Упорядотлм вое эта Kl + t. эле! птоз 13 порядке возр'зотания их номеров, ропола г ая пл4Шйковко элементы рядом. Будем иметь Ю гдупп элементов, О'^'яблик группы друг от друга вертикаггдамн черточками. Потре- б^.л'сл (м--! ) черточек, для которых ну.яно выбрггь ( и--# ) Хазличных промежутков между элеменгашз, причем порядок этих проме-гутков безразличен. Вовго между ( р + ^ ) элементами иглеетоя. V\+^-i промежуисов. Таким образом, чиоло о^оообов раоотановки n - i черточек аа И+ К--f меотах равно С^|'1+'Г.-(,и-0 . Заметим, что расположение раоотановленных чер­ точек, в з т м н о однозначно ооответотвуат -сочетанию Й. . Поэтому С!Си,г)= С С й + - г — » i - 0 . Иоиользуя (13.4), полу­ чим формулу ^ г/(и-<)! (13.5)^ .jI3.3.. Биномальная йошула Биномиальная форглула (бином Ньютона) имеет вид: ( э с + ^ г = X (13.6) о Яокзаательотво. =( x f - ^ ) •• • Ccc-f-^) . раскроем "oe скобки. Получим слагаемых. Сгруппируем олагаеше вида ^ Таких слагаемых ^^удет С к ) , т.к. для полу- ЧЙЯ1Ш такого олагаемого нужно выбрать к скобок u s Ю и паре- многшть в них первые слагаеше з : , а в остальных И-К скоб­ ках перамиокшть ^ , т . е . выбрать К -оочетаиив скобок. Сумма слагаешх и данной r g y m e равна С(1^,к)СС'^ . Сумми­ руя их по группам (по 1- ) , получим формулу (13.6), Числа С (У1,К) , К = 0 , » называются биномиальными ко8ф*~ фйщгентами р: опрвдалятатоя по формуле (13,4). Иопользуя фармулу' (13.6), .•'•'^'гко получить шо г а а свойства биномиальных ксайициентов. Прлокив X = 1 I ^ = '1 , получим ^ = (13.7) Ktt V