Задание 1. Вопрос 2: Введение в комбинаторику

Задание 1.

Упростить выражения:

                                                                                      

Ответы для самопроверки:

                                                                                                              

Вопрос 2: Введение в комбинаторику.

Число размещений с повторениями из n элементов по m мест равно n^m.

Доказательство: при каждом заполнении места, мы имеем дело с n вариантами выборов, а итоговое число комбинаций – произведение числа вариантов на каждом месте.

Пример: сколько можно составить десятизначных чисел из нечётных цифр в шестнадцатиричной системе счисления? Как изменится ответ, если будут использованы чётные цифры?

Решение:

В шестнадацатиричной системе счисления суть 8 чётных и 8 нечётных цифры. При использовании нечётных цифр мы получим 8¹⁰ чисел, а при использовании чётных –  ибо если на первом месте стоит цифра ноль, то он незначащий, и число таким образом не десятизначное.

Число перестановок из n элементов равно n!.

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

Пример: сколькими способами я смогу расставить 20 книг на полке?

Чтобы получить число размещений (без повторений) из n элементов по k местам разделим n! на k!:

                                                                                                          

В данном случае число мест меньше числа вариантов, и в итоге идёт перемножение от n до (n-k). Выразить это можно при помощи формулы (13).

Пример: у Деда Мороза 15 подарков, и ему нужно поздравить на празднике 10 детей; сколькими способами можно распределить подарки между детьми?

Число сочетаний можно получить, разделив число расстановок на число повторений: дело в том, что в случае сочетаний пары вида {a,b} и {b,a} не различаются. Число этих повторов k!:

                                                                                                       

Пример: Преподаватель, едя на экзамен попал в аварию, прибыв в зело плохом настроении, он решил завалить шестерых студентов из двадцати одного в группе. Сколькими способами он сможет выбрать своих жертв?

Рисунок 1: Пояснение к числу сочетаний и к числу размещений

Обобщение данной формулы: число разбиений (размещений без повторений) из n элементов по m групп численностью k_i каждая, причём :

                                                                                       

Пример: Группа из 12 туристов собралась в поход, нужно выделить трёх человек на добычу воды и четырёх на сбор дров, сколькими способами это можно сделать?

Решение:

    В условии задачи неявно присутствует ещё подгруппа путешественников: трое за водою, четверо за дровами, а ещё пятеро – никуда не идут. Таким образом, число распределений обязанностей .

Как это выводится? Мы распределяем части по группам, причём порядок расположения нам не важен, поэтому каждый раз мы делим на число повторений в данной группе.

Рисунок 2: Пояснение к числу разбиений

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