Комбинаторика

Комбинаторика

Факториал Факториал числа — это произведение натуральных чисел от 1 до а.  Факториал обозначается с помощью восклицательного знака, вот так: 4! Пример: 3! = 1 * 2 * 3 = 6 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720 10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = 3628800

Перестановки Перестановки — комбинации, состоящие из n объектов и отличающиеся только их расположением. Пример: Представим, что перед нами лежит список сериалов, которые мы хотим посмотреть. Допустим, их всего 4, назовем их А, Б, В и Г. Теперь вопрос: в каком порядке мы будем смотреть сериалы?

Выведем формулу для перестановок. Вернемся к сериалу. Сколько сериалов можно посмотреть первым делом? Всего 4. Сколько сериалов могут оказаться на втором месте? 4 — 1 = 3. То есть у нас четыре варианта сериала, который может оказаться на первом месте. Для каждого из этих вариантов еще по три того, какой сериал может оказаться на втором месте. Всего получаем 4 * 3 комбинаций.

Применим аналогичные рассуждения. Сколько сериалов может оказаться на третьем месте? 3 — 1 = 2. Получаем 4 * 3 * 2 комбинаций. Остался последний сериал. Значит, на четвертом месте может оказаться только один из сериалов. Получаем 4 * 3 * 2 * 1 комбинаций. Ничего не напоминает? Все верно, это факториал. Следовательно, чтобы найти количество перестановок для n элементов, нужно найти n! Перестановки обозначаются буквой Р. Pn = n!

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

Сочетания Сочетания — комбинации из m элементов, которые выбраны из n различных элементов и отличаются только составом элементов. Формула сочетания выглядит так: 

Представим, что к нам в гости на день рождения должны прийти трое друзей. Они решили принести по шарику из ближайшего цветочного магазина. В этом магазине 5 видов шариков, а наши друзья покупают их независимо друг от друга — не видят, что купили двое других. Сколько способов у наших друзей купить шарики так, чтобы они не повторялись? Всего у нас 5 шариков – это n. Друзей трое, то есть они принесут на праздник только три шарика – это m. По формуле получаем:

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

То есть для каждой из десяти комбинаций у нас есть по шесть вариантов размещения шариков в них. Всего получаем 10 * 6 = 60 комбинаций. В этом случае у нас был достаточно простой счет. А если каждая комбинация будет состоять из 10 элементов? Найти все варианты вручную у нас не получится. Но в комбинаторике есть решение и для этого случая. Когда важны и порядок, и комбинация элементов, мы имеем дело с размещениями.

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

Размещения Размещения — комбинации, составленные из m элементов, которые выбраны из n различных элементов и отличаются составом и порядком элементов. В нашем случае n = 5 — виды шариков в магазине, а m = 3 — сколько всего шариков окажется на дне рождения.  Формула для размещений выглядит следующим образом:

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

Один из наших друзей решил принести нам в подарок еще и цветы. Он знает, что мы любим розы, пионы и кактусы. К сожалению, денег у него хватит только на один цветок. Сколько у него способов купить цветы? Три: или роза, или пион, или кактус. Важно обратить внимание на “или”. Это слово-маркер, которое показывает, что нужно применить правило сложения.

Определение Комбинаторика – раздел математики, изучающий способы подсчёта всевозможных комбинаций из некоторых элементов (объектов), составленных по определённым правилам. Термин «комбинаторика» происходит от латинского слова «combina», что в переводе означает «сочетать», «соединять».

Правило произведения Если объект A может быть выбран m различными способами, причем после каждого такого выбора объект B можно выбрать n различными способами, то выбор «сначала A, а потом B» можно осуществить m⋅n способами.

Пример решения задач В классе 25 человек. Сколькими способами можно выбрать старосту класса и его помощника?  Старосту класса можно выбрать 25 различными способами. После этого к каждому такому выбору старосты помощника можно подобрать 24 различными вариантами. 25*24=600 Ответ. 600.

Правило суммы Если объект A может быть выбран m различными спосо­бами, а другой объект B можно выбрать n различными спо­собами, причем ни один из способов выбора объекта A не совпадает ни с одним из способов выбора объекта B, то выбор «либо A, либо B» можно осуществить m+n способами.