Элементы комбинаторики и теории вероятности в школьном курсе

n(А∪В)=n(А)+n(В)-n(А∩В).

Правило суммы также может быть представлено кругами Эйлера:

Рисунок 1.2.2.1

Элементы, которые относятся и к множеству А и к множеству В, отмечены двойной штриховкой. Так как эти элементы множеств повторяются, они исключаются единожды из объединения множеств.

Пример 1. Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?

Решение: А = 17, В = 13

По правилу суммы АUВ = 17+13=30 тем.

Пример 2. Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет из спортлото или автомотолотереи?

Решение: Так как денежно-вещевая лотерея в выборе не участвует, то всего 6+10 = 16 вариантов.

Пример 3. 20 человек знают английский и 10 – немецкий, из них 5 знают и английский, и немецкий. Сколько Человек всего?

Ответ: 10+20-5 = 25 человек.

Пример 4. Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским - 42. Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько туристов не владеют ни одним языком?

Решение: Выразим условие этой задачи графически. Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий.

Рисунок 1.2.2.2

Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким. Следовательно, только английским и французским владеют 10-3=7 человек.

Аналогично получаем, что только английским и немецким  владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста. Вносим эти данные в соответствующие части.

Рисунок 1.2.2.3

Определим теперь, сколько человек владеют только одним из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским - 30 человек.

Рисунок 1.2.2.4

По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков.

Правило произведения.

Рассмотрим следующую задачу:

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

Выпишем сначала бутерброды с белым хлебом. Это бутерброд с сыром (БС), с колбасой (БК) и вареньем (БВ). Столько же бутербродов можно приготовить и с черным хлебом; ЧС, ЧК, ЧВ. Всего получается 6 видов бутербродов. Это число можно найти с помощью так называемого комбинаторного правила умножения.

Если элемент a можно выбрать m способами, а элемент b выбрать n способами, то пару (a, b) можно выбрать mn способами.

Чтобы найти число комбинаций из предметов нескольких типов, нужно перемножить количества предметов каждого типа.

Пример 5. Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?

Решение: Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 123 = 36 вариантов переплета.

Пример 6. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

Решение: В таких числах последняя цифра будет такая же, как и первая, а предпоследняя – как и вторая. Третья цифра будет любой. Это можно представить в виде XYZYX, где Y и Z – любые цифры, а X – не ноль. Значит по правилу произведения количество цифр одинаково читающихся как слева направо, так и справа налево равно 91010 = 900 вариантов.

Подсчитаем, например, сколько слов, содержащих 6 букв, можно составить из 33 букв русского алфавита при условии, что любые две стоящие рядом буквы различны (например, слово «корова» допускается, а слово «колосс» нет). При этом, разумеется можно писать бессмысленные слова. В этом случае на первое место у нас 33 кандидата. Но после того, как первая буква выбрана, вторую можно выбрать лишь 32 способами – ведь повторять первую букву нельзя. На третье место тоже 32 кандидата – первую букву уже можно повторить, а вторую – нельзя. Также убеждаемся, что на все места, кроме первого, имеется 32 кандидата. А так как число этих мест равно 5, то получаем ответ 33∙32∙32∙32∙32∙32=1107396236.

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

1. В отделе научно-исследовательского института работают несколько человек, причем каждый из них знает хотя бы один иностранный язык, 6 человек знают английский, 6 – немецкий, 7 – французский, 4 знают английский и немецкий, 3 – немецкий и французский, 2 – французский и английский, 1 человек знает все три языка. Сколько человек работает в отделе? Сколько из них знают только английский язык? Сколько человек знают только один язык?
2. Сколько чисел среди первых 100 натуральных чисел не делятся ни на 2, ни на 3, ни на 5?
3. Имеется 5 видов конвертов и 4 вида марок. Сколькими способами можно выбрать конверт и марку для посылки письма?
4. Сколькими способами можно выбрать на шахматной доске черный и белый квадраты, не лежащие на одной горизонтали или одной вертикали?
5. Имеется 20 тетрадей в линейку и 30 тетрадей в клетку. Необходимо выбрать две тетради одного вида. Сколько способов выбора двух тетрадей возможно, если учитывается порядок выбора тетрадей?

 

Методические рекомендации  к проведению занятия №2.

Занятие следует провести по следующему плану:

1) Выступления  учащихся

2) Игра «Что? Где? Когда?»

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

