Классические задачи комбинаторики

КЛАССИЧЕСКИЕ ЗАДАЧИ КОМБИНАТОРИКИ

Общие правила комбинаторики

Решение многих комбинаторных задач основывается на двух фундаментальных прави­лах, называемы х правилом суммы и правилом произведения. Прежде всего, определимся в терминологии. Если имеется, к примеру, 5 шаров в ящике, то мы будем говорить, что один шар из ящика можно выбрать пятью способами.

Правило суммы: если объект А можно выбрать n способами, а объект В - k спосо­бами, то объект "А или В" можно выбрать n+k способами.

Пример. В ящике находятся 20 шаров: 5 белых, 6 черных, 7 синих и 2 красных. Сколькими спо­собами можно взять из ящика один цветной шар?

Решение: здесь предполагается, что цветной шар - это синий или красный, поэтому надо при­менять правило суммы. Цветной шар можно выбрать 7+2=9 способами.

Правило произведения: если объект А можно выбрать n способами, а объект В неза­висимо от него - k способами, то пару объектов "А и В" можно выбрать n·k способами.

Пример. Сколько может быть различных комбинаций выпавших граней при бросании двух иг­ральных костей (игральная кость - это кубик, на гранях которого нанесены числа 1,2,3,4,5,6)? 
Решение: на первой кости может выпасть 1, 2, 3, 4, 5 или 6 очков, то есть всего будет 6 вариан­тов. Точно так же и на второй кости 6 вариантов. Получится всего 6 · 6 = 36 способов.

Правила суммы и произведения справедливы не только для двух, но и для любого числа объектов. Приведем еще два примера, в которых необходимо выбрать правило суммы или про­изведения.

Пример. На книжной полке стоят 3 книги по алгебре, 4 книги по геометрии и 5 книг по литера­туре. Сколькими способами можно взять с полки одну книгу по математике? 
Решение: книга по математике - это книга по алгебре или по геометрии. Применяем правило суммы 3+4=7.

Пример. В меню имеется 4 первых блюда, 3 вторых и 2 третьих. Сколько различных полных обедов можно из них составить?

Решение: полный обед состоит из первого, и второго, и третьего блюд. По правилу произведе­ния получаем 4 · 3 · 2 = 24 различных полных обеда. Решить следующую задачу тремя различными способами: с помощью простого перебора, с помощью дерева вариантов и по правилу умножения.

1.Задача: В коридоре висят три лампочки. Сколько имеется различных способов освещения коридора?

I способ: Пронумеруем лампочки и будем писать + и – в зависимости от того, горит или не горит очередная лампочка.

Перечислим все способы освещения:

+ + + ; + + - ; + - + ; - + + ; + - - ; - + - ; - - - ; - - +

Всего 8 способов. (Всегда можно решить задачу, но можно запутаться, и это может быть сильно долгий путь)

II способ: Построим дерево возможных вариантов

Пе рвая лампочка

+ -

Вторая лампочка Вторая лампочка

+ - + -

Тр етья лампочка Третья лампочка Третья лампочка Третья лампочка
+ - + - + - + -

+ + + + + - + - + + - - - + + - + - - - + - - -

Всего 8 вариантов. (Оказался более понятным способом, но в зависимости от условия задачи может быть громоздким).

III способ: Способ умножения

У каждой лампочки имеется два исхода: может гореть или не гореть. Всего 3 лампочки и у каждой по 2 исхода, т.е.

2•2•2=8

Ответ: 8

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

Решили такие задачи решать следующим образом.

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

Десятки: 1 2 3 4 5

Е диницы: 1 2 3 4 5

5•5=25

Ответ: 25

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

Десятки: 1 2 3 4 5

Е диницы: 1 2 3 4 5

5•4=20

Ответ: 20

3а ) Сотни: 2 4 6

Десятки: 0 2 4 6

Единицы: 0 2 4 6

3•4•4=48

Ответ: 48 чисел.

б ) Сотни: 2 4 6

Десятки: 0 2 4 6

Единицы: 0 2 4 6

Ответ: 18 чисел.

4.Задача. В чемпионате России по футболу в высшей лиге участвует 16 команд.

Перед началом чемпионата газета «Спорт» провела интернет-опрос читателей, задав им 2 вопроса: 1) какие 3 команды станут призерами чемпионата, т.е. займут первое, второе и третье места; 2) какие две команды займут два последних места? Читатели указали все возможные варианты при ответе и на первый, и на второй вопрос.

