Размещения с повторениями.

Допустим из элементов множества А составляются различные соединения, содержащие по m элементов в каждой группе. Соединения будем считать различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. Причем некоторые из этих элементов могут повторяться. Например, если А ={1, 2, 3, …n}, то {1, 1, 1}, {!, 1, 2}, {1, 2, 3}, {3, 2, 1}, {1, 2, 2, 2} и т.д. – соединения указанного вида. Такие соединения называются размещениями из n элементов по m с повторениями. Найдем число таких размещений. При составлении соединений на каждое место можно поставить любой элемент множества А, т.е. для заполнения каждого места в соединении имеется n возможностей. Тогда по правилу умножения число размещений с повторениями будет равно n^m.

П р и м е р 1. Четыре человека едут на лифте, который может останавливаться на семи этажах. Найти число возможных комбинаций выхода пассажиров.

Решение. Каждый пассажир может выйти на любом из семи этажей, т.е. у каждого пассажира есть семь вариантов выхода. Всего пассажиров – четыре. Следовательно, всего вариантов выхода равно 7⁴.

Размещения без повторений.

Рассмотрим множество А = {a₁, a₂, ...a_n}.Будем далее рассматривать размещения длины m элементов из множества А, не содержащие повторяющихся элементов, т.е. будем рассматривать такие соединения, которые отличаются друг от друга либо хотя бы одним элементом, либо порядком их расположения. При этом они не содержат повторяющихся элементов. Такие соединения называются размещениями без повторений и обозначаются .

При составлении таких соединений на первое место можно поставить любой из n элементов множества А, на второе – любой из n – 1 оставшихся элементов и, наконец. на m-е место – любой из n – (m – 1) оставшихся элементов. По правилу прямого произведения получаем, что общее число размещений без повторений из n по m равно = n(n – 1)(n – 2)...(n – m + 1) или

(*)

П р и м е р 2 . В хоккейном турнире участвуют 17 команд. Разыгрываются золотые, серебряные и бронзовые медали. Сколькими способами могут быть распределены медали?

Р е ш е н и е. 17 команд претендуют на три призовых места. Тогда указать команды, получившие золотую, серебряную и бронзовую медали, можно A ₁₇³ = 17∙16∙15 = 4080 способами.

Перестановки.

Предположим, что мы рассматриваем соединения из множества А = {a₁, a₂, ...a_n }, содержащие все n элементов. Такие соединения отличаются друг от друга только порядком входящих элементов и называются перестановками из n элементов. Число таких перестановок обозначается . Общее число таких перестановок мы получим, если в формуле (*) числа размещений заменим m на n.

P_n = n(n – 1)(n – 2)...(n – n + 1) = n!.

П р и м е р .Сколькими способами можно расположить 5 книг на книжной полке?

Р е ш е н и е. Число способов равно числу перестановок из пяти элементов по пять

P₅ = 5! = 1∙2∙3∙4∙5 = 120.

Сочетания.

В тех случаях, когда нас не интересует порядок элементов в соединении, а интересует лишь его состав, вводят понятие сочетания.

Сочетаниями из n элементов по m называются такие соединения длины m, которые отличаются друг от друга хотя бы одним элементом, входящим в соединение. Порядок элементов безразличен.

Число сочетаний из m элементов по n обозначают через Определим это число. Очевидно, размещения из n элементов по m получатся, если в каждом сочетании сделать все возможные перестановки. Их число равно m!. Отсюда =

П р и м е р 3. В примере 2 найти число возможных троек призеров.

Р е ш е н и е. Число троек призеров равно числу сочетаний из 17 по 3.

.