Далее занятие продолжается в форме игры «Что? Где? Когда?». Заранее заготовлено поле, разделенное на секции и стрелочка, которая устанавливается в центр поля. В игре участвуют три команды. Поочередно из каждой команды к полю подходит один ученик и крутит стрелочку. Затем из того сектора на который показывает стрелок зачитывается вопрос. Каждая команда решает поставленную задачу. Команда первой решившая задачу демонстрирует её решение на доске остальным командам. Если решение правильное, то ей присуждается 5 баллов.

Содержание занятия №2. «Размещения. Перестановки. Сочетания».

Размещения без повторений.

Пусть имеем n – элементное множество А и m различных позиций. Размещение без повторений – упорядоченная выборка без возвращения из n элементов по m. Количество размещений из n элементов по m обозначают .

Пример 1. Пусть имеется 4 шара и 3 пустых ячейки. Сколькими способами шары можно поместить в ячейки.

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

 

Размещения с повторениями.

Часто в задачах по комбинаторике встречаются множества, в которых какие-либо компоненты повторяются. Размещения с повторениями – упорядоченная выборка m элементов из n возможных. Для таких задач при размещениях используется формула .

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

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

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

Перестановкой без повторений из n элементов называется упорядоченная выборка n элементов из n возможных.

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

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

Таким образом, мы получили 3 2 1 =6 способов перестановки трех человек. На рисунке 1.2.2.5 показаны все эти способы. Очевидно, что данная задача является, случаем перестановок без повторений т.к. имеем 3 различные позиции, 3 различных людей и один человек не может встать на несколько позиций одновременно.

Рисунок 1.2.2.5

Обобщим полученный результат. Если есть n предметов, то число способов перенумеровать их равно n (n— 1) (n —2) ... 3 2 1. Таким образом для нахождения числа перестановок без повторений имеем

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

Пусть n-количество всех элементов, , ,…, – количество одинаковых элементов, где n=+

Число различных перестановок на элементах такой выборки равно

Так как некоторые элементы в выборке повторяются и при их перестановке новой перестановки не получим, то понятно, что число перестановок с повторениями меньше числа перестановок без повторения в (n1)!(n2)!...(nk)! раз.

Пример 3.

Сколькими способами можно переставить буквы слова «ананас»?

Решение: всего букв 6. Из них одинаковы «а»=3, «н»=2, «с»=1. Следовательно, число различных перестановок равно =60

Пример 4. У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней она дает сыну по 1 фрукту. Сколькими способами это может быть сделано.

Решение. Р(2,3)=

Сочетания.

В размещениях из n элементов по k комбинации отличаются либо набором элементов, либо порядком следования элементов.

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

Сочетаниями из n элементов по k называют любая не упорядоченная выборка k элементов объектов из n возможных объектов. Число сочетаний обозначают .

Пример 5. В первые три вагона поезда садятся 9 пассажиров по 3 человека в каждый вагон. Сколькими способами это можно сделать?

Решение. В первый вагон садится из 9 человек 3 человека, значит  С , в следующий вагон уже из 6 человек выбирается 3человека С тогда способов:

Рассмотрим размещения из n элементов по k и объединим в отдельные группы такие комбинации, которые содержат k одинаковых элементов и отличаются друг от друга только порядком этих элементов.

Каждая такая группа содержит выборок.

Поэтому справедлива формула

Сочетания  с повторениями.

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

 

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

Решение. Искомое число равно т.е.

 

Пример 7.  Сколькими способами можно разложить k одинаковых шаров по m различным ящикам?

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

Задачи для игры «Что? Где? Когда?»

1. В автосервис одновременно приехали 3 машины для ремонта. Сколько существует способов выстроить их в очередь на обслуживание?
2. Сколько есть способов раздать спортивные номера с 1 по 5 пяти хоккеистам?
3. Сколько перестановок можно получить из букв слова КОЛОКОЛА?
4. Сколькими способами можно разложить 28 различных предметов по четырем различным ящикам, так, чтобы в каждом ящике оказалось по 7 предметов?
5. Учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предмета?
6. Сколько трехзначных чисел (без повторения чисел в записи числа) можно составить из цифр 0, 1, 2, 3, 4, 5, 6?
7. Сколько различных 4-буквенных слов можно составить из символов 0, 0, a, b?
8. Сколько различных перестановок можно составить из букв слова АБАКАН?
9. Из вазы с фруктами, в которой лежат 9 яблок и 6 груш, надо выбрать 3 яблока и 2 груши. Сколькими способами можно сделать такой выбор?
10. Сколькими способами можно составить команду из 4 человек для соревнований по бегу, если имеются 7 бегунов?
11. В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить в нем 12 открыток?
12. Сколькими способами можно распределить три одинаковых карандаша между двумя детьми?

 

Методические рекомендации  к проведению занятия №3.