Задача по комбинаторике

В множестве нет порядка чисел (это как кошелёк с горстью монет, например. В каком бы порядке ты их не вынула - это один и тот же набор). Поэтому сочетание {1,2} и сочетание {2,1} - это одно и то же сочетание!
Поэтому, так как в условии разрешены повторы элементов в одном сочетании (то есть сочетания, такие, как {1,1} ) - то ответ будет именно таким.

Первый подход — выбираем по одному.

Размещения. Пусть имеется группа из п различных элементов. Будем извлекать из группы последовательно по одному элементу и располагать их в порядке выбора, не возвращая элементы в исходную совокупность. Пусть совершено к операций выбора.

Теорема 1.1. Число различных способов, которыми можно произвести последовательный выбор к элементов без возвращения из совокупности объема п, равно


? Выбираем первый элемент из совокупности в п элементов. Число таких вариантов равно п. Из оставшейся совокупности в п - 1 элементов выбираем следующий элемент. Число вариантов равно п - 1. Продолжая процесс отбора элементов, к-й элемент мы будем выбирать из п - (к - 1) элементов. По правилу умножения общее число способов выбора к элементов будет равно


Пример 1.4. Для совокупности {1, 2, 3} найти А| и выписать соответствующие комбинации цифр.

31

Решение. Число размещений равно А| = ^ '^ = 6. Соответствующие ком' бинации цифр имеют следующий вид: 12, 21,13, 31, 23, 32.

Величина Aft называется числом размещений без повторений из п элементов по к элементов, а сами размещения без повторений — это все возможные комбинации элементов, отличающиеся друг от друга либо составом, либо порядком элементов.

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



Эти размещения содержат одни и те же элементы и различаются только перестановками своих элементов.