а) Сколько вариантов состава призеров чемпионата указали участники опроса?

Решение:

Для первого места имеется 16 вариантов выбор команды,

для второго – 15 и третьего – 14.

16 •15•14=3360

Ответ: 3360 вариантов

б) Сколько вариантов состава неудачников чемпионата указали участники опроса?

Решение: Для выбора последнего места – 16 вариантов, предпоследнего – 15.

16•15=240 Ответ: 240 вариантов.

5. Задача. Группа туристов планирует осуществить поход по маршруту Мамино – Папино – Бабушкино – Дедушкино – Тетино.

Из Мамино в Папино можно сплавиться по реке или дойти пешком. Из Папино в Бабушкино – пешком или на велосипедах. Из Бабушкино в Дедушкино доплыть по реке, доехать на велосипедах или пройти пешком. Из Дедушкино в Тетино пешком, на велосипедах или на лошадях. Сколько всего вариантов прохода могут выбрать туристы?

Решение:

Сделаем рисунок:

п п п п

_{в  в}

М П Б Д Т

р в р л

2•2•3•4=36

Ответ: 36 вариантов

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

Решение:

Посчитаем число вариантов маршрута при условии, что они нигде не идут пешком

в в

р в

М П Б Д Т

р д

1•1•2•2=4

Искомая величина: 36-4=32

Ответ: 32 варианта.

Размещения

Если из данного множества предметов мы будем выбирать некоторое подмножество, то его будем называть выборкой. Выборки бывают упорядоченные и неупорядоченные. В упоря­доченной выборке существенен порядок, в котором следуют ее элементы, другими словами, изменив порядок элементов, мы получим другую выборку.

Например, из цифр 1, 2, 3, 4, 5 составляем трехзначные числа 123, 431, 524, ...и т.д. Это упорядоченные трехэлементные выборки, ведь 123 и 132 - разные числа. Другой пример: из 20 учащихся класса будем выбирать двух дежурных. Любая пара дежурных представляет собой неупорядоченную двухэлементную выборку, так как порядок их выбора не важен.

Определение: размещениями из n элементов по m (m n) называются упорядоченные m -эле­ментные выборки из данных n элементов.

Из определения следует, что размещения отличаются друг от друга либо самими элемен­тами, либо их порядком. Число размещений из n по m обозначается -  .

 - формула для вычисления числа размещений.

Найдем, например, число размещений из 7 по 3. Здесь  ,  . Значит, 

Пример. На пяти карточках написаны числа 1, 2, 3, 4, 5. Сколько различных трехзначных чисел можно из них составить?

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

Часто формулы комбинаторики записывают с помощью факториалов: произведение всех последовательных натуральных чисел от 1 до n обозначается n! (n! = 1 · 2 · 3 · ... · n; условимся считать, что 0! =1).

Тогда получится преобразование формулы для вычисления числа размещений:  . Вычислим например по этой формуле :

 

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

Определение: перестановками из n элементов называются размещения из n элементов по n.

Из определения следует, что в данном случае в упорядоченную выборку входят все n элементов и отличаться выборки могут только порядком. Поэтому все перестановки имеют один и тот же состав и отличаются только порядком элементов. Число перестановок из n эле­ментов обозначается  . Получим формулу для вы­числения числа перестановок из n элементов:    .

Приведем несколько примеров использования этой формулы:

Р₅ = 5! = 1· 2 ·3 · 4 ·5 = 120; Р₂ = 2! = 1· 2 = 2; Р₁ = 1! = 1.

Пример. Составить все размещения из трех букв А, В, С.

Решение: АВС, АСВ, ВАС, ВСА, СВА, САВ. Проверим по формуле: Р₃ = 1·2·3 = 6.

Сочетания

Определение: Сочетаниями из n элементов по m (m n) называются неупорядоченные m-элементные выборки из данных n элементов.

Ясно, что все сочетания отличаются друг от друга хотя бы одним элементом, а порядок элемен­тов здесь не существенен. Число сочетаний из n по m обозначается -  . Чтобы из сочетаний получить размещения, надо упорядочить каждую m-элементную выборку, а это можно сделать m! способами. Следовательно, число сочетаний   меньше числа размещений   в m! раз. Получим соответствующие формулы для вычисле­ния числа сочетаний:

  и       

Например,  ;  ;  ;  .

Пример. Из 20 учащихся надо выбрать двух дежурных. Сколькими способами это можно сделать? 
Решение: надо выбрать двух человек из 20. Ясно, что от порядка выбора ничего не зависит, то есть Иванов-Петров или Петров-Иванов - это одна и та же пара дежурных. Следовательно, это будут сочетания из 20 по 2:  . Ответ: 190 способами.

2.5. Треугольник Паскаля. Бином Ньютона

Составим таблицу значений   для n, m = 0,1,2,3,4,5,6,7 - эту таблицу можно неограниченно продолжать вниз и вправо. Она называется треугольником Паскаля. Еще удобнее ее записывать в виде равнобедренного треугольника.

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

Нам знакомы формулы сокращенного умножения: (a + b)¹ = a + b;

(a + b) ² = a² + 2ab + b²; (a + b)³ = a³ + 3a²b + 3ab² + b³.

Легко заметить, что коэффициенты в правых частях этих формул взяты из соответствующих строк треугольника Паскаля. Оказывается, при любом натуральном n справедлива формула:  - которая называется формулой Бином Ньютона. Правую часть формулы называют разложением степени бинома. По этой же формуле вычисляется  , полагая  . В этом случае второе слагаемое будет со знаком минус, далее знаки чередуются.

Пример. Вычислить без калькулятора:

Решение: сначала возведем в четвертую степень двучлен: 
  .

Поэтому 

 ПОДСЧЕТ ВАРИАНТОВ С ПОМОЩЬЮ ГРАФОВ.

Граф – это геометрическая фигура, состоящая из точек (вершин) и соединяющих их отрезков (ребер). При этом с помощью вершин изображают элементы некоторого множества, а с помощью ребер – определенные связи между этими элементами. Точки – называются вершинами графа, они могут быть замены кругами прямоугольниками, картинками и др. для удобства иллюстрации. С помощью вершин изображают элементы некоторого множества. Отрезки – называются ребрами графа, могут заменяться любыми линиями.

 Решение задач 1. Полный граф – граф, в котором соединены все возможные вершины, т.е.все элементы множества, изображаемые графом, взаимосвязаны. Рассмотрим понятие полного графа на задаче:

Задача 1. Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно? А Б Г В Ответ: 6 партий.

2. Андрей, Борис, Виктор и Григорий после возвращения из летнего лагеря ребята обменялись фотографиями. Причем каждый мальчик подарил каждому по одной фотографии. Сколько фотографий было подарено .Решение: Данную задачу можно решить двумя способами

I способ – c помощью полного графа. Стрелки на ребрах графа с вершинами А, Б, В, Г (по первым буквам имен мальчиков) показывают процесс обмена, такой граф называется ориентированным. А БII способ – правило произведения. Каждый из мальчиков подарил друзьям по три фотографии,следовательно,3*4 = 12. Г В Ответ: 12 фотографий.

. Граф-дерево – граф, который имеет одну вершину, порождающую все другие. В такого вида графах каждая предыдущая вершина порождает следующие. Свое название получил за внешнее сходство с деревом. Рассмотрим понятие графа-дерева на задаче: Задача 3. Антон (А), Борис (Б), Василий (В) купили 3 билета на футбольный матч на 1, 2, 3- е места первого ряда. Сколькими способами они могут занять имеющиеся три места? Способы 1 место А Б В А Б 2 место Б В А В 3 место Б А В Б В А Ответ: 6.

Итог занятия.

ПРИЛОЖЕНИЯ

Приложение 1. Треугольник Паскаля.

n \ m

0	1	2	3	4	5	6	7
0	1	.	.	.	.	.	.	.
1	1	1	.	.	.	.	.	.
2	1	2	1	.	.	.	.	.
3	1	3	3	1	.	.	.	.
4	1	4	6	4	1	.	.	.
5	1	5	10	10	5	1	.	.
6	1	6	15	20	15	6	1	.
7	1	7	21	35	35	21	7	1

Приложение 2. Треугольник Паскаля (в виде равнобедренного треугольника).

1 1        1 1        2        1 1        3        3        1 1        4        6        4        1  1       5        10      10       5       1   1      6        15       20      15      6      1   1       7       21      35      35       21      7      1

Приложение 3. Схема определения вида комбинации.