Рассмотрим еще одну задачу. Пусть у нас есть в классе 12 студентов. Сколько есть способов разбить их на группы из двух человек для выполнения группового проекта, одного и того же проекта для всех пар? Хорошо. Эта задача, на самом деле, более сложная. Есть несколько разных способов ее решать, но в любом случае нам потребуется скомбинировать несколько идей из тех, что мы рассматривали в нашем курсе. Давайте разберем решение, в котором мы будем смотреть с позиции групп. Мы должны выбрать двух людей из 12 в одну из групп, в первую группу. При этом порядок в группе неважен, то есть это сочетание, мы должны выбрать подмножество из двух человек среди 12 человек, и у нас C из (12 по два) вариантов выбрать состав первой группы. Дальше. Для следующей группы у нас осталось 10 людей, и у нас, аналогично, C из (10 по два) вариантов составить вторую группу и так далее. Для каждой следующей группы у нас будет на два человека меньше, но это будет сочетание: мы каждый раз должны выбрать двух людей из оставшихся. Дальше мы должны перемножить это по правилу произведения, и получится вот такое число вариантов: C из (12 по два) на C из (10 по два) на C из (восьми по два), и так далее, до C из (двух по два). Для каждой из шести групп мы это перемножили, получилось шесть множителей. Общее число вариантов — это вот это произведение. Все ли правильно закончили мы тут? Оказывается, что нет. Давайте посмотрим, почему. Давайте для удобства занумеруем людей числами от одного до 12. Например, мы посчитали вот такое разбиение на группы: в одну группу, в первую, вошел третий и седьмой человек, во вторую первый и пятый, потом шестой и девятый и так далее. Также есть другой вариант, например, вот такой: в первую группу вошли первый и пятый человек, во вторую — третий и седьмой, и так далее, и дальше они просто совпадают. Заметим, что эти разбиения на группы отличаются чем? Только первыми двумя группами. Они просто написаны в разном порядке, можно это заметить. На самом деле, для нашей задачи это неважно. Мы хотели разбить людей на группы по два так, чтобы они выполняли один и тот же проект, поэтому неважно совершенно, в каком порядке мы выбирали эти пары. То есть, на самом деле, порядок между группами тоже неважен, а мы посчитали, как будто у нас есть первая группа, вторая и так далее. Но что же теперь делать, как с этим быть? Мы просто можем воспользоваться одной из старых идей, которая у нас была. Мы посчитали каждое разбиение шесть факториал раз. Мы посчитали их столько раз, каждое разбиение на пары, столько раз, сколько есть способов переставить группы между собой. У нас шесть групп, количество перестановок (мы его считали) это шесть факториал, поэтому мы каждое разбиение посчитали шесть факториал раз. Когда мы пробовали решить задачу первый раз, у нас получилось вот такое количество способов: C из (12 по два) на C из (10 по два) и так далее. При этом мы каждое разбиение посчитали шесть факториал раз. Что нужно сделать? Надо просто поделить на шесть факториал теперь, и получится правильный ответ. Поделим на шесть факториал, можно это немножко упростить. Просто, если мы распишем каждый биномиальный коэффициент, первый — это (12 на 11 пополам); второй — это (10 на девять пополам) и так далее, то видно, что в числителе у нас получается просто 12 факториал, просто перемножаем 12 на 11 на 10 и так далее. А в знаменателе получается (во-первых, шесть факториал там уже просто есть), а во-вторых, еще получается: два на два на два, и так далее, шесть раз, получается два в шестой. Получается, что ответ у нас 12 факториал делить на шесть факториал умножить на два в шестой в знаменателе. Это 10395 способов. Хорошо. За эти две недели мы обсудили несколько самых стандартных постановок задач комбинаторики, и в подавляющем большинстве случаев в задачах на подсчеты, которые встречаются на практике, этих постановок хватит. Подавляющее большинство задач попадает в одну из этих постановок. Но при этом бывают и более сложные ситуации, которые мы не разбирали, и, конечно, в них тогда нужны какие-то еще знания. На самом деле, бывают настолько сложные задачи, что никто в принципе не знает, как их решать. На следующей неделе мы применим то, что мы узнали в первые две недели, при изучении вероятностей.