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

106 такой выбор сделан, остается п-1 возможностей для выбора второго элемента, затем п-2 возможностей для выбора третьего элемента и т.д., для выбора f-oro элемента будет п-г+\ возможностей. По правилу произведения получим: Р(п,г)= п(п-\)...(п-г+\). Очевидно, что имеем; Р(п,п)=п! Для полноты будем считать, что Р('п,0;=0.'=1. Подсчитаем теперь число Р возможных г-перестановок с повторениями. В этом случае после выбора любого элемента г-перестановки остаются все те же «-возможностей для выбора следующего элемента. Следовательно, по правилу произведения, число г-перестановок с повторениями из п-множества равно Р=п. Подсчитаем теперь число г-сочетаний (без повторений). Обозначим число г-сочетаний (без повторений) через С(п,г), или С/, или г-сочетание (ai, а;,..., a j , ajSA не зависит от порядка написания элементов, в то время как в (--перестановках в зависимости от порядка элементов получаем различные /--перестановки. Так как P(r,r)~r!, то Q г_Р(п,г) _п(п- 1)...(п-г +1) _ п! г! г! г!(п-г)! Итак, имеем: г!( п-г)! Определим число г-сочетаний с повторениями. Пусть элементы множества А занумерованы числами 1,2,...,п. Тогда вместо г-сочетаний с повторениями из множества А будем рассматривать соответствующие им (взаимно однозначно) г-сочетания с повторениями из множества А ={\,2,...,п]. Так как в сочетаниях порядок элементов несущественен, всякое г-сочетание из А ' можно записать в виде (ki, кг,.... К), \<ki^n, (4.4) где ki< к2<... ^ К (равенство имеет место, когда есть повторяющиеся эле.^ленты). .'--сочетаншо (4.4) с повторениями поставим в соответствие г- выборку: (7с)+0, ^/ + 1,/С2+2, кг'^г-\), (4.5) в которой все элементы уже различны, потому что к элементам неубывающей последовательности прибавлены элементы возрастающей последовательности.