Математика

Тема 17.

Примеры комбинаторных задач.

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

Методы комбинаторики находят широкое применение в физике, химии, биологии, экономике и других областях знаний.

Рассмотрим некоторые комбинаторные задачи:

1.Несколько стран в качестве символа своего государства решили использовать флаг в виде 3-х горизонтальных полос одинаковых по ширине и цвету: синий, красный и белый. Сколько стран могут испытать такую символику при условии, что у каждой страны свой отличный от других флаг?

Воспользуемся деревом возможных вариантов:

 

 

Ответ: 6 комбинаций.

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

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

Здесь на помощь приходят несколько замечательных комбинаторных правил, которые позволяют подсчитать количество комбинаций без их прямого перечисления.

Сколько трехзначных чисел можно составить из цифр 1, 3, 5, 7, используя в записи числа каждую из них не более одного раза?

Чтобы ответить на вопрос задачи, выпишем все такие числа. Пусть на первом месте стоит цифра 1. На втором месте может быть 3,5 или 7. Запишем, например, на втором месте цифру 3, тогда в качестве третьей цифры может быть 5 или 7. получим два числа135 и 137. Если на втором месте взять цифру 5, то в качестве третьей цифры можем взять или 7. В этом случае получим числа 153 и 157. Если же, наконец, на втором месте записать цифру 7, то мы получим числа 173 и 175.

 

 

Числа, которые начинаются с цифры 1:

135, 137, 153, 157, 173, 175.

Аналогично, можно составить числа, которые начинаются с цифры 3, с цифры 5, с цифры 7.

Ответ: 24 трехзначных числа.

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

Следовательно, общее число трехзначных чисел равно произведения 4 ∙ 3 ∙ 2 ∙ 1 = 24. Здесь мы использовали комбинаторное правило умножения. Сформулируем это правило в общем виде.

Пусть имеется n элементов и требуется выбрать из них один за другим k элементов. Если первый элемент можно выбрать n₁ способами, после чего второй элемент можно n₂ способами из оставшихся, затем третий элемент можно выбрать n₃ способами из оставшихся и т.д., то число способов, которыми могут быть выбраны все k элементов, равно произведению n₁ ∙ n₂ ∙ n₃ ∙ … ∙ n_k

Например, кафе имеются три первых блюда, пять вторых блюд и два третьих. Сколькими способами посетитель кафе может выбрать обед, состоящий из первого, второго и третьего блюд?

Первое блюдо можно выбрать тремя способами, второе блюдо – пятью способами и третье – двумя способами. По правилу умножения обед можно выбрать 3 ∙ 5 ∙ 2 = 30