Комбинаторика примеры. Комбинаторные задачи (5 класс). Число сочетаний из n элементов по m
Реферат на тему:
Выполнил ученик 10 класса «В»
средней школы №53
Глухов Михаил Александрович
г. Набережные Челны
2002 г.
Содержание
| Из истории комбинаторики_________________________________________ | 3 |
| Правило суммы___________________________________________________ | 4 |
| - | |
| Правило произведения_____________________________________________ | 4 |
| Примеры задач____________________________________________________ | - |
| Пересекающиеся множества________________________________________ | 5 |
| Примеры задач____________________________________________________ | - |
| Круги Эйлера_____________________________________________________ | - |
| Размещения без повторений________________________________________ | 6 |
| Примеры задач____________________________________________________ | - |
| Перестановки без повторений_______________________________________ | 7 |
| Примеры задач____________________________________________________ | - |
| Сочетания без повторений__________________________________________ | 8 |
| Примеры задач____________________________________________________ | - |
| Размещения и сочетания без повторений______________________________ | 9 |
| Примеры задач____________________________________________________ | - |
| Перестановки с повторениями_______________________________________ | 9 |
| Примеры задач____________________________________________________ | - |
| Задачи для самостоятельного решения________________________________ | 10 |
| Список используемой литературы___________________________________ | 11 |
Из истории комбинаторики
Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге "Теория и практика арифметики" (1656 г.) французский автор А. Также посвящает сочетаниям и перестановкам целую главу.
Б. Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин "комбинаторика" стал употребляться после опубликования Лейбницем в 1665 г. работы "Рассуждение о комбинаторном искусстве", в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство предугадывания) в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX в.
Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило суммы и правило произведения.
Правило суммы
Если конечные множества не пересекаются, то число элементов X U Y {или} равно сумме числа элементов множества X и числа элементов множества Y.
То есть, если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки, можно X+Y способами.
Примеры задач
Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?
Решение: X=17, Y=13
По правилу суммы X U Y=17+13=30 тем.
Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет из спортлото или автомотолотереи?
Решение: Так как денежно-вещевая лотерея в выборе не участвует, то всего 6+10=16 вариантов.
Правило произведения
Если элемент X можно выбрать k способами, а элемент Y-m способами то пару (X,Y) можно выбрать k*m способами.
То есть, если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.
Примеры задач
Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?
Решение: Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.
Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?
Решение: В таких числах последняя цифра будет такая же, как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Это можно представить в виде XYZYX , где Y и Z -любые цифры, а X - не ноль. Значит по правилу произведения количество цифр одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900 вариантов.
Пересекающиеся множества
Но бывает, что множества X и Y пересекаются, тогда пользуются формулой
, где X и Y - множества, а - область пересечения. Примеры задач20 человекзнаютанглийскийи 10 - немецкий, изних 5 знаютианглийский, инемецкий. СколькоЧеловеквсего?
Ответ: 10+20-5=25 человек.
Также часто для наглядного решения задачи применяются круги Эйлера. Например:
Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским - 42. Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько туристов не владеют ни одним языком?Решение: Выразим условие этой задачи графически. Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий.
Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким. Следовательно, только английским и французским владеют 10-3=7 человек.Аналогично получаем, что только английским и немецким владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста. Вносим эти данные в соответствующие части.
Определим теперь, сколько человек владеют только одним из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским - 30 человек.По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков.
Размещения без повторений.
Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?
Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.
Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов.
Количество всех размещений из n элементов по m обозначают
n! - n-факториал (factorial анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа nЗадача
Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец?
Решение : два юноши не могут одновременно пригласить одну и ту же девушку. И варианты, при которых одни и те же девушки танцуют с разными юношами считаются, разными, поэтому:
Возможно 360 вариантов.
Перестановки без повторений
В случае n=m (см. размещения без повторений) из n элементов по m называется перестановкой множества x.
Количество всех перестановок из n элементов обозначают P n.
Действительно при n=m:
Примеры задач
Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?
1) Найдем количество всех перестановок из этих цифр: P 6 =6!=720
2) 0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P 5 =5!=120.
P 6 -P 5 =720-120=600
Проказница Мартышка
Да косолапый Мишка
Затеяли играть квартет
Стой, братцы стой! –
Кричит Мартышка, - погодите!
Как музыке идти?
Ведь вы не так сидите…
И так, и этак пересаживались – опять музыка на лад не идет.
Урок по математике в 5 классе
«
Знакомьтесь, комбинаторика»
Тема урока:
Цель урока
:
сформулировать первоначальные навыки комбинаторных задач с помощью перебора возможных вариантов.
Задачи урока:
Образовательные:
Развитие умения решать комбинаторные задачи методом полного перебора вариантов;
Выработка умения применять математическую теорию в конкретных ситуациях;
Знакомство учащихся с элементами гуманитарного знания, связанного с математикой.
Развитие умения самостоятельно выбирать способ решения и умения обосновать выбор;
Развитие умения решать задачи путём только логических рассуждений;
Развитие умения делать выбор рационального способа кодирования;
Развитие коммуникативных и творческих способностей учащихся.
- Воспитывать чувство ответственности за качество и результат выполняемой работы;
Прививать сознательное отношение к труду;
- Формировать ответственность за конечный результат
.
- интерактивная доска;
раздаточный материал (цветные полоски: белая, синяя, красная);
карточки с задачами.
- Организационный момент.
Изучение нового материала.
Практическая часть.
Рефлексия
Выставление отметок
Задание домашней работы
- Организационный момент.
- Актуализация темы и мотивация.
- 50 рублей, 100 рублей, 50 рублей, 100 рублей;
50 рублей, 50 рублей, 100 рублей, 100 рублей (слайд №2 и №3).
- Изучение нового материала
.
Комбинаторика – это раздел математики, посвященный решению задач выбора и расположения заданных элементов по заданным правилам
Обычный вопрос в комбинаторных задачах – это « Сколькими способами …?» или
« Сколько вариантов …?»
Учитель : Давайте еще раз вернемся к задаче о флагах, решим ее используя перебор возможных вариантов: (слайд №7) КБС КСБ БСК БКС СБК СКБ Ответ: 6 вариантов. Итак, при решении этой задачи мы искали способ перебора возможных вариантов. Во многих случаях оказывается полезным прием построения картинки – схемы перебора вариантов. Это, во – первых, наглядно, во- вторых, позволяет нам все учесть, ничего не пропустить.Решение Флаг
Варианты БСК, БКС, СБК, СКБ, КБС, КСБ.
Ответ: 6 вариантов.
Вопрос, ответ на который должны знать все, какой из представленных вариантов флагов – государственный флаг РФ.(Слайд№7)Оказывается, Не только флаг России имеет эти три цвета. Есть государства, флаги которых, имеют такие же цвета.
КБС – Люксембург,
Нидерланды.
Франция СКБ
Учитель: Найдем правило решения таких задач путем логического рассуждения.
Разберем на примере цветных полосок. Возьмем белую полоску – её можно переставить 3 раза, возьмем синюю полоску – её можно переставить только 2 раза, т.к. одно из мест уже занято белой, возьмем красную полоску – её можно положить только 1 раз.
ИТОГО: 3 х 2 х 1=6
Основное правило произведения :
Правило умножения: если первый элемент в комбинации можно выбрать а способами, после чего второй элемент – b способами, то общее число комбинаций будет равно а х b . (слайд №8)
Физкультминутка для глаз. (слайд №9)
Упражнение « Фигуры».
Нарисовать глазами квадрат, круг, треугольник, овал, ромб по часовой стрелке, а затем- против.
Практическая часть
Учитель: А теперь перейдем к математическим задачам. (раздаем карточки с задачами)
У одного довольно знаменитого мушкетера в гардеробе имеются 3 элегантных шляпы,4 чудных плаща и 2 пары отличных сапог. Сколько вариантов костюма ему можно составить? (Выбираем по одному элементу из трех множеств, то есть, составляем «тройку», значит, по правилу умножения получаем 3 4 2 = 24 варианта костюма.)
В футбольной команде 11 человек. Необходимо выбрать капитана и его заместителя. Сколькими способами можно это сделать? (Всего 11 человек, значит, капитана можно выбрать 11 способами, осталось 10 футболистов, из которых можно выбрать заместителя капитана. Итак, пару капитана и его заместителя можно выбрать 11 10 = 110 способами.)
Сколько различных двузначных чисел можно составить, используя цифры 1, 4, 7, если допустить повторение цифр? (Должно получиться двузначное число – всего две позиции. На первую позицию можно поставить любую из предложенных цифр – 3 варианта выбора, на вторую позицию, с учетом возможности повтора цифры, тоже 3 варианта выбора. Значит, пару цифр мы составляем 3 3 = 9 способами, т.е. получится 9 чисел.
Сколько различных трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что ни одна цифра не повторяется? (Трехзначное число: первая позиция – 5 вариантов цифр, вторая позиция с учетом исключения повторов цифр - 4 варианта, третья позиция – 3 варианта. Получаем 5 4 3 = 60 чисел.)
Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3, если цифры: а) могут повторяться; б) не могут повторяться? (а) Двузначное число, как и любое многозначное, не может начинаться с 0, поэтому на первую позицию можно поставить лишь 3 из имеющихся 4-х цифр, 3 варианта выбора, на вторую позицию, с учетом повтора, можно поставить любую из цифр – 4 варианта выбора. Поэтому получается 3 4 = 12 чисел; б) Первая позиция – 3 варианта, вторая позиция – 3 варианта, т.к. повтор исключается. Получаем 3 3 = 9 чисел.)
Шифр для сейфа состоит из пяти различных цифр. Сколько различных вариантов составления шифра? (5 4 3 2 1 = 120 вариантов.) Сколькими способами можно разместить 6 человек за столом, на котором поставлено 6 приборов? (6 5 4 3 2 1 = 720 способов.)
6 приборов? (6 · 5 · 4 · 3 · 2 · 1 = 720 способов.)
(8 · 7 · 6 · 5 · 4 = 6720 вариантов.)
(Используются цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – всего 10 цифр, исключая по условию 0 и 9 в начале номера, с учетом возможности повтора, получаем 8 · 10 · 10 · 10 · 10 · 10 · 10 = 8 000 000 номеров.)
- Рефлексия
Учитель: Ребята вот и подходит к концу наш урок. Как вы считаете, мы сегодня достигли нашей цели, почему? Что было трудным на уроке, как с эти можно бороться? Подумайте и поставьте себе за свой труд и работу отметку, поставьте сами, эту отметку никто из ребят не увидит, попробуйте быть честным с самим собой. Полностью ли вы участвовали в работе на уроке? Что нужно сделать, чтобы результат был лучше?
Кроме того, ученикам предлагается ответить на 3 блиц - вопроса:
На сегодняшнем уроке мне было … (легко, обычно, трудно)
Новый материал я … (усвоил и могу применить, усвоил и затрудняюсь применить, не усвоил)
Моя самооценка за урок …
Ответы на приведенные вопросы можно не подписывать, т.к. их основная функция помочь учителю проанализировать урок и его результаты
Подведение итогов . Выставление отметок
Учитель: Я очень рада, что многие из вас сегодня хорошо поработали, узнали много нового, но я очень хотела бы, чтобы все вы дома хорошо поработали и не получили на следующем уроке двоек.
7. Задание домашней работы :
1)Составить задачу о своем классе
2) Несколько стран решили использовать для своего государственного флага символику в виде 3 горизонтальных полос разной ширины, разных цветов – белый, синий, красный. Сколько стран могут использовать такую символику при условии,что у каждой страны свой флаг?
3) а) Сколько двузначных чисел можно составить из цифр 1, 3, 5, 7, 9?
б) Сколько двузначных чисел можно составить из цифр 1, 3, 5, 7, 9 при условии, что цифры не должны повторяться
Учитель : Итак, я была рада встрече с вами, интересуйтесь математикой, это, несомненно, отразится в положительную сторону в ваших размышлениях и действиях. Урок окончен. Всем спасибо. До свидания.
Литература:
Е.А.Бунимович, В.А. Булычев. Вероятность и статистика в курсе математики общеобразовательной школы: лекции 1- 4, 5 – 8. – М.: Педагогический университет “Первое сентября”, 2006.
Виленкин Н.Я. Математика. 5 класс: учебник для общеобразоват. учреждений/ Н.Я.Виленкин и др. – М. : Мнемозина, 2009.
Смыкалова Е.В. Дополнительные главы по математике для учащихся 5 класса. СПб: СМИО. Пресс, 2006.
5 класс. «Математика-5», И.И. Зубарева, А.Г. Мордкович, 2004 год.
Задачи (карточки)
Сколько вариантов семизначных телефонных номеров можно составить, если исключить из них номера, начинающиеся с 0 и 9?
У одного довольно знаменитого мушкетера в гардеробе имеются 3 элегантных шляпы,4 чудных плаща и 2 пары отличных сапог. Сколько вариантов костюма ему можно составить?
В футбольной команде 11 человек. Необходимо выбрать капитана и его заместителя. Сколькими способами можно это сделать?
Сколько различных двузначных чисел можно составить, используя цифры 1, 4, 7, если допустить повторение цифр
Сколько различных трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что ни одна цифра не повторяется?
Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3, если цифры: а) могут повторяться; б) не могут повторяться?
Шифр для сейфа состоит из пяти различных цифр. Сколько различных вариантов составления шифра?
Сколькими способами можно разместить 6 человек за столом, на котором поставлено 6 приборов?
В пятом классе изучаются 8 предметов. Сколько различных вариантов расписания можно составить на понедельник, если в этот день должно быть 5 уроков и все уроки – разные?Ответы
6 5 4 3 2 1 = 720 способов
8 7 6 5 4 = 6720 вариантов
Используются цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – всего 10 цифр, исключая по условию 0 и 9 в начале номера, с учетом возможности повтора, получаем 8 10 10 10 10 10 10 = 8 000 000 номеров.
Выбираем по одному элементу из трех множеств, то есть, составляем «тройку», значит, по правилу умножения получаем 3 4 2 = 24 варианта костюма.
Всего 11 человек, значит, капитана можно выбрать 11-ю способами, осталось 10 футболистов, из которых можно выбрать заместителя капитана. Итак, пару, капитана и его заместителя, можно выбрать 11 10 = 110 способами.
Должно получиться двузначное число – всего две позиции. На первую позицию можно поставить любую из предложенных цифр – 3 варианта выбора, на вторую позицию, с учетом возможности повтора цифры, тоже 3 варианта выбора. Значит, пару цифр мы составляем 3 3 = 9 способами, т.е. получится 9 чисел.
Трехзначное число: первая позиция – 5 вариантов цифр, вторая позиция, с учетом исключения повторов цифр, - 4 варианта, третья позиция – 3 варианта. Получаем 5 4 3 = 60 чисел.
(а) Двузначное число, как и любое многозначное, не может начинаться с 0, поэтому на первую позицию можно поставить лишь 3 из имеющихся 4-х цифр, 3 варианта выбора, на вторую позицию, с учетом повтора, можно поставить любую из цифр – 4 варианта выбора. Поэтому получается 3 4 = 12 чисел; б) Первая позиция – 3 варианта, вторая позиция – 3 варианта, т.к. повтор исключается. Получаем 3 3 = 9 чисел.
5 4 3 2 1 = 120 вариантов.В этом параграфе мы рассмотрим еще несколько комбинаторных задач, при решении которых будем пользоваться установленными выше формулами и правилами.
Пример 1. В некотором государстве каждые два человека отличаются набором зубов. Каково максимально возможное число жителей этого государства, если наибольшее число зубов у человека равно 32?
Решение. Эту задачу можно решить двумя способами. Первый способ заключается в том, что мы сначала ищем, сколько людей может иметь зубов, а потом просуммируем полученные результаты от до . Ясно, что мест из 32 можно выбрать способами. Поэтому ровно k зубов имеют не более чем жителей. А тогда общее число жителей не превосходит
Полученный этим способом ответ оказался очень громоздким. Выгоднее избрать другой путь, которым мы уже пользовались при решении примера 5 в § 2, - применить метод индукции.
Если речь идет об одном зубе, то возможны только два человека - один с зубом и второй без него. При двух зубах число возможных наборов зубов становится равным четырем: нет ни одного зуба, есть первый, есть второй и есть оба.
Увеличив число зубов до трех, мы удвоим число возможностей и получим восемь различных наборов. Действительно, каждый из рассмотренных наборов двух зубов может встретиться дважды - когда нет третьего зуба и когда он есть.
Обозначим число возможных наборов зубов через . Предыдущими рассуждениями мы доказали, что Допустим, что для некоторого справедливо равенство и докажем, что аналогичное равенство справедливо и для случая зубов. Среди всех различных наборов, входящих в имеется ровно наборов, в которых отсутствует (к зуб, и столько же наборов, в которых зуб имеется. Поэтому
Таким образом, при возможных зубах число всех людей, отличающихся набором зубов, равно . В нашем случае поэтому мы получаем Как известно, . Поэтому , так что возможное население этого государства больше нынешнего населения всего земного шара.
Заметим, что полученный нами результат на самом деле дает больше, чем только оценку возможного населения забавного государства. Сравнивая полученное значение с написанным выше выражением как суммы сочетаний, мы приходим к формуле:
Более того, из приведенного выше доказательства по индукции вытекает, что аналогичное равенство справедливо при любом то есть что имеет место формула
Пример 2. Дана прямоугольная сетка квадратов размером . Каково число различных дорог на этой сетке, ведущих из левого верхнего угла в правый нижний (рис. 46)? (Все звенья дороги предполагаются идущими или вправо, или вниз - без возвращений;
сходная ситуация возникает, скажем, при выборе одного из кратчайших маршрутов между двумя городскими перекрестками.)
Решение. Всякая дорога представляет собой ломаную, содержащую горизонтальных и вертикальных звеньев, то есть состоящую из звеньев. Различные дороги отличаются одна от другой лишь порядком чередования горизонтальных и вертикальных звеньев. Поэтому число возможных дорог равно числу способов, которыми можно выбрать вертикальных отрезксв из общего числа отрезков, а следовательно, есть
Можно было бы рассматривать число способов выбора не вертикальных, а горизонтальных отрезков и тогда мы получили бы ответ Но формула (9) из § 3 показывает, что
Полученный результат можно использовать для вывода еще одной интересной формулы. Пусть наша сетка является квадратной, то есть имеет размеры Тогда из приведенного выше решения следует, что число различных дорог, соединяющих левый верхний угол с правым нижним, равно .
Вместе с тем число этих дорог можно подсчитать иначе. Рассмотрим диагональ, идущую из нижнего левого угла в верхний правый, и обозначим вершины, лежащие на этой диагонали, через . Так как каждая дорога обязательно проходит через одну - и притом единственную точку этой диагонали, то общее число дорог есть сумма числа дорог, идущих через точку через точку через точку через точку .
Найдем число возможных дорог, идущих через точку Если нумерация точек произведена снизу вверх, как
это показано на рис. 47, то точка отстоит от нижней горизонтали на расстоянии считая за единицу измерения длину стороны квадрата сетки. От правой вертикали ее отделяют тогда горизонтальных отрезка.
Дорог, соединяющих верхний левый угол с точкой будет тогда а дорог, соединяющих точку с нижним правым углом, будет (это видно из рассмотрения равных прямоугольников, противоположными вершинами которых служат верхний левый угол исходного квадрата и точка и соответственно точка и нижний правый угол квадрата). Поэтому общее число дорог, соединяющих верхний левый угол с нижним правым и проходящих через равно Но тогда общее число всех дорог равно сумме
Сравнивая полученную сумму с найденным выше выражением для числа дорог, мы придем к формуле:
Пример 3. Шесть пассажиров садятся на остановке в трамвайный поезд, состоящий из трех трамвайных вагонов. Каким числом различных способов могут они распределиться в вагонах?
Решение. Прежде всего необходимо указать, что задача сформулирована недостаточно точно и допускает два различных толкования. Нас может интересовать или только число пассажиров в каждом вагоне или же кто именно в каком вагоне находится. Рассмотрим обе возможные формулировки.
Сначала рассмотрим случай, когда учитывается, кто в каком вагоне находится, то есть когда случаи «пассажир А в первом вагоне, а пассажир В - во втором» и «пассажир В в первом вагоне, а пассажир А - во втором» считаются различными.
Здесь мы имеем размещения с повторениями из трех элементов по шесть элементов: для каждого из шести пассажиров имеются три возможности. Пользуясь формулой (1) из § 4, получаем, что число различных способов, которыми шесть пассажиров могут распределиться в трех вагонах, равно:
Иной результат получится в том случае, если нас интересует лишь число пассажиров в каждом вагоне, так что случай «один пассажир в первом вагоне и один во втором» является единственным, независимо от того, кто из пассажиров где находится. Здесь нужно
Но подсчитывать уже не размещения, а Сочетания с повторениями. По формуле (4) из §4 находим, что число различных способов распределения пассажиров в этом случае равно
Пример 4. Сколькими способами можно распределить 28 костей домино между 4 игроками так, чтобы каждый получил 7 костей?
Решение. Первый игрок может выбрать 7 костей способами. После этого второй игрок должен выбрать 7 костей из оставшихся 21 кости. Это можно сделать способами. Третий игрок может выбрать кости Си способами, а четвертый - способом. Всего получаем
способов раздела костей.
Эту задачу можно решить иначе. Упорядочим все кости и отдадим первые 7 костей первому игроку, вторые 7 костей - второму игроку и т. д. Так как 28 костей можно упорядочить 28! способами, то получаем 28! способов раздела. Но некоторые из этих способов приводят к одинаковым результатам - игрокам неважно, в каком порядке приходят к ним кости, а важно лишь, какие именно кости они получат. Поэтому результат не изменится, если мы как угодно переставим друг с другом первые 7 костей, потом вторые 7 костей и т. д. Первые 7 костей можно переставить 7! способами, вторые 7 костей - тоже 7! способами и т. д. Всего получим перестановок, дающих то же распределение костей, что и данная. Поэтому число способов раздела костей равно
Пример 5. Сколькими способами можно разделить 40 яблок между 4 мальчиками (все яблоки считаются одинаковыми)?
Для построения соответствующих математических моделей комбинаторных задач будем использовать математический аппарат теории множеств . Может случиться, что в данном множестве порядок следования элементов не важен, а важен только состав множества. Но есть задачи, в которых прядок элементов является существенным.
Определение
1:
Порядок
во множестве
из
элементов – это нумерация его элементов
натуральными числами, т.е. отображение
множества
на множество
.
Определение 2: Множество с заданным на нем порядком называется упорядоченным множеством.
Очевидно, что множество, содержащее более одного элемента, можно упорядочить не единственным способом.
Например,
из двух букв
и
можно построить упорядоченное множество
двумя различными способами:
и
.
Три
буквы
,
и
можно расположить в виде последовательности
шестью способами:
,
,
,
,
,
.
Для четырех букв путем перебора получим уже 24 различных упорядоченных последовательностей.
Упорядоченные последовательности элементов некоторого множества можно рассматривать как распределения или расстановки этих элементов в последовательности.
Определение
3:
Пусть
дано конечное множество
из
элементов. Всякий набор из
элементов данного множества (при этом
элементы в наборе могут и повторяться)
будем называть
-расстановками
.
Через понятие расстановки вводятся основные определения комбинаторики: сочетания, размещения и перестановки . При этом каждое из этих понятий может быть с повторениями и без повторений. В данном параграфе будут рассмотрены комбинаторные формулы без повторений.
Перестановки без повторений.
Определение
4:
Пусть
- конечное множество из
элементов.Перестановками
из
различных элементов множества
называются все расположения
элементов в определенном порядке.
Обозначается:
(от французского словаpermutation
- перестановка).
Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком.
Определение 5: Различные упорядоченные множества, которые отличаются лишь порядком элементов, называются перестановками этого множества.
Последнее определение сформулировано с позиции теории множеств.
Определение
6:
Произведение
последовательных натуральных чисел в
математике обозначают
и называютфакториалом
.
Выбор
для обозначения
восклицательного знака, возможно, связан
с тем, что даже для сравнительно небольших
значений
число
очень велико. Например,
,
,
,
,
,,и т.д.
Теорема
1:
Число
перестановок из
различных элементов вычисляется по
формуле:
Доказательство.
Рассмотрим произвольное множество из
элементов. Построим всевозможные
расстановки из этих
элементов.
На первое
место
расстановки можно поставить любой из
элементов (
способов выбора первого элемента). После
того, как первый элемент выбран и
независимо как он выбран, второй элемент
можно выбрать
способом. Для выбора третьего элемента
остается
способа и т.д. Последний элемент выбирается
соответственно одним способом. Тогда,
в силу комбинаторного принципа умножения,
количество таких расстановок будет
равно:
Теорема доказана.
Пример 1: Сколькими способами трое друзей могут занять в кинотеатре места с номерами 1, 2 и 3.
Решение.
Количество искомых способов будет равно
числу перестановок без повторений из
трех элементов:
способов. При необходимости эти способы
можно перебрать.
Перестановки
букв некоторого слова называют
анаграммами
.
Открытые еще в ІІІ
веке до
нашей эры греческим грамматиком
Ликофроном анаграммы до сих пор привлекают
внимание языковедов, поэтов и любителей
словесности. Мастера словесных игр
помимо эрудиции и большого запаса слов
знают много секретов, связанных с
комбинаторными навыками, один из которых
– анаграммы. Часто требуется среди всех
перестановок выбрать те, которые обладают
определенным свойством. Например, среди
анаграмм слова «крот»
,
которых всего
,
только одна, не считая самого слова«крот»
,
имеет смысл в русском языке – «корт».
Кроме линейных перестановок, можно рассматривать перестановки круговые (или циклические). В этом случае перестановки, переходящие друг в друга при вращении, считаются одинаковыми и не должны засчитываться.
Теорема
2:
Число
круговых перестановок из
различных элементов равно
Пример 2: Сколькими способами 7 детей могут стать в хоровод?
Решение.
Число линейных перестановок 7 детей
будет равно
.
Если хоровод уже сформирован, тогда для
него существует 7 круговых перестановок,
переходящих друг в друга при повороте.
Эти перестановки не должны быть засчитаны,
поэтому круговых перестановок из 7
элементов будет
.
Размещения без повторений.
Определение
7:
Пусть
имеется
различных предметов. Расстановки из
элементов по
элементов (
)
называютсяразмещениями
без повторений
.
Обозначают:
.
Здесь имеется в виду, что элементы в
расстановках не повторяются.
В данном определении существенной является следующая позиция: две расстановки различны, если они отличаются хотя бы одним элементом или порядком элементов.
Приведем еще одно определение размещений, эквивалентное исходному, более простое для понимания.
Определение 8: Конечные упорядоченные множества называются размещениями.
Теорема
3:
Количество
всех размещений из
элементов по
элементов без повторений вычисляется
по формуле:
Доказательство.
Пусть имеется произвольное множество
,
состоящее из
элементов. Необходимо выбрать из этого
множества
различных элементов. Причем, важен
порядок выбора.
Выбор
элементов осуществляется поэтапно.
Первый элемент расстановки можно выбрать
различными способами. Тогда из оставшихся
элементов множества
второй элемент расстановки выбирается
способом. Для выбора третьего элемента
возможно
способа и т.д. Тогда для выбора
-
го элемента имеем
способ. Следовательно, согласно правилу
умножения, количество таких расстановок
будет равно:
По определению, такие расстановки являются размещениями. Что и требовалось доказать.
Пример 3: Собрание из 25 человек выбирает президиум из 3 человек: 1) председатель, 2) заместитель, 3) секретарь. Сколько возможно вариантов выбора президиума?
Решение. Выбирая трех человек из 25, замечаем, что важен порядок выбора, поэтому количество президиумов будет равно:
Замечание: Число размещений без повторений можно также находить по формуле:
. (3)
Если
в знаменателе дроби из формулы (3)
,
то принято считать
.
Замечание: Формула (3) отличается компактностью, но при решении задач удобнее использовать формулу (2). Дробь, стоящая в правой части формулы (3), может быть сокращена до целого числа. Это число равно числу из правой части формулы (2).
Пример 4: Сколько можно составить двухбуквенных слов (буквы не повторяются) из 33 букв русского алфавита?
Решение. В данном случае мы имеем дело не со словами в лингвистическом понимании, а с буквенными комбинациями произвольного состава.
Тогда количество различных комбинаций из 2 букв, выбранных из 33 букв алфавита, будет равно:
.
В данном случае важен порядок букв. Если поменять 2 буквы в слове, то получим новое слово.
Замечание:
Перестановка без повторений – это
частный случай размещений без повторений
при
.
Можно сказать, что перестановка из
элементов – это размещение из
элементов по
элементов:
В некоторых задачах по комбинаторике не имеет значения порядок расположения объектов в той или иной совокупности. Важно лишь то, какие именно элементы ее составляют. В таких ситуациях мы имеем дело с сочетаниями .
Сочетания без повторений.
Определение
9:
Сочетания
без
повторений из
элементов некоторого множества по
элементов (
)
– это расстановки, отличающиеся друг
от другасоставом
,
но не порядком
элементов. Обозначают:
(от французского словаcombinaison
– сочетание).
В данном случае в расстановках важен состав, а не порядок элементов в подмножестве. Если две расстановки отличаются только порядком следования элементов, то с точки зрения сочетаний они не различимы. Элементы в этих расстановках не повторяются.
С точки зрения теории множеств определение сочетаний можно сформулировать иначе.
Определение 10: Конечные неупорядоченные множества называются сочетаниями.
Таким образом, сочетания – это такая выборка элементов, при которой их порядок совершенно не важен.
Сочетаний
из
элементов по
элементов должно быть меньше, чем
соответствующих размещений. Это следует
из того, что не надо засчитывать
расстановки одинакового состава.
Теорема
4:
Число
сочетаний
находится по следующей формуле:
. (4)
Доказательство.
Если из произвольного
-элементного
множества выбраны
элементов, то их можно пронумеровать
номерами
числом способов, равным
.
Оставшиеся
элементов можно занумеровать номерами
,
,
…,
всего
способами. Кроме того, сам отбор
элементов из
элементов можно осуществить
способами. Таким образом, мы получили
вариантов нумерации полного множества
из
элементов, которых всего
.
Поэтому имеем
,
откуда получаем:
.
Теорема доказана.
Замечание: Дробь, стоящая в правой части (4), может быть сокращена до целого числа.
Из формулы числа сочетаний следует:
,
,
.
Формула
(4) может быть преобразована к виду:
.
Отсюда видно, что число размещений
в
раз больше числа соответствующих
сочетаний
.
Другими словами, чтобы посчитать все
сочетания
,
нужно исключить из всех размещений
подмножества, отличающиеся порядком
(их будет
штук), т.е.
делят на
.
Пример 5: Сколькими способами можно выбрать 3 различные краски из имеющихся пяти.
Решение.
Порядок выбора красок не важен. Важно
только какие краски выбраны. Поэтому
количество вариантов равно:
.
Пример 6: Сколькими способами можно пошить трехцветные полосатые флаги, если имеется материал пяти различных цветов.
Решение.
Порядок выбора полос важен, поэтому
количество таких флагов равно:
.
Комбинаторикой называется раздел математики, изучающий вопрос о том, сколько комбинаций определенного типа можно составить из данных предметов (элементов).
Правило умножения (основная формула комбинаторики)
Общее число способов, которыми можно выбрать по одному элементу из каждой группы и расставить их в определенном порядке (то есть получить упорядоченную совокупность ), равно:
Пример 1
Монету подбросили 3 раза. Сколько различных результатов бросаний можно ожидать?
Решение
Первая монета имеет альтернативы – либо орел, либо решка. Для второй монеты также есть альтернативы и т.д., т.е. .
Искомое количество способов:
Правило сложения
Если любые две группы и не имеют общих элементов, то выбор одного элемента или из , или из , …или из можно осуществить способами.
Пример 2
На полке 30 книг, из них 20 математических, 6 технических и 4 экономических. Сколько существует способов выбора одной математической или одной экономической книги.
Решение
Математическая книга может быть выбрана способами, экономическая - способами.
По правилу суммы существует способа выбора математической или экономической книги.
Размещения и перестановки
Размещения – это упорядоченные совокупности элементов, отличающиеся друг от друга либо составом, либо порядком элементов.
Размещения без повторений , когда отобранный элемент перед отбором следующего не возвращается в генеральную совокупность. Такой выбор называется последовательным выбором без возвращения, а его результат – размещением без повторений из элементов по .
Число различных способов, которыми можно произвести последовательный выбор без возвращения элементов из генеральной совокупности объема , равно:
Пример 3
Расписание дня состоит из 5 различных уроков. Определите число вариантов расписания при выборе из 11 дисциплин.
Решение
Каждый вариант расписания представляет набор 5 дисциплин из 11, отличающихся от других вариантов как составом, так и порядком следования. поэтому:
Перестановки – это упорядоченные совокупности, отличающиеся друг от друга только порядком элементов. Число всех перестановок множества из элементов равно
Пример 4
Сколькими способами можно рассадить 4 человек за одним столом?
Решение
Каждый вариант рассадки отличается только порядком участников, то есть является перестановкой из 4 элементов:
Размещения с повторениями , когда отобранный элемент перед отбором следующего возвращается в генеральную совокупность. Такой выбор называется последовательным выбором с возвращением, а его результат - размещением с повторениями из элементов по .
Общее число различных способов, которыми можно произвести выбор с возвращением элементов из генеральной совокупности объема , равно
Пример 5
Лифт останавливается на 7 этажах. Сколькими способами могут выйти на этих этажах 6 пассажиров, находящихся в кабине лифта?
Решение
Каждый из способов распределения пассажиров по этажам представляет собой комбинацию 6 пассажиров по 7 этажам, отличающуюся от других комбинаций как составом, так и их порядком. Так как одном этаже может выйти как один, так и несколько пассажиров, то одни и те же пассажиры могут повторяться. Поэтому число таких комбинаций равно числу размещений с повторениями из 7 элементов по 6:
Сочетания
Сочетаниями из n элементов по k называются неупорядоченные совокупности, отличающиеся друг от друга хотя бы одним элементом.
Пусть из генеральной совокупности берется сразу несколько элементов (либо элементы берут последовательно, но порядок их появления не учитывается). В результате такого одновременного неупорядоченного выбора элементов из генеральной совокупности объема получаются комбинации, которые называются сочетаниями без повторений из элементов по .
Число сочетаний из элементов по равно:
Пример 6
В ящике 9 яблок. Сколькими способами можно выбрать 3 яблока из ящика?
Решение
Каждый вариант выбора состоит из 3 яблок и отличается от других только составом, то есть представляет собой сочетания без повторений из 9 элементов:
Количество способов, которыми можно выбрать 3 яблока из 9:
Пусть из генеральной совокупности объема выбирается элементов, один за другим, причем каждый отобранный элемент перед отбором следующего возвращается в генеральную совокупность. При этом ведется запись, какие элементы появились и сколько раз, однако порядок их появления не учитывается. Получившиеся совокупности называются сочетаниями с повторениями из элементов по .
Число сочетаний с повторениями из элементов по :
Пример 7
На почте продают открытки 3 видов. Сколькими способами можно купить 6 открыток?
Это задача на отыскание числа сочетаний с повторениями из 3 по 6:
Разбиение множества на группы
Пусть множество из различных элементов разбивается на групп так, то в первую группу попадают элементов, во вторую - элементов, в -ю группу - элементов, причем . Такую ситуацию называют разбиением множества на группы.
Число разбиений на групп, когда в первую попадают элементов, во вторую - элементов, в k-ю группу - элементов, равно:
Пример 8
Группу из 16 человек требуется разбить на три подгруппы, в первой из которых должно быть 5 человек, во второй – 7 человек, в третьей – 4 человека. Сколькими способами это можно сделать?