double arrow

Материалы для семинаров (для обязательного решения предлагаются задачи с номерами 1, 7, 8, 9, 10, остальные задачи приведены в качестве дополнительного материала)

ОТВЕТЫ ДЛЯ САМОКОНТРОЛЯ

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

Задачи комбинаторики.

1. Найти количество объектов, удовлетворяющих некоторым условиям.

2. Занумеровать их и построить алгоритм нахождения элемента по номеру и номера по элементу.

Правило произведения

Если А содержит n элементов, множество В содержит m элементов, то множество пар вида (ai, bj), где ai Î А, bj Î B, содержит mn элементов.

Пример

Сколько способов поставить две шахматные ладьи на доску 8х8 так, чтобы они не «били» друг друга?

Решение.

Есть 64 способа поставить первую ладью, и на каждый из них приходится по 49 способов поставить вторую ладью (поскольку первая ладья занимает одну клетку, и бьёт при этом 14 клеток, то остаётся 49 клеток для второй ладьи). Таким образом, получим 64 × 49 вариантов расстановки двух ладей.

Но при этом каждую расстановку при таком подсчёте мы сосчитаем дважды, поскольку могли бы начать с первой ладьи, а могли бы со второй. Поэтому найденное количество нужно разделить на 2.

64 × 49 / 2 = 1568.

Ответ. 1568.

Пример 2

Сколько существует трёхзначных чисел, у которых все цифры различны?

Решение. Для первой цифры 9 вариантов, от 1 до 9. Когда её выбрали, для второй цифры тоже 9 вариантов, поскольку она не должна совпасть с первой. Когда выбрали первые две цифры, то для третьей осталось 8 вариантов.

По правилу произведения получим ответ: .

Ответ: 648.

Правило сложения

Идея рассуждения – разбить все варианты на группы, каждая из которых состоит из «одинаково устроенных» комбинаций.

Пример

Сколько способов поставить двух шахматных королей на доску 8х8 так, чтобы они не «били» друг друга?

Решение.

В данном случае количество полей, которое «бьёт» король, зависит от его положения на доске.

Если он в углу (4 варианта), то для второго короля свободны 60 полей, если у края доски (24 варианта), то свободны 58 полей, а если отстоит не в углу и не у края (36 вариантов), то свободны 55 полей.

Таким образом, получим 4 × 60 + 24 × 58 + 36 × 55 = 3612. Разделив это количество пополам (по той же причине, что в предыдущем примере), получим 1806.

Перестановки

Перестановкой называют упорядоченный набор чисел 1, 2, 3, … n, возможно, переставленных в другом порядке – например, 3, 2, 1, 4, 5, 6, …, n.

Первый элемент перестановки можно выбрать n способами, тогда второй останется (n-1) способов, на третий – (n-2) способа, и так далее до заключительного элемента, для которого останется ровно один вариант.

Таким образом, количество перестановок равно n(n-1)(n-2)× … × 2×1 = n!

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

Пример.

Сколько способов посадить 5 человек на 5 стульев, по одному человеку на стул?


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: