Класс: 5
В данной статье рассмотрим один из уроков в курсе математики 5 класса, посвященного знакомству с комбинаторикой.
Цели урока.
Образовательные :
Познакомить учащихся с новым типом задач (комбинаторные задачи), приемами их решения – перебор возможных вариантов, построение дерева возможных вариантов, применение правила умножения;
Ввести новое понятие – факториал, закрепить его при решении задач, примеров, уравнений.
Воспитательные :
Формирование уважения к товарищам, умения слушать и слышать собеседника
Формирование отношения к дружбе как одной из важнейших человеческих ценностей.
Развивающие :
Формирование интереса к предмету;
Формирование вычислительных навыков;
Развитие логического мышления;
Формирование умения доказывать, обосновывать свое мнение.
Ход урока
1. Организационный момент
Учитель: Сегодня у нас с вами необычный урок. Мы будем решать задачи, связанные с одним из интереснейших разделов математики – комбинаторикой. В науке и в реальной жизни очень часто приходится решать задачи, главным вопросом которых является вопрос “Сколькими способами это можно сделать?”. Например:
Сколькими способами можно поставить ученику оценку на уроке?
Сколькими способами можно назначить дежурного в классе?
Сколькими способами можно назначить двух дежурных в классе?
Решая такие задачи, приходится составлять различные комбинации из конечного числа элементов и подсчитывать число комбинаций. Такие задачи получили название комбинаторных задач, а раздел математики, в котором рассматриваются подобные задачи, называют комбинаторикой. А какой еще теме будет посвящен урок, вы узнаете, когда мы проверим, как вы справились с выполнением домашнего задания.
2. Проверка выполнения домашнего задания
(На предыдущем уроке домашнее задание составляется таким образом, чтобы заданий было ровно 6. Например, в учебнике Виленкина Н.Я. и др. это могут быть № 693(а, в), 735(1), 765(а,б,в))
На доске – таблица и закрепленные магнитами карточки. На карточках с одной стороны – ответ к заданию из домашней работы, с другой стороны – буква.
Учитель: Проверим домашнюю работу. Откройте тетради, возьмите карандаши. Найдите ответы к номерам домашней работы.
Учащиеся выходят к доске по одному, выбирают карточку с ответом и прикрепляют ее в ячейку таблицы под номером задания. Сначала карточки закрепляют в клетках таблицы вверх стороной, на которой записан ответ, чтобы учащиеся могли проверить правильность выполнения домашней работы. Остальные проверяют свои ответы в тетрадях.
| № упражнений | 693(а) | 693(в) | 735(1) | 765(а) | 765(б) | 765(в) |
| Ответы | 25 | 13 | 6 | 182 000 | 6 300 | 65 000 |
Варианты ответов (располагаются на разных сторонах карточек). Карточек делают заведомо избыточное количество, чтобы часть ответов была неверной.
| д | р | у | ж | б | а | м | п | о |
| 25 | 13 | 6 | 182 000 | 6 300 | 65 000 | 49 | 12 | 18 200 |
“5” - если все верно
“4” - если одна ошибка
“3” - 2-3 ошибки
“2” - больше 3 ошибок
Учитель: Перевернем карточки, какое слово получили? (ДРУЖБА). Действительно, сегодня на уроке мы будем не только решать математические задачи, совершенствовать навыки вычислений, но и говорить о дружбе.
3. Новый материал.
Учитель: Итак, мы уже сказали, что будем сегодня учиться решать задачи, главным вопросом которых является вопрос “Сколькими способами..”.
Имеются три слова “ДРУЖБА”, “ДЕЛО”, “ЛЮБИТ” (нарезать листочки с этими словами – по 7 карточек на каждое слово). Сколькими способами из этих слов можно составить фразу?
Учащиеся предлагают варианты, эти варианты составляют на доске.
Ответ: 6 способов.
Учитель: Как вы думаете, какой вариант является верным с точки зрения русского языка? (Дружба любит дело). Как вы понимаете это высказывание?
Учитель: Здесь был приведен полный перебор всех возможных вариантов, или, как обычно говорят, всех возможных комбинаций. Поэтому это комбинаторная задача. Давайте подумаем, как можно записать, оформить решение этой задачи.
1 способ. Обозначим предложенные слова заглавными буквами:
ДРУЖБА – Д
ЛЮБИТ – Л
ДЕЛО – Е (возьмем вторую букву этого слова)
Тогда все названные вами способы можно просто перечислить: ДЛЕ, ДЕЛ, ЛДЕ, ЛЕД, ЕДЛ, ЕЛД.
Оказывается, решение можно оформить в виде модели, которую называют деревом возможных вариантов. Она, во-первых, наглядна, как всякая картинка, и, во-вторых, позволяет все учесть, ничего не пропустив,
Учащиеся под руководством учителя составляют схему:
Способ 3 (рассуждение)
На первом месте может стоять одно из трех слов: ДРУЖБА, ЛЮБИТ, ДЕЛО. Если первое слово выбрано, то на втором месте может стоять одно из двух оставшихся слов, а на третьем месте – только одно оставшееся слово. Значит, всего вариантов: .
Заметим, что последний прием называется правилом умножения.
У каждого из этих трех способов есть свои преимущества и свои недостатки (обсудить) Выбор решения – за вами! Отметим все же, что правило умножения позволяет в один шаг решать самые разнообразные задачи.
У Ани 3 подруги, и она каждой из них купила по шоколадке и хочет подарить их к празднику. Сколькими способами она может это сделать?
Решение: Решение выполняют на доске ученики (решение выполняется 3 способами)
В компании друзей – 6 человек: Андрей, Борис, Витя, Гриша, Дима, Егор. В школьной столовой за столом 6 стульев. Друзья решили каждый день, завтракая, рассаживаться на эти 6 стульев по-разному. Сколько раз они смогут это сделать без повторений?
Учитель: Какой способ мы выберем? (Учащиеся под руководством учителя должны придти к выводу, что это третий способ – правило умножения).
Решение оформляет на доске ученик.
Для удобства рассуждений будем считать, что друзья усаживаются за стол поочередно. Будем считать, что первой усаживается за стол Андрей. У него 6 вариантов выбора стула. Вторым усаживается Борис, и независимо выбирает стул из 5 оставшихся. Витя делает свой выбор третьим и на выбор у него будет 4 стула. У Гриши будет уже 3 варианта, у Димы – 2, у Егора – 1. По правилу умножения получаем:
Ответ – 720 дней или почти 2 года.
Учитель: Как мы видим, условия задач разные, а решения, по сути дела, одинаковы. Удобно, поэтому ввести и одинаковые обозначения для этих ответов.
Определение: произведение всех натуральных чисел от 1 до п включительно называется п – факториал и обозначается символом п!
Знак п ! читается “Эн факториал”, что в дословном переводе с английского языка обозначает “состоящий из п множителей”. Отметим важную особенность этой величины – ее быстрый рост.
Вычислите:
а) 1!; б) 2!; в) 3!; г) 4!; д) 5!; е)10!
Считают, что 0! =1 (записать)
Задача 5.
Учитель: ДРУЖБА – одно из важнейших богатств, которое может быть у человека. Недаром о дружбе слагаются стихи и песни, сочиняют пословицы и поговорки. Какие пословицы и поговорки о дружбе вы знаете?
Друзья познаются в беде.
Не имей сто рублей, а имей сто друзей.
Один в поле не воин.
Сам погибай, а товарища выручай.
Старый друг лучше новых двух.
Без друга в жизни туго.
Молодцы! Для каждого человека очень важно, чтобы у него были хорошие, настоящие друзья. Давайте решим несколько примеров с применением нового понятия – факториал, и узнаем новую пословицу о дружбе.
| 7!+ | 8! – (13 - 5) 2 | 6! – 5! | ||
Карточки с ответами выполняют с запасом (есть карточки с числами, не являющимися ответами).
Таблица после заполнения:
| 7!+ | 8! – (13 - 5) 2 | 6! – 5! | ||
| 5048 | 40256 | 600 | 24 | 7 |
| Нет | друга - | ищи, | а нашел - | береги |
Задание 6.
К Васе в гости пришли 4 друзей, и они собираются смотреть новый фильм. У Васи в комнате есть кресло и еще он принес 4 стула из кухни. Кресло он, несомненно, займет сам, а на стульях рассадит своих друзей. Вася подсчитал, что рассадить друзей он сможет 24 способами.
Учитель: Правильно ли рассчитал Вася? (Да, с точки зрения математики)
Хорошо ли он поступил? (Обсуждается моральный аспект проблемы)
4. Физкультурная минутка.
Учитель: А теперь давайте немного отдохнем, а для этого проведем физкультурную минутку. Если я правильно прочитаю выражение, то вы встаете и поднимаете руки вверх, а если неправильно – садитесь, руки в бок.
Встали. Начинаем, будьте внимательны.
| Выражение | Слова учителя | Верно / неверно |
| 5! +3 | Сумма 5! и 3 | + |
| 2 – 7! | Произведение 2 и 7! | - |
| 4х: 2! | Частное 4х и 2! | + |
| 5! + 7! + 3! | Сумма 5!, 7! и 3! | + |
| 20! - 19! | Частное 20! и 19! | - |
6. Самостоятельная работа.
Учитель: Ну, а теперь, когда мы хорошо отдохнули, давайте проверим, что мы научились делать сегодня на уроке. Для этого выполним самостоятельную работу.
| Вариант 1 | Вариант 2 |
| 1. В 5 классе в среду 5 уроков: математика, русский язык, литература, музыка и труд. Сколько вариантов расписания на день можно составить? | 1. Шесть разных писем раскладывают в 6 разных конвертов. Сколько существует способов такого раскладывания? |
| 2. Вычислите: а) 6! – 2; б) 4! + (2+3) 2 |
2. Вычислите: а) 3 2 + 5! б) (9-4) 2 + 4! |
| 3. Сколькими способами 5 мальчиков могут занять очередь к билетной кассе, если первым все равно будет Толя? | 3. Сколькими способами Даша может съесть обед, состоящий из первого, второго, третьего и пирожного, если первым она наверняка съест пирожное? |
7. Домашнее задание.
Придумать, записать условия и решения 2 комбинаторных задач на тему “Семья”. Оформить на листах А4, можно выполнить рисунки к задачам.
8. Итог урока.
Давайте подведем итоги урока.
Что нового узнали? (Получили правило умножения, рассмотрели его геометрическую модель – дерево вариантов, ввели новое понятие – факториал)
Что понравилось?
Что запомнилось?
Оценки за урок.
Литература:
- Е.А.Бунимович, В.А. Булычев. Вероятность и статистика в курсе математики общеобразовательной школы: лекции 1- 4, 5 – 8. – М.: Педагогический университет “Первое сентября”, 2006.
- Виленкин Н.Я. Математика. 5 класс: учебник для общеобразоват. учреждений/ Н.Я.Виленкин и др. – М. : Мнемозина, 2009.
- Смыкалова Е.В. Дополнительные главы по математике для учащихся 5 класса. СПб: СМИО. Пресс, 2006.
- Мордкович А.Г. События. Вероятности. Статистическая обработка данных: Доп. Параграфы к курсу алгебры 7-9 кл. общеобразовательных учреждений / А.Г. Мордкович, П.В. Семенов. – М.: Мнемозина, 2006.
При решении многих практических задач приходится использовать комбинации элементов, выбирать из данной совокупности те, которые имеют определенные свойства, и размещать их в определенном порядке. Такие задачи называются комбинаторными . Раздел математики, посвящённый решению задач выбора и расположения элементов в соответствии с данными условиями, называется комбинаторикой. Термин «комбинаторика» происходит от латинского слова «combina» , что в переводе на русский язык означает – «сочетать», «соединять».
Выбранные группы элементов называют соединениями. Если все элементы соединения разные, то получаем соединения без повторений, которые и рассмотрим ниже.
Большинство комбинаторных задач решается с помощью двух основных правил – правила суммы и правила произведения .
Задача 1.
В магазине «Все для чая» есть 6 разных чашек и 4 разных блюдца. Сколько вариантов чашки и блюдца можно купить?
Решение .
Чашку мы можем выбрать 6-ю способами, а блюдце 4-я способами. Так как нам надо купить пару чашку и блюдце, то это можно сделать 6 · 4 = 24 способами (по правилу произведения).
Ответ: 24.
Для успешного решения комбинаторных задач надо еще и правильно выбрать формулу, по которой искать количество нужных соединений. В этом поможет следующая схема.
Рассмотрим решение нескольких задач на разные виды соединений без повторений.
Задача 2.
Найдите количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 7, если цифры в числе повторяться не могут.
Решение.
Для выбора формулы выясняем, что для чисел, которые мы будем составлять, порядок учитывается и не все элементы одновременно выбираются. Значит, это соединение – размещение из 7 элементов по 3. Воспользуемся формулой для числа размещений: A 7 3 = 7(7 – 1)(7 – 2) = 7 · 6 · 5 = 210 чисел.
Ответ: 210.
Задача 3.
Сколько существует семизначных телефонных номеров, в которых все цифры разные, а номер не может начинаться с нуля?
Решение.
На первый взгляд эта задача такая же, как и предыдущая, но сложность в том, что надо не учитывать те соединения, которые начинаются с нуля. Значит необходимо из существующих 10-ти цифр составить все семизначные номера телефонов, а потом от полученного числа отнять количество номеров, начинающихся с нуля. Формула будет иметь вид:
A 10 7 – A 9 6 = 10 · 9 · 8 · 7 · 6 · 5 · 4 – 9 · 8 · 7 · 6 · 5 · 4 = 544 320.
Ответ: 544 320.
Задача 4.
Сколькими способами можно расставить на полке 12 книг, из которых 5 книг – это сборники стихотворений, так, чтобы сборники стояли рядом?
Решение.
Сначала примем 5 сборников условно за одну книгу, потому что они должны стоять рядом. Так как в соединении существенным есть порядок, и все элементы используются, значит это перестановки из 8 элементов (7 книг + условная 1 книга). Их количество Р 8 . Далее будем переставлять между собой только сборники стихотворений. Это можно сделать Р 5 способами. Поскольку нам нужно расставить и сборники, и другие книги, то воспользуемся правилом произведения. Следовательно, Р 8 · Р 5 = 8! · 5!. Число способов будет большим, поэтому ответ можно оставить в виде произведения факториалов.
Ответ: 8! · 5!
Задача 5 .
В классе 16 мальчиков и 12 девочек. Для уборки территории возле школы нужно 4 мальчика и 3 девочки. Сколькими способами можно их выбрать со всех учеников класса?
Решение.
Сначала отдельно выберем 4 мальчика из 16 и 3 девочки из 12. Так как порядок размещения не учитывается, то соответственные соединения – сочетания без повторений. Учитывая необходимость одновременного выбора и мальчиков, и девочек, используем правило произведения. В результате число способов будет вычисляться таким образом:
С 16 4 · С 12 3 = (16!/(4! · 12!)) · (12!/(3! · 9!)) = ((13 · 14 · 15 · 16) / (2 · 3 · 4)) ·((10 · 11 · 12) / (2 · 3)) = 400 400.
Ответ: 400 400.
Таким образом, успешное решение комбинаторной задачи зависит от правильного анализа ее условия, определения типа соединений, которые будут составляться, и выбора подходящей формулы для вычисления их количества.
Остались вопросы? Не знаете, как решать комбинаторные задачи?
Чтобы получить помощь репетитора – зарегистрируйтесь .
Первый урок – бесплатно!
сайт, при полном или частичном копировании материала ссылка на первоисточник обязательна.
План:
1. Элементы комбинаторики.
2. Общие правила комбинаторики.
4. Применение графов (схем) при решении комбинаторных задач.
1. Комбинаторика и ее возникновение.Комбинаторика - это область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству.
Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры (карты, кости). Широко были распространены лотереи. Первоначально комбинаторные задачи касались в основном азартных игр: сколькими способами можно получить данное число очков, бросая 2 или 3 кости или сколькими способами можно получить 2-ух королей в некоторой карточной игре. Эти и другие проблемы азартных игр являлись движущей силой в развитии комбинаторики и далее в развитии теории вероятностей.
Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицы (числа способов выпадения k очков на r костях). Однако, он не учел, одна и та же сумма очков может выпасть различными способами, поэтому его таблицы содержали большое количество ошибок.
Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские математики Блез Паскаль и Ферма. Исходным пунктом их исследований были так же проблемы азартных игр.
Дальнейшее развитие комбинаторики связано с именами Я. Бернулли, Г. Лейбница, Л. Эйлера. Однако, и в их работах основную роль играли приложения к различным играм.
Сегодня комбинаторные методы используются для решения транспортных задач, в частности задач по составлению расписаний, для составления планов производства и реализации продукции и т.д.
2. Общие правила комбинаторики.Правило суммы: Если некоторый объект А может быть выбран m способами, а объект В- k способами, то объект «либо А, либо В» можно выбрать m +k способами.
Примеры:
1. Допустим, что в ящике находится n разноцветных шаров. Произвольным образом вынимается 1 шарик. Сколькими способами это можно сделать?
Ответ: n способами.
Распределим эти n шариков по двум ящикам: в первый- m шариков, во второй- k шариков. Произвольным образом из произвольно выбранного ящика вынимается 1 шарик. Сколькими способами это можно сделать?
Решение: Из первого ящика шарик можно вынуть m способами, из второго- k способами. Тогда всего способов m+k=n .
2. Морской семафор.В морском семафоре каждой букве алфавита соответствует определенное положение относительно тела сигнальщика двух флажков. Сколько таких сигналов может быть?
Решение: Общее число складывается из положений, когда оба флажка расположены по разные стороны от тела сигнальщика и положений, когда они расположены по одну сторону от тела сигнальщика. При подсчете числа возможных положений применяется правило суммы.
Правило произведения: Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора объекта А) k способами, то пары объектов «А и В» можно выбрать m *k способами.
Примеры:
1. Сколько двузначных чисел существует?Решение: Число десятков может быть обозначено любой цифрой от 1 до 9. Число единиц может быть обозначено любой цифрой от 0 до 9. Если число десятков равно 1, то число единиц может быть любым (от 0 до 9). Таким образом, существует 10 двузначных чисел, с числом десятков- 1.Аналогично рассуждаем и для любого другого числа десятков. Тогда можно посчитать, что существует 9 *10 = 90 двузначных чисел.
2. Имеется 2 ящика. В одном лежит m разноцветных кубиков, а в другом- k разноцветных шариков. Сколькими способами можно выбрать пару «Кубик-шарик»?
Решение: Выбор шарика не зависит от выбора кубика, и наоборот. Поэтому, число способов, которыми можно выбрать данную пару равно m *k .
3. Генеральная совокупность без повторений и выборки без повторений.Генеральная совокупность без повторений - это набор некоторого конечного числа различных элементов a 1 , a 2 , a 3 , ..., a n .
Пример: Набор из n разноцветных лоскутков.
Выборкой объема k (k n ) называется группа из m элементов данной генеральной совокупности.
Пример: Пестрая лента, сшитая из m разноцветных лоскутков, выбранных из данных n .
Размещениями из n элементов по k называются такие выборки, которые содержат по k элементов, выбранных из числа данных n элементов генеральной совокупности без повторений, и отличаются друг от друга либо составом элементов, либо порядком их расположения.
- число размещений из n по k .
Число размещений из n по k можно определить следующим способом: первый объект выборки можно выбрать n способами, далее второй объект можно выбрать n -1 способом и т.д.
Преобразовав данную формулу, имеем:
Следует помнить, что 0!=1.
Примеры:
1. В первой группе класса А первенства по футболу участвует 17 команд. Разыгрываются медали: золото, серебро и бронза. Сколькими способами они могут быть разыграны?
Решение:
Комбинации
команд-победителей отличаются друг от друга составом и порядком следования
элементов, т.е. являются размещениями из 17 по 3.
2. Научное общество состоит из 25-ти человек. Необходимо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами это можно сделать?
Решение: Комбинации руководящего состава общества отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 25 по 4.
Перестановками без повторений из n элементов называются размещения без повторений из n элементов по n , т.е. размещения отличаются друг от друга только порядком следования элементов.
Число перестановок.
Примеры:
1. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что они должны состоять из различных цифр?
Решение: Имеем перестановки из 5 элементов. 2. Сколькими способами можно собрать 6 разноцветных лоскутков в пеструю ленту?Решение: Имеем перестановки из 6 элементов.
Сочетаниями без повторений из n элементов по k называются такие выборки, которые содержат по k элементов, выбранных из числа данных n элементов генеральной совокупности без повторений, и отличаются друг от друга только составом элементов.
- число сочетаний из n по k
Элементы каждого из сочетаний можно расставить способами. Тогда Примеры:1. Если в полуфинале первенства по шахматам участвует 20 человек, а в финал выходят лишь трое, то сколькими способам и можно определить эту тройку?
Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки, вышедшие в финал, являются сочетаниями из 20 по 3.
2. Сколькими способами можно выбрать трех делегатов из десяти человек на конференцию?Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки делегатов являются сочетаниями из 10 по 3.
Конспект:
4.Применение графов (схем) при решении комбинаторных задач.
В случае, когда число возможных выборов на каждом шагу зависит от того, какие элементы были выбраны ранее, можно изобразить процесс составления комбинаций в виде «дерева». Сначала из одной точки проводят столько отрезков, сколько различных выборов можно сделать на первом шагу. Из конца каждого отрезка проводят столько отрезков, сколько можно сделать выборов на втором шагу, если на первом шагу был выбран данный элемент и т.д.
Задача:
При составлении команд космического корабля учитывается вопрос и психологической совместимости участников путешествия. Необходимо составить команду космического корабля из 3 человек: командира, инженера и врача. На место командира есть 4 кандидата: a 1 , a 2 , a 3 , a 4 .На место инженера- 3: b 1 , b 2 , b 3 . На место врача- 3: c 1 , c 2 , c 3 . Проведенная проверка показала, что командир a 1 психологически совместим с инженерами b 1 и b 3 и врачами c 1 и c 3 . Командир a 2 - с инженерами b 1 и b 2 . и всеми врачами. Командир a 3 - с инженерами b 1 и b 2 и врачами c 1 и c 3 . Командир a 4 -со всеми инженерами и врачом c 2 . Кроме того, инженер b 1 не совместим с врачом c 3 , b 2 - с врачом c 1 и b 3 - с врачом c 2 . Сколькими способами при этих условиях может быть составлена команда корабля?
Решение:
Составим соответствующее «дерево».
Ответ: 10 комбинаций.
Такое дерево является графом и применяется для решения комбинаторных задач.
КОМБИНАТОРИКА
Комбинаторика - раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.
Правила сложения и умножения в комбинаторике
Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В - n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.
Пример 1.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?
Решение
Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.
По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.
Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n 1 способами, второе действие n 2 способами, третье - n 3 способами и так до k-го действия, которое можно выполнить n k способами, то все k действий вместе могут быть выполнены:
способами.
Пример 2.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?
Решение
Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.
После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.
По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.
Сочетания без повторений. Сочетания с повторениями
Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?
Пример 3.
Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?
Решение
Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:
.
Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?
.
Пример 4.
В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Решение
Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.
.
Размещения без повторений. Размещения с повторениями
Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?
Пример 5.
В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?
Решение.
В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:
Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.
Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно вы б рать и разместить по m различным местам m из n предметов, с реди которых есть одинаковые?
Пример 6.
У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера- составить каталог. Сколько различных пятизначных номеров может составить мальчик?
Перестановки без повторений . Перестановки с повторениями
Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?
Пример 7.
Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?
Решение
Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. есть одинаковые предметы.
Пример 8.
Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
Решение
Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно
ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ "КОМБИНАТОРИКА"
Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиально возможное количество различных вариантов развития событий.
Основная формула комбинаторики
Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *...*n k .
Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n 1 элементов, а вторая - из n 2 элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n 2 . Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n 2 . Так как в первой группе всего n 1 элемент, всего возможных вариантов будет n 1 *n 2 .
Пример 2.
Сколько
трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если
цифры могут повторяться?
Решение:
n 1 =6
(т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n 2 =7
(т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5,
6), n 3 =4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4,
6).
Итак, N=n 1 *n 2 *n 3 =6*7*4=168.
В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =...n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k . Такой способ выбора в комбинаторики носит название выборки с возвращением.
Пример 3.
Сколько всех четырехзначных чисел
можно составить из цифр 1, 5, 6, 7, 8?
Решение.
Для каждого разряда
четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625.
Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью .
Число размещений из n элементов по m
Определение 1. Размещением из n элементов по m в комбинаторике называется любой упорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.
Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.
Число размещений в комбинаторике обозначается A n m и вычисляется по формуле:
Замечание: n!=1*2*3*...*n (читается: "эн факториал"), кроме того полагают, что 0!=1.
Пример 5
. Сколько существует двузначных
чисел, в которых цифра десятков и цифра единиц различные
и нечетные?
Решение:
т.к. нечетных цифр
пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на
две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:
Определение 2. Сочетанием из n элементов по m в комбинаторике называется любой неупорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.
Пример 6 . Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.
Число сочетаний из n элементов по m
Число сочетаний обозначается C n m и вычисляется по формуле:
Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся?
Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:
Перестановки из n элементов
Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.
Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).
Число различных перестановок из n элементов обозначается P n и вычисляется по формуле P n =n!.
Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд?
Решение: эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.
Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.
Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов).
Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.
И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.
Пример 9.
На родительском собрании
присутствует 20 человек. Сколько существует различных вариантов состава
родительского комитета, если в него должны войти 5 человек?
Решение:
В этом примере нас
не интересует порядок фамилий в списке комитета. Если в результате в его
составе окажутся одни и те же люди, то по смыслу для нас это один и тот же
вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний
из 20 элементов по 5.
Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок , которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.
Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5,
6, если цифры могут повторяться?
2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?
3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?
4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?
5. Сколькими способами можно разложить восемь различных писем по восьми различным конвертам, если в каждый конверт кладется только одно письмо?
6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?
