Комбинаторные задачи Для самостоятельного решения

Элементы комбинаторики

 

Комбинаторика – это раздел элементарной математики, связанный с изучением количества комбинаций, подчинённых тем или иным условиям, которые можно составить из заданного конечного множества элементов (безразлично, какой природы; это могут быть буквы, цифры, какие-либо предметы и т.п.).

 

Непосредственные подсчеты

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

Логический перебор: При логическом переборе выписывают все комбинации элементов, придерживаясь некоторого правила.

 

Пример 1. В случайном эксперименте симметричную монету бросают: а) дважды; б) трижды. Определите все возможные комбинации выпадения орла и решки.

Решение. Выпадение орла обозначим буквой О, решки – буквой Р.

а) Записываем на первом месте букву О: ОО, ОР. Теперь на первом месте записываем букву Р: РО, РР. В итоге получаем 4 комбинации выпадения орла и решки: ОО, ОР, РО, РР.

б) В каждой комбинации, полученной в предыдущей задаче, добавляем слева букву О: ООО, ООР, ОРО, ОРР. Аналогично слева приписываем букву Р: РОО, РОР, РРО, РРР. В итоге получаем 8 комбинаций.

Ответ: 8.

 

Пример 2. Сколько четных двузначных чисел можно составить из цифр 0, 1, 2, 5, 8, 9?

Решение. Составим таблицу: слева от первого столбца таблицы поместим цифры десятков двузначных чисел, выше первой строки – цифры единиц.

Искомых чисел будет столько же, сколько клеток в таблице, то есть 5·3=15.

Ответ:15.

Иногда подсчет вариантов облегчают графы. Так называют геометрические фигуры, состоящие из точек (их называют вершинами) и соединяющих их отрезков (называемых ребрами графа). Для удобства иллюстрации условия задачи с помощью графа его вершины-точки могут быть заменены кругами или прямоугольниками, а ребра-отрезки – любыми линиями.

Полный граф: При решении задач с помощью полного графа проводят все возможные ребра.

 

Пример 3. Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?

Решение. Рассмотрим полный граф с четырьмя вершинами, обозначенными по первым буквам имен каждого из 4 мальчиков. Отрезки-ребра обозначают шахматные партии, сыгранные каждой парой мальчиков. Из рисунка видно, что граф имеет 6 ребер, следовательно, и партий было сыграно 6.

Ответ: 6.

Граф-дерево

При решении некоторых задач удобно использовать граф, называемый деревом (за внешнее сходство с деревом).

 

Пример 4. Антон, Борис и Василий купили 3 билета на футбольный матч на 1, 2 и 3-е места первого ряда. Сколькими способами они могут занять имеющиеся три места?

Решение. Изобразим перебор способов с помощью графа-дерева, помещая в вершины графа первые буквы имен друзей А, Б и В.

В итоге получаем 6 способов.

Ответ: 6.

Правило умножения

Перебрать и подсчитать всевозможные комбинации из данных элементов, используя наглядные средства, несложно, когда их количество невелико. Однако при большом количестве элементов этот перебор затруднителен, и тогда используют правила комбинаторики. Правило умножения (правило «и») - одно из основных правил комбинаторики.

Согласно ему, если элемент множества А может быть выбран m способами, а элемент множества B - n способами, то упорядоченная пара (A, B) может быть составлена m • n способами. Правило обобщается на произвольную длину последовательности.

 

Пример 5. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если:

а) числа не повторяются;

б) числа могут повторяться.

Решение.

а) Первую цифру выбираем 5 способами, вторую цифру – 4 способами, третью – 3 способами. Всего 5•4•3 =60 трехзначных чисел.

б) Всего 5•5•5 =125 трехзначных чисел.

Ответ: а) 60; б) 125.

 

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

Правило сложения (правило «или») – одно из основных правил комбинаторики, утверждающее, что, если элемент множества A можно выбрать m способами, элемент множества B можно выбрать n способами, и множества A и B не имеют общих элементов, то выбор одного из элементов множеств A или B осуществляется m + n способами.

Пример 6. На блюдце лежит 8 яблок и 6 груш. Сколькими способами можно

взять плод с блюдца?

Решение. Всего способов 6 +8 =14.

Ответ: 14.

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

Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок из n различных элементов P_n= n!, где n!=1•2 •3•...• (n -1) • n; 1!11; 0!=0.

Например, из трех элементов a, b и c можно образовать 3!=1•2•3 = 6 перестановок: abc, acb, bac, bca, cab, cba.

 

Пример 7. Сколькими способами можно обозначить вершины куба буквами A, B, C, D, E, F, G, K?

Решение. Число способов обозначить восемь вершин куба данными различными буквами (которых также восемь) равно P₈ = 8!= 40320

Ответ: 40320.

Размещения

Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений

В частности, при m = n получаем = n!= P_n.

Например, из четырех элементов a, b, c и d можно образовать

размещений по два элемента: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc.

 

Пример 8. Сколько можно составить сигналов из 6 флажков различного цвета,

взятых по 2?

Решение.

Ответ: 30.

Сочетания

Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются только составом элементов. Число всех возможных сочетаний

Например, из пяти элементов a, b, c, d и e можно образовать

сочетаний по три элемента: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.

Числа размещений, перестановок и сочетаний связаны равенством

 

Пример 9. Сколькими способами читатель может выбрать две книжки из пяти

имеющихся?

Решение.

Ответ: 10.

4

 

КОМБИНАТОРНЫЕ ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Т1.1. Сколько различных трехзначных чисел можно записать с помощью цифр 0, 1, 2, если цифры в числе могут повторяться?

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

Т2.1. Четыре мальчика и четыре девочки садятся на 8 расположенных подряд стульев, причём мальчики садятся на места с чётными номерами, а девочки – на места с нечётными номерами. Сколькими способами это можно сделать?

Т2.2. В розыгрыше первенства по футболу принимают участие 18 команд. Сколькими способами могут быть распределены золотая, серебряная и бронзовая медали, если любая команда может получить только одну медаль?

Т3.1. Алфавит состоит из пяти букв. Сколько можно составить слов, имеющих не более трех букв, из букв этого алфавита?

Т3.2. Сколько существует делителей числа 42?

Т4.1. Сколько всего шестизначных четных чисел можно составить из цифр 1, 3, 4, 5, 7 и 9, если в каждом из этих чисел ни одна цифра не повторяется?

Т4.2. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга?

Т5.1. Учащиеся 2 класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предмета?

Т5.2. На станции 7 запасных путей. Сколькими способами можно расставить на них 4 поезда?

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

Т6.2. Для участия в первенстве университета по легкой атлетике необходимо составить команду из 5 человек. Сколькими способами это можно сделать, если имеется 7 бегунов?