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

105 Для каждого а еЛ обозначим через R(a) множество всех упорядоченных пар (а,Ь}, составленных из элемента а и всевозможных b из В, т.е. R(a)={(a,b): ЬеВ}. Очевидно, что n(R(a))= п(В). При различных ai и ор (ai мнонсества ^(ajJ и R(a2) не имеют общих элементов, т.е. R(aj)nR(a2)=0 Ясно, что и ^ ( а ) - А х В . Тогда по правилу суммы получим: п(АхВ)= asA Число слагаемых, очевидно равно п(Л), следовательно, п(А хВ) =п(А) п(В) -пт, где п=п(А) и т=п(В). Это соотношение и называется правилом произведения. Правило произведения можно сформулировать следующим образом: если объект А может быть выбран п способами и после каждого из таких выборов объект В в свою очередь может быть выбран т способами, то выбор «А и В» в указанном порядке может быть осуществлен пт способами. Индукцией можно доказать следующее обобщенное правило произведения-. n(AixA2X...xA^= n(Ai) nfA^j ... n(AJ. § 3. Выборки и упорядочения Отметим, что в множестве порядок элементов не играет никакой роли, т . е . еслиА={а,Ь}, В={Ь,а}, тоА-В. Пусть имеется множество А с п элементами, которое часто называется п-лтожеством А. Некоторая совокупность г элементов этого множества: (aj, Uj, .... Or), где QiSA, i=\,2 г, г < п. называется г-выборкой, а число г - ее объемом. Неупорядоченные г-выборки из и-множества А называются г- сочетаниями, если все г элементов различны, и г-сочетаниями с повторениями - при наличии одинаковых элементов. Упорядоченные г-выборки из и-множества А называются г- перестаиовками, если все г элементов различны, и г-перестаноеками с повторениями, если среди г элементов имеются одинаковые (равные), Задачи выделения г-перестановок и г-сочетаний не дают, как правпло, единственного решения. Эта неоднозначность с решением порождает естественный вопрос: сколькими способами можно осуществить требуемое комбинаторное расположение. Найдем число всех возможных г-перестановок (без повторений) из п- множества. Обозначим искомое число через Р(п,г), иногда это число обозначают Р,' или Р,,^. Задача определения Р(п,г) сводится к последовательному применению правила произведения. Действительно, в и-множестве имеется п возможностей для выбора первого элемента г-перестановки. Как только