Зачем делить в комбинаторике

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

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

По условию ломаная замкнутая, так что все наборы разбиваются на десятки, получаемые при её обходе, начиная с каждой из десяти вершин (например, ). В итоге получаем различных ломаных.

Но нужно заметить, что ломаная симметричная и все наборы разбиваются на пары, получаемые при её обратном обходе (то есть в рассмотренном примере если мы выберем вершины , то получим ту же самую ломаную!). Поэтому нужно наш результат ещё поделить на чтобы исключить повторы.

Замечание.

Эта задача про известный факт, что различных простых циклов на вершинах имеется

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

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

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

Замечание. Подумайте, сработал ли бы наш способ, если бы было известно, что три отрезка пересеклись в одной точке?

Первую ладью можно поставить на любую из клеток, вторую — на любую из клеток независимо от того, куда поставили предыдущим шагом первую ладью. Так как мы выбираем несколько объектов последовательно, и количество способов выбрать следующий объект не зависит от того, что выбрано ранее, мы должны перемножить числа и . Но мы для себя говорим “первая” ладья и “вторая” — а на самом деле эти ладьи одинаковые. Поэтому способы, когда на клетку поставили первую ладью, а на клетку — вторую, и наоборот, когда на клетку поставили вторую ладью, а на клетку — первую, одинаковы. Значит, все способы посчитаны дважды. Таким образом, произведение нужно ещё поделить на : получаем .

Первую точку можно выбрать десятью способами. Каждую из следующих восьми точек можно выбрать двумя способами: она должна быть соседней с одной из ранее выбранных точек (иначе получится самопересекающаяся ломаная). Поскольку начало и конец при таком подсчёте различаются, а в ломаной – нет, результат нужно разделить на . Следовательно, всего имеется ломаных.

Сначала выберем того студента, у которого профессор спросит домашнее задание. Им может быть любой из гриффиндорцев, итого способов. Затем нам нужно выбрать того, кто будет писать контрольную. Так как это должен быть другой школьник, есть вариантов выбора. Мы выбираем два объекта последовательно, и вне зависимости от выбора первого объекта второй мы можем выбрать всегда одинаковым количеством способов. Значит, чтобы получить общее количество вариантов, посчитанные выше способы необходимо перемножить: .

Главное отличие от предыдущей задачи состоит в том, что нам не важно, какой ингредиент мы выберем первый, а какой вторым. Но сначала посчитаем количество способов, как будто нам важен порядок. Первый ингредиент можно выбрать способами, второй — способами, так как это должен быть другой ингредиент. Так как выбор последовательный и независимый, способы перемножаются, и всего получается вариантов. Но каждый из интересующих нас на самом деле вариантов мы посчитали дважды: скажем, когда Гарри выбирает аконит и рог двурога, мы эти варианты посчитали, во-первых, когда первым выбирается аконит, а вторым — рог двурога, а во-вторых, когда первым выбирается рог двурога, а уже затем аконит. Итак, на самом деле в вариантах каждый нужный нам вариант посчитан дважды. Значит, чтобы найти настоящее количество способов, нам надо найденное число, то есть , поделить пополам: способов.

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

Сразу отметим, что порядок выбора нам не важен: так, партия Рон против Гарри — то же самое, что партия Гарри против Рона!

Но сначала сосчитаем, сколькими способами мы можем выбрать упорядоченную пару.

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

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

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

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

В этой задаче, в отличие от предыдущих, выставляемые фигуры одинаковые. Тем не менее, сначала будем считать их разными, и назовем одну ладью первой, а другую — второй. Первую ладью можно поставить на доску способами, а вторую — способами. Так как выбор последовательный и независимый, мы получаем способа поставить две ладьи вместе. Вспомним, что на самом деле ладьи одинаковые. Это означает, что каждый способ мы посчитали два раза, ведь от перестановки двух ладей местами на самом деле способ расстановки не изменится, но в наших подсчетах этот способ был другим. Поэтому, чтобы найти настоящее количество способов, нужно найденное число поделить пополам: способов.

В каждом рукопожатии участвуют двое ребят, поэтому рукопожатий столько же, сколькими способами мы можем выбрать неупорядоченную пару ребят. Сначала посчитаем, сколькими способами можно выбрать упорядоченную пару. Первого человека мы выбираем способами, второго — способами. Так как выбор последовательный и независимый, эти способы перемножаются: упорядоченных пар. Каждая неупорядоченная пара соответствует двум упорядоченным: например, упорядоченные пары Рон–Гарри и Гарри–Рон соответствуют одной и той же неупорядоченной паре. Значит, чтобы найти количество неупорядоченных пар, или рукопожатий, нужно найденное количество упорядоченных пар поделить пополам: рукопожатий.

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

Сначала выберем пару гриффиндорцев. Упорядоченных пар , так как выбор последовательный и независимый. Но нам нужны неупорядоченные пары, и их вдвое меньше, то есть . К каждой из таких пар профессор может выбрать любого из восьми слизеринцев. Поэтому всего получается различных троек. Таким образом, уроков могут пройти без повторений троек спрашиваемых студентов, а вот на -ом уроке профессору Снейпу придется повториться.

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

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

Итак, пару вертикальных границ можно выбрать способами. Аналогично пару горизонтальных границ также можно выбрать способами. Учитывая, что любой паре вертикальных границ может соответствовать любая пара горизонтальных границ, и все такие комбинации дадут нам различные прямоугольники, эти два количества нужно перемножить: .

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

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

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

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

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

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

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

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

Иы дважды вычли способ, когда все смешарики остались на базе, а нужно было его вычесть всего один раз. Поэтому этот способ надо один раз прибавить к итоговому ответу. Значит, окончательный ответ: .

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

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

Посчитаем количество способов выбрать 3 книги у первого школьника, книг 6 и при выборе нам не важен порядок, поэтому оно равно Аналогично для второго количество способов выбрать 3 книги равно

В итоге количество комбинаций таких троек равно

Сначала мы должны выбрать позиции, где будут стоять чётные, а где нечётные цифры. Заметим, что если мы выберем позиции для трёх чётных цифр, то нечётные мы расположим точно на трёх оставшихся. Посчитаем количество способов выбрать позиции для чётных, всего позиций 6 и при выборе нам не важен порядок, поэтому оно равно

Всего у нас 5 чётных и 5 нечётных цифр. Поэтому количество -значных последовательностей цифр(в отличие от чисел может стоять 0 в начале), у которых по три чётных и нечётных цифры, равно

Теперь посчитаем количество последовательностей, начинающихся с 0. Для этого достаточно посчитать количество идущих после этого 0 -значных последовательностей, у которых две чётных и три нечётных цифры. Аналогично случаю для -значных получаем, что оно равно

В итоге количество -значных чисел, у которых по три чётных и нечётных цифры, равно