Владстон Феррейра Фило - Теоретический минимум по Computer Science [Все что нужно программисту и разработчику]

Представьте колоду из 13 игральных карт только пиковой масти . Сколькими способами вы сможете раздать шесть карт своему сопернику? Мы уже видели, что — это количество перестановок 6 карт из 13. Поскольку порядок их следования не имеет значения, нужно разделить это число на 6! чтобы получить

комбинаций.

Бином — это количество способов, которыми можно извлечь m элементов из ряда, состоящего из n элементов, независимо от порядка их следования:

Конструкция в левой части (запись бинома) читается как «из n по m » [18] В литературе принято обозначение ( m — нижний индекс, n — верхний), которое читается как «сочетания m из n ». — Примеч. пер. .

Шахматные ферзи У вас есть пустая шахматная доска и 8 ферзей, которые допускается ставить на доске где угодно. Сколькими разными способами можно разместить фигуры?

Шахматная доска поделена на 64 клетки, 8 × 8. Число способов выбрать 8 клеток из 64 составляет млрд [19] Профессиональная подсказка: поищите в Интернете по запросу « из 64 по 8 », чтобы узнать результат. .

Подсчет сумм последовательностей часто встречается при решении комбинаторных задач. Суммы последовательных чисел обозначаются прописной буквой «сигма» ( ). Такая форма записи показывает, как выражение будет суммироваться для каждого значения i :

выражение с участием i.

Например, суммирование первых пяти нечетных чисел записывается так:

.

Обратите внимание: чтобы получить слагаемые 1, 3, 5, 7 и 9, вместо i последовательно используются числа от 0 до 4 включительно. Следовательно, сумма первых n натуральных чисел составляет:

Когда гениальному математику Гауссу было 10 лет, он устал от суммирования натуральных чисел одного за другим по порядку и нашел такой ловкий прием:

Догадаетесь, каким образом Гаусс это обнаружил? Объяснение приема приведено в приложении II. Давайте посмотрим, как можно его использовать для решения следующей задачи.

Недорогой перелет Вы должны слетать в Нью-Йорк в любое время в течение следующих 30 дней. Цены на авиабилеты изменяются непредсказуемо в соответствии с датами отъезда и возвращения. Сколько пар дней необходимо проверить, чтобы отыскать самые дешевые билеты для полета в Нью-Йорк и обратно на ближайшие 30 дней?

Любая пара дней между сегодняшним (день 1) и последним (день 30) допустима при условии, что возвращение будет в тот же день или позже, чем отъезд. Следовательно, 30 пар начинаются с 1-го дня, 29 пар начинаются со 2-го дня, 28 — с 3-го и т. д. И есть всего одна пара, приходящаяся на последний день. Таким образом, 30 + 29 + … + 2 + 1 — общее количество пар, которое нужно рассмотреть. Мы можем записать это как и использовать удобную формулу Гаусса:

пар.

Кроме того, мы можем решить эту задачу при помощи комбинаций, выбрав 2 дня из 30. Порядок не имеет значения: на более ранний день придется отъезд, на более поздний — возвращение. Таким образом, мы получим . Что-то не то… Дело в том, что мы должны учесть еще и случаи, когда прибытие и отъезд приходятся на одну дату. Так как дней всего 30, следовательно, .