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

воли V ; , L ='I, К -М;-множеотва, то I §13.2. Пдрвотанорки и сочетания Получим фор; „-лы кия расчета количества вихорок чогир-- ооновных типов. Допз'отим, что производится Budop элементов и з некоторого VI -множэотва ] . Упорядоченные выборки называются переотанояками, неуггоря- дочённна - оочетаниями. Различают пврзотаковки и оочвтания боа пслторений или о ггиатораниями. Выборки бвз повторений пршш-го пазнчать просто переотановками и оочеганиялт. Обозначим: РСи д ) - чноло T -пареотановок из И - АИОВДСТНО -. РСиД)-чиоло t -переотано^ок о ггопт-раняям:! j ! 3 у \ -тгожд Hfj, С Си,г) - число -сочат .,;•!» пз и- MHO. «9OTI!:I ; С( и , *6 ) - чио.по t - сочетаний с повторениями из yi -.чноя-.оотн. Выбор t -переотановкй мо-дно представить как поолвдовагял;- ннй выбор эл0М0"'|'ов, причем рапае выбранный элемент не должен всзвращатьоя в множество перед ол..,1уи1ции выбором, '^аяим образом, •К -й элементt -выборки может быть выбран ( и+ (<:-•( ) спосо­ бами , . Пс правилу произведен!'." имеем: Р ( И , г ) = И(И-'|)""Си-^ + 0 ' (13.1' Если —И , то =• " ' й ' ' , г де п1 - факто­ риал числа И . Очевидно, что i^! ц . Лопольауя ivi'v оэойотво и считая, что о ! =.^ , перепишем фор|дулу (13.1) в виде Р ( и л , -* ' ( £ 3.Й ) Если допускаются повторения элементов, то каидий эдемшп выборки можно выс^,ать<и с^ -собамн. Поэтому I P C N , T ' ) . (J.3,3) Получим формулу для'^<и,'Ч-) . Заметим, что упортдочЕНие элвЫч;цтсв-^ -ссчс.ания да е т ' ^ -пороотановку. До правилу про­ изведения имеем: . Отсюда •С( n , t ) =-Р(»,%'}/ •PC'iM. Пользуясь (формулой (13.2), получим _|1J . .f(^~K)l • ' (13.4)