Размеўения и перестановки с повторениями и без повторений. Сочетания без повторений и их свойства

Пример №1
Алфавит состоит из множества символов E={+,∗,0,1,f}. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.
Решение
Под трёхсимвольными словами будем понимать выражения вида "+*0" или "0f1". В множестве E пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3. Вот примеры таких размещений:
(+,∗,f),(∗,+,f),(1,+,0)
Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:
A35=5!(5−3)!=5!2!=60.
Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться.
Ответ: 60.
Размещения с повторениями из n элементов по k
Размещение с повторениями из n элементов по k – упорядоченная (n,k)-выборка с повторениями.
Количество размещений с повторениями из n элементов по k определяется следующей формулой:
¯Akn=nk(2)
Пример №2
Сколько пятизначных чисел можно составить из множества цифр {5,7,2}?
Решение
Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: (5,5,5,5,5), (7,5,2,2,2). Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 – разные числа. Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):
¯A53=35=243.
Следовательно, из заданных цифр можно составить 243 пятизначных числа.
Ответ: 243.
Перестановки без повторений из n элементов
Перестановка без повторений из n элементов – упорядоченная (n,n)-выборка без повторений.
По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из n элементов определяется следующей формулой:
Pn=n!(3)
Эту формулу, кстати, легко получить, если учесть, что Pn=Ann. Тогда получим:
Pn=Ann=n!(n−n)!=n!0!=n!1=n!
Пример №3
В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения?
Решение