Руководство для начинающих по комбинаторике и его использование для решения довольно сложного вопроса.

Понимание

Убедитесь, что мы понимаем, что означает вопрос! (Если вы уже понимаете обозначения, вы можете перейти к разделу «Решение»)

Факториалы

Полезная часть математической записи - это факториальная запись; это число, за которым следует восклицательный знак. Лучший способ понять это - это пример. 5! = 5 * 4 * 3 * 2 * 1 = 120.3! = 3 * 2 * 1 = 6. 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1. В общем N! означает умножение всех целых чисел до N вместе.

Факториалы полезны при рассмотрении количества способов перестановки вещей. Предположим, у вас есть 3 шара разного цвета, и вы хотите узнать, сколько способов вы можете расположить их в линию. Вы можете решить это вручную и обнаружить, что есть 6 способов сделать это. В качестве альтернативы вы можете рассуждать более абстрактно и утверждать, что есть 3 варианта выбора для первого шара в вашей линии, затем 2 для второго и только один для последнего, что дает 3 * 2 * 1 или 3 факториала. Древовидная диаграмма прекрасно это представляет.

Как видно, 6 комбинаций: красный-зеленый-синий, красный-синий-зеленый, зеленый-красный-синий, зеленый-синий-красный, синий-красный-зеленый, синий-зеленый-красный. Все эти 6 комбинаций генерируются нашим деревом, которое визуализирует предыдущую логику: три ветви для нашего первого выбора, затем для каждой ветви, две ветви для второго варианта и затем одна ветвь для третьего варианта.

Количество способов, которыми мы можем расположить 10 разноцветных шаров в линию, равно 10 !, а с N шарами будет N! способы их расположения.

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

«Выбрать обозначение»

Команда «N выбрать k» задает вопрос от N человек, сколькими способами вы можете сформировать команду из k человек. Например, ответ «10 вариантов 3» спрашивает, сколькими способами вы можете сформировать команду из 3 человек, которым предоставляется выбор из 10 человек.

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

Но это не совсем так - это говорит нам о количестве способов, которыми мы можем упорядочить 3 человека в линию при наличии 10 человек на выбор. Однако это не команда! Неважно, в каком порядке мы выбираем игроков *, важна команда, которую мы получим в конце.

* Хотя эго игроков может пострадать, если их выбрать последним, это не математическое соображение.

Итак, корректируем исходную фигуру и делим ее на 3 !. (Вспомните 3! = 3 * 2 * 1 = 6.)

Это потому, что на каждую команду из 3 человек приходится 3 человека! способы выстроить эту команду в линию. Таким образом, мы пришли к выводу, что наши 10 * 9 * 8 включают каждую команду 3! раз. Следовательно, если разделить на 3! мы получаем общее количество различных команд.

Мы используем специальные обозначения для обозначения «N выбирают k».

Теперь мы можем перейти к основной проблеме!

Решение

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

Второй способ - рассматривать это как комбинаторную проблему.

Правая часть уравнения спрашивает из 2N человек, как возможны различные команды размером N?

Но левая часть уравнения не имеет такой простой интерпретации.

Первое, что мы делаем, это замечаем, что «N choose k» равно «N choose (N-k)». Например. количество команд размера 4, выбранных из пула из 12 человек, такое же, как количество команд размера 8 (8 = 12–4) из пула из 12 человек. Это потому, что после того, как вы выбрали свою команду из 8 человек, оставшиеся 4 игрока станут командой из 4 человек. Точно так же, если вы выберете команду из 4 игроков из 12, останется 8 игроков, что означает, что, выбрав команду размером 4, вы получите также создали команду 8-го размера. Таким образом, каждый уникальный способ подбора команды 4-го размера также создавал уникальный способ подбора команды 8-го размера, и наоборот.

Мы переписываем уравнение, чтобы отразить это. Наша новая цель - доказать следующее:

Если вас не устраивают n, k, n и абстрактные обозначения, не волнуйтесь! Сначала мы рассмотрим реальный пример, который концептуально аналогичен доказательству общего случая.

Давайте рассмотрим случай, когда мы пытаемся выбрать 11 игроков для футбольной команды из 22 возможных игроков. Это 22 Выберите 11 (правая часть нашего уравнения). Теперь мы меняем нашу точку зрения. Мы разделили 22 игрока на две группы по 11 человек в каждой. Возможно, два местных клуба объединились, и нам нужно выбрать новую первую команду из обеих предыдущих первых команд.

Каждый раз, когда мы выбираем команду, мы выбираем игроков из каждой группы. Например, мы можем выбрать 6 игроков из первой группы и 5 из второй, чтобы сформировать нашу команду из 11 человек. Я называю это «сплит». «Сплит» - это способ разделения между двумя командами количества игроков, которые они могут внести в объединенную команду.

Рассмотрим расщепление (6,5). Количество способов выбрать 6 игроков из первой команды - «11 Выбери 6», а количество способов выбрать 5 игроков из другой команды - «11 Выбери 5». Умножьте их вместе, и вы получите количество способов выбрать команду из 11 человек, где вы выбираете 6 из первой команды и 5 из второй команды.

Мы можем выбрать не более 11 из одной команды и 0 из другой, затем 10 из одной команды и 1 игрока из другой и так далее: (11,0), (10,1), (9,2), ( 8,3) (7,4), (6,5), (5,6), (4,7), (3,8), (2,9), (1,10), (0,11 ). Для каждого «сплита» мы получаем несколько возможных команд, которые мы можем создать. Суммируя все «сплиты», мы получаем общее количество команд, которые мы можем создать.

Логика для общего случая с «2N Choose N» использует идентичную логику, только с немного более общим языком. Мы подсчитываем количество возможных способов построения команды с учетом сплита, а затем суммируем по всем сплитам. Каждое разделение представляет собой одно из (0, N), (1, N-1), (2, N-2), (3, N-3),… (k, Nk),… (N-1,1) , (N, 0). И количество способов построения команды при разбиении (k, N-k): «N выбирают k раз» N выбирают (N-k) ». Суммирование по всем k дает нам левую часть нашей идентичности.

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

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