Методическая разработка по теме "Комбинаторика" для студентов 1 курса СПО
методическая разработка по алгебре (10 класс) по теме

Пояснительная записка.

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

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

        Комбинаторные навыки оказались полезными и в часы досуга. Нельзя точно сказать, когда наряду с состязаниями в беге, метании диска, прыжках появились игры, требовавшие, в первую очередь, умения рассчитывать, составлять планы и опровергать планы противника.

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

        Комбинаторика как наука стала развиваться в 18 веке параллельно с возникновением теории вероятностей, так как для решения вероятностных задач необходимо было подсчитать число различных комбинаций элементов. Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж.Кардано, Н.Тарталье (1499-1557), Г.Галилею (1564-1642) и французским ученым Б.Паскалю (1623-1662) и П.Ферма.

        Комбинаторику как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г.Лейбниц в своей работе “Об искусстве комбинаторики ”, опубликованной в 1666 году. Он также впервые ввел термин “комбинаторика”. Значительный вклад в развитие комбинаторики внес Л.Эйлер. В современном обществе с развитием вычислительной техники комбинаторика “добилась” новых успехов. В настоящее время в образовательный стандарт по математике включены основы комбинаторики, решение комбинаторных задач методом перебора, составлением дерева вариантов (еще его называют “дерево возможностей”) с применением правила умножения.        В комбинаторике решаются задачи, связанные с рассмотрением множеств и составлением различных комбинаций из элементов этих множеств. В зависимости от правил составления можно выделить три типа комбинаций: перестановки, размещения, сочетания.

        Данная работа содержит необходимый теоретический материал, а также большое количество различных заданий.

        Изучение темы "Комбинаторика" осуществляется на 5 занятиях. Распределение тем по занятиям может быть следующим:

1 занятие: Дерево возможных вариантов. Правило умножения.  Перестановки без повторений.

2 занятие: Перестановки с повторениями.

3 занятие: Выбор нескольких элементов. Размещения. Сочетания.

4 занятие: Решение комбинаторных задач.

5 занятие: Бином Ньютона.

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

• на 2 занятии (15 минут)
• на последнем занятии (25 минут).

Задания для самостоятельной работы прилагаются.

Содержание.

1. Решение занимательных задач (самостоятельная работа студентов).

1. Маша на свой день рождения пригласила в гости трех лучших подруг - Дашу, Глашу и Наташу. Когда все собрались, то по случаю дня рождения Маши решили обняться - каждая пара по одному разу. Сколько получилось разных пар?
2. На пустую шашечную доску надо поместить две шашки разного цвета. Сколько различных положений могут они занимать на доске?
3. Сколько способов разместить две ладьи на шахматной доске, так, чтобы каждая из них не смогла побить вторую?
4. В ящике лежат 70 шаров: 20 красных, 20 синих, 20 желтых, остальные черные и белые. Какое наименьшее число шаров надо взять, не видя их, чтобы среди них было не меньше 10 шаров одного цвета? 
5. На международную конференцию приехали 10 делегатов, не понимающих языка друг друга. Какое минимальное число переводчиков потребуется для обслуживания конференции при условии, что каждый переводчик знает только два языка?
6. Перед нами 10 закрытых замков и 10 похожих ключей к ним. К каждому замку подходит только один ключ, но ключи смешались. Возьмем один из замков, назовем его первым и попробуем открыть его каждым из 10 ключей. В лучшем случае он откроется первым же ключом, а в худшем - только десятым.
   Сколько нужно в худшем случае произвести проб, чтобы определить какой ключ от какого замка?
7. В магазине "Все для чая'' есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?

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

Задача 1. На завтрак Вова может выбрать плюшку, бутерброд, пряник или кекс, а запить их может кофе, соком или кефиром. Из скольких вариантов завтрака Вова может выбрать решение?

Решение. Соберем все варианты в таблице:

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

Ответ: 12.

Упражнения.

Составив таблицы, решите задачи:

1. Алфавит племени Мумбо-Юмбо состоит из букв А, Б, В, Г. Словом является любая последовательность из возможных 4 букв (буквы могут повторяться). Столько слов в языке племени Мумбо-Юмбо.
2. Из города А в город В можно добраться по железной дороге, на автобусе по шоссе и на катере по реке. Из города В в город С ведет железная дорога, шоссейная трасса, проселочная дорога, а также курсирует катер. Сколькими способами можно добраться из А в С?
3. Сколько четных двузначных чисел можно записать с помощью цифр 0, 1, 2, 4, 5, 9?

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

Задача 2. Флаг России состоит из трех горизонтальных полос: белой, синей и красной. Флаг Франции состоит из тех же полос, но в другом порядке. Сколько всего различных флагов можно придумать из этих полос?

Решение.

Будем искать решение с помощью дерева возможных вариантов.

Ответ: 6.

Упражнения.

Постройте дерево возможных вариантов и решите задачи:

1. Из четырех тузов поочередно выбирают два.

а) в скольких случаях среди выбранных будет бубновый туз?

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

в) в скольких случаях тузы будут разного цвета?

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

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

        Задачи, которые были рассмотрены выше, очень хорошо иллюстрируют одно из основных правил комбинаторики – правило умножения. Для двух испытаний оно звучит так:

если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать п способами, то выбор пары (А, В) в указанном порядке можно осуществить m∙п способами.

        Например, в задаче про Вову еду он мог выбрать 4 способами, а напиток 3-мя. Используя правило умножения, получаем 3∙4=12. Построенная нами таблица доказывает правильность данного правила, ведь число клеток в ней равно произведению числа строк на число столбцов.

        Для трех и более испытаний данное правило тоже работает, только число множителей будет совпадать с числом объектов.

Задача 3. В магазине «Все для чая» есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?

Решение:

Выберем чашку. В комплект к ней можно выбрать любое из трех блюдец. Поэтому есть 3 разных комплекта, содержащих выбранную чашку. Поскольку чашек всего 5, то число различных комплектов равно 15 (15 = 5 • 3).

Ответ: 15.

Задача 4. В магазине «Все для чая» есть еще 4 чайные ложки. Сколькими способами можно купить комплект из чашки, блюдца и ложки?

Решение:

Выберем любой из 15 комплектов предыдущей задачи. Его можно дополнить ложкой четырьмя различными способами. Поэтому общее число возможных комплектов равно 60 (60 = 15 • 4 = 5 • 3 • 4).

Ответ: 60.

Упражнения.

1. Бросают игральную кость с 6 гранями и запускают волчок, имеющий 8 граней. Сколькими различными способами могут они упасть?
2. В Стране Чудес есть три города: А, Б и В. Из города А в город Б ведет 6 дорог, а из города Б в город В – 4 дороги. Сколькими способами можно проехать от А до В?
3. В футбольной команде (11 человек) нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?
4. На доске написаны 7 существительных, 5 глаголов и 2 прилагательных. Для предложения нужно выбрать по одному слову каждой из этих частей речи. Сколькими способами это можно сделать?
5. Сколько существует треугольников, длины сторон которых принимают одно из значений 4,5,6,7?
6. Сколько существует неравносторонних треугольников, длины сторон которых принимают одно из значений: 6, 7, 8, 9, 10, 11?
7. Сколькими способами можно выбрать два особняка в престижном районе Лондона из предлагаемых пяти?
8. Множество М состоит из букв М = {Д, П, О, А, К}. Сколько различных трехбуквенных слов можно составить из букв этого множества, если:

а) буквы не повторяются,

б) буквы могут повторяться.

В каждом из случаев приведите примеры слов, имеющих смысловое значение и не имеющих его.

1. Нужно сшить платье из материала 4-х цветов так, чтобы было использовано три разных цвета, но чтобы обязательно присутствовал белый. Сколькими способами это можно сделать?
2. Стадион «Динамо» имеет 4 выхода. Сколькими способами можно войти через один вход и выйти через другой?
3. В футбольном турнире участвуют 8 команд. В первом туре каждая команда должна сыграть по одной игре. Сколько всего игр пройдет в первом круге?
4. Встретились 6 человек и каждый пожал руку другому. Сколько всего было рукопожатий?
5. Сколько диагоналей можно провести в пятиугольнике? 10-ти угольнике? n-угольнике?

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

если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m+n способами.

Задача 5. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?

Решение. По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу сложения, можно осуществить 5+4=9 способами.

Ответ: 9.

Упражнения.

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

 2. На полке стоят 5 книг. Сколькими способами можно выложить в стопку несколько из них (стопка может состоять и из одной книги)?

3. Перестановки без повторений.

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

первая полоса может быть выбрана одним из трех цветов,

вторая – одним из оставшихся двух,

третья – одним последним.

Применяя правило произведения, получаем 3·2·1=6.

Задача 6. У Вовы на обед – первое, второе, третье блюда и пирожное. Он не хочет есть как полагается. Найдите число возможных вариантов обеда.

Решение. Первым блюдом Вова может съесть любое из предложенных (4 варианта),

вторым – одно из оставшихся (три варианта),

третьим – опять одно из оставшихся (два варианта),

а четвертым – то, что осталось.

Таким образом, число вариантов равно 4·3·2·1=24.

Ответ: 24.

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

Определение. Произведение первых подряд идущих n натуральных чисел называется факториал и обозначается n!, причем, если  n = 0, считают n! = 1.

Для решения задачи на определение числа возможны перестановок пользуются следующим правилом

n различным элементам можно присвоить номера от 1 до n ровно n! различными способами.

Задача 7. У Лены есть 8 разных красок. Она хочет написать ими слова «Новый Год». Сколькими способами она может это сделать, если каждая буква может быть раскрашена одним цветом и все 8 букв должны быть разные по цвету.

Решение.

Число возможных вариантов равно

40320

Ответ: 40320

Упражнения.

1. С понедельника по пятницу Оля посещает дополнительные занятия по физике, математике, химии, русскому и английскому языках (по одному предмету в день). Сколько у Оли способов составить расписание дополнительных занятий на неделю?

2. Семеро терпеливых стоят в очереди в кассу. Сколькими способами можно составить очередь?

3.  Сколькими способами можно расставить на полке 6 различных книг?

4. Сократите дробь:

1)  , 2) , 3) , 4) , 5)

5. Вычислите:

1) , 2) ,  3) , 4) .

1. Перестановки с повторениями.

Задача 8. Сколькими способами можно переставить буквы в следующих словах?

а) «ВЕКТОР»;

б) «ЛИНИЯ»;

в) «ПАРАБОЛА»;

г) «БИССЕКТРИСА»;

д) «МАТЕМАТИКА».

Решение:

а) Так как все буквы слова различны, то всего можно получить 6! слов.

б) В этом слове две буквы И, а все остальные буквы разные. Временно будем считать разными и буквы И, обозначив их через И1 и И2. При этом предположении получится 5! = 120 разных слов. Однако те слова, которые получаются друг из друга только перестановкой букв И1 и И2, на самом деле одинаковы. Таким образом, полученные 120 слов разбиваются на пары одинаковых. Поэтому разных слов всего 120:2 = 60.

в) Считая три буквы А этого слова различными (А1, А2, А3), получим 8! разных слов. Однако слова, отличающиеся лишь перестановкой букв А, на самом деле одинаковы. Поскольку буквы А1, А2, А3 можно переставлять 3! способами, все 8! слов разбиваются на группы по 3! одинаковых. Поэтому разных слов всего

г) В этом слове три буквы С и две буквы И. Считая все буквы различными, получаем 11! слов. Отождествляя слова, отличающиеся лишь перестановкой букв И, но не С, получаем 11!/2! различных слов. Отождествляя теперь слова, отличающиеся перестановкой букв С, получаем окончательный результат  

д) Ответ:  

Упражнения.

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

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

3. Найти количество четырехзначных чисел, получаемых при всевозможных перестановках цифр 1,2,2,5?

4.  Сколько различных браслетов можно сделать из 5 одинаковых изумрудов,6 одинаковых рубинов, 7 одинаковых сапфиров (В браслет входят все 18 камней?).

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

1. Выбор нескольких элементов.

Задача 9. В классе 27 учеников, из которых нужно выбрать троих. Сколькими способами это можно сделать, если:

а) первый ученик должен решить задачу, второй – сходить за мелом, третий – пойти дежурить в столовую?

б) им следует спеть хором?

Решение. 

а) В первом случае важен порядок вызова учеников и применимо правило умножения. Один из 27 учеников решает задачу. Один из оставшихся 26 учеников идет за мелом, а один из оставшихся 25 будет дежурным в столовой. Получается  способов вызова.

б) Во втором случае начнем действовать, вызывая учеников по порядку (123). Можно вызвать этих же учеников и в другом порядке, например, (132) или (321). Во всех  случаях состав хора будет одним и тем же. Порядок выбора в данном случае нам не важен, а значит число возможных вариантов, полученных в первом случае нужно разделить на количество перестановок из трех элементов. В итоге имеем: .

Определение. Конечные  упорядоченные подмножества, содержащие по m элементов основного множества, называются размещениями из n элементов по m элементов.

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

Определение. Конечные  неупорядоченные подмножества, содержащие по m элементов основного множества, называются сочетаниями из n элементов по m элементов.

Число всех возможных сочетаний из n элементов по m элементов обозначается .

        Задачи на размещения можно решать пользуясь правилом умножения, но можно вывести формулу для нахождения  используя факториал.

        Один элемент из n можно выбрать n  способами. Таким образом: .

        Два элемента можно выбрать  способами.

        Три элемента можно выбрать  способами.

        ……………………………………………………

Рассуждая аналогично, получаем:

Задача 10.  В классе 30 учеников. Необходимо избрать старосту, культорга и редактора стенгазеты. Сколькими способами это можно сделать, если одно лицо может занимать только один пост.

Решение. В данном случае нам важен порядок выбора каждого ученика, поэтому можно использовать формулу для количества размещений. При этом, n = 30, m = 3.

.

Ответ: 24360 способов.

        Выведем формулу для числа сочетаний. Так как при решении задач на сочетания нам не важен порядок выбранных m элементов, число всех возможных сочетаний меньше числа возможных размещений равно в m! раз. Таким образом:

.

Задача 11. Тренер отбирает 5 спортсменов из 12. Сколькими способами он может составить команду?

Решение. Порядок выбора спортсменов в данном случае не важен. Используем формулу для количества сочетаний, учитывая, что n = 12, m = 5.

.

Ответ: 792 способа.

Упражнения.

1. На складе имеются 5 одинаковых деталей. Мастеру необходимо выбрать 4 детали. Сколькими способами он может это сделать? Ответ обоснуйте.
2. Расписание одного дня состоит из 5 уроков. Определить число вариантов расписания при выборе из 11 дисциплин.
3. У людоеда в подвале томятся 25 пленников.

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

б) А сколько есть способов выбрать троих, чтобы отпустить на свободу?

1. Иногда номера трамваев обозначают двумя цветными фонариками. Какое количество различных маршрутов можно обозначить, используя фонари восьми различных цветов.
2. Из команды, которая состоит из 15 спортсменов, выдвигают 4 участника эстафеты 800м. + 400м. + 200м. +100м. Сколько существует способов такого выбора?
3. Из 20 вопросов к экзамену Вова выучил 12. На экзамене в билете будет три вопроса.

а) сколько существует вариантов билетов?

б) сколько из них тех, в которых Вова знает все вопросы?

1. Из 12 резервных троллейбусов в троллейбусном парке нужно выпустить на линию по одному дополнительному троллейбусу на каждый из 7 маршрутов. Сколько существует способов это сделать?
2. Назовем натуральное число «симпатичным», если в его записи встречаются только нечетные цифры. Сколько существует 4-значных «симпатичных» чисел?
3. Сколькими способами можно выбрать 3 цветка из вазы, в которой стоят 10 красных и 4 розовых гвоздики?
4. Из состава конференции в 52 человека нужно избрать делегацию из 5 человек. Сколькими способами это можно сделать?
5. В подразделении 60 солдат 5 офицеров. Сколькими способами можно выделить караул, состоящий из 3 солдат и одного офицера?
6. В мешке лежат 3 красных и 5 синих шариков. Сколькими способами можно выбрать из них 2 любых шарика? Сколькими способами можно выбрать из них 2 синих шарика? Воспользуйтесь формулой для числа сочетаний.
7. Четверо студентов сдают экзамен. Сколькими способами могут быть поставлены им оценки, если известно, что никто из них не получил неудовлетворительную оценку?
8. Сколькими способами из девяти книг можно отобрать четыре, так, чтобы определенная книга не входила в их число?
9. . На собрании должны выступать 5 человек: А, Б, В, Г и Д. Сколькими способами можно расположить их в списке ораторов при условии, что А должен выступать непосредственно перед Д?
10. В колоде 36 карт. Наудачу вынимают 3 карты. Каково число всех возможных комбинаций? Сколько троек содержит, по крайней мере, один туз? Сколько троек содержат только один туз?
11. В рекламного агентстве имеется 19 агентов и четыре менеджера. Сколькими способами можно составить бригаду, состоящую из трех агентов и одного менеджера?
12. Сколько вариантов команды можно создать из 5 нападающих, 7 защитников и 4 вратарей, если команда состоит из 3 нападающих, 2 защитников и одного вратаря?
13. На пять сотрудников выделены три путевки. Сколькими способами их можно распределить, если:

а) все путевки различны;

б) все путевки одинаковы?

1. Бином Ньютона.

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

Выясним, какими свойствами обладают эти числа.

Задача 12. Найти , где m = 0, 1, 2, 3, 4, 5.

Решение.

,  , , , , .

Анализируя полученные результаты, можно сделать следующие выводы:

1. Коэффициенты, равностоящие от начала и конца, равны между собой, т.е. .
2. Сумма всех коэффициентов равно .
3. Сумма коэффициентов, стоящих на четных местах равна сумме коэффициентов, стоящих на нечетных местах.

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

 Напишем в первой строке число 1.

Под ним еще две единицы.

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

        В данном треугольнике, первая строка считается нулевой и первый элемент в строки тоже. Тогда, в пятой строке треугольника Паскаля можно найти все те коэффициенты, которые мы нашли в предыдущей задаче.

        Биноминальные коэффициенты играют в математике большую роль. Именно они являются коэффициентами многочлена при возведении в степень любого двучлена. Всем известно формула сокращенного умножения: . Коэффициенты перед одночленами в данном трехчлене можно найти во второй строке треугольника Паскаля. Аналогично, при возведении в третью степень получаем: . Сделать это значительно проще, чем умножать между собой три скобки, а потом приводить подобные слагаемые. Степени a и b в искомом многочлене располагаются по следующей зависимости: степень a начинается с 3 и уменьшается до 0, степень b наоборот.

Упражнения.

1. Возвести в степень двучлены:

1. , 2) .

1. Сколько раз встретится одночлен  при возведении в степень n, если:

1. n = 7, m = 2, k = 5;  2) n = 8, m = 6, k = 2; 3)  n = 10,  m = 3, k = 7; 4)  n = 12, m = 5, k = 7.

1. Чему равна сумма коэффициентов в разложении:

1. ,    2) .

Литература.

1. М.И. Башмаков, Математика, М, Академия, 2010
2. А.Г.Мордкович, П.В. Семенов, События. Вероятности. М. Мнемозина, 2005
3. http://www.matburo.ru/