Элементы комбинаторики: перестановки, сочетания, размещения.
“Число, положение и комбинация – три
взаимно пересекающиеся, но различные
сферы мысли, к которым можно
отнести все математические идеи”.
Джозеф Сильвестр (1844 г.)
Цели занятия.
Образовательные:
- познакомить студентов с новым разделом математики: "Комбинаторика", с его историей, основными понятиями и задачами, использованием в практических целях и в жизни человека;
- способствовать созданию учебного проекта как показатель качественного изучения темы занятия.
Развивающие:
- развивать аналитические способности, логическое мышление,
- индивидуальные способности каждого студента, создавая комфортную психологическую обстановку для каждого студента при обучении и создании проекта.
Воспитывающая:
- формировать активность личности студента, умение работать в группе, отвечать за свои поступки.
Оборудование: компьютеры, проектор, экран, презентация, электронные и на бумажных носителях тесты, задачи “Судоку”, кубики Рубика, папки для ВСР (внеаудиторная самостоятельная работа), рабочие тетради, чистые ватманы, калькуляторы, цветная бумага, клей, ножницы, фломастеры.
Ход занятия
I. Организационный момент
Перекличка
Сообщение целей и задач занятия: В связи с тем, что по дисциплине “Математика” на 2 курсе специальности “Технология деревообработки” на тему “Основные понятия комбинаторика: перестановки, размещения, сочетания” отводится 2 часа, а рассмотреть нужно много материала, решать задачи, создать проект, вам было выдано задание на внеаудиторную самостоятельную работу следующее: в литературе по истории математики, в энциклопедиях, в учебниках и в интернете найти материал о разделе математики, имеющем звучное название “комбинаторика”. Слайды № 1–2. Презентация
В календарно-тематическом плане по дисциплине “Математика” на 2 курсе специальности “Технология деревообработки” на тему “Основные понятия комбинаторика: перестановки, размещения, сочетания” отводится 2 часа. Изучить теоретический материал, решить задачи разных видов за такой временной промежуток невозможно. Для достижения глубокого изучения материала было выдано задание на внеаудиторную самостоятельную работу: в литературе по истории математики, в энциклопедиях, в учебниках и в интернете найти материал о разделе математики, имеющем звучное название “комбинаторика”. Слайды № 1–2.
Вопросов для внеаудиторной самостоятельной работы выделено было три:
- Определения комбинаторики.
- Ученые – математики - первооткрыватели этого раздела.
- Применение комбинаторики в современной жизни.
Запись даты, темы урока.
II. Работа над темой занятия
Вступление:
Из глубокой древности до современного человечества дошли сведения о том, что уже тогда люди занимались выбором объектов и расположения их в том или ином порядке и увлекались составлением различных комбинаций. Так, например, в Древнем Китае увлекались составлением квадратов, в которых заданные числа располагали так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же (современная игра – задача “Судоку”). Такие задачи вы могли встречать в журналах и газетах. В частности, наша Мариинская газета “Вперед” довольно часто предлагает читателям такие задачи. В Древней Греции подобные задачи возникали в связи c такими играми, как шашки, шахматы, домино, карты и т.д.
Комбинаторика ставится самостоятельным разделом математики, по сути – самостоятельной наукой лишь во второй половине XVII века, - в период, когда возникла теория вероятностей.
Таким образом, - комбинаторика – это самостоятельный раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или условиям, можно составить из заданных объектов.
Комбинаторика – самостоятельная ветвь математической науки. Cлайд № 3
Термин “КОМБИНАТОРИКА” происходит от латинского слова “combina”, что в переводе на русский означает – “сочетать”, “соединять” - слайд № 4.
Как трактует это слово Большой Энциклопедический Словарь?
Комбинаторика – это раздел математики, в котором изучаются простейшие “соединения”: перестановки, размещения, сочетания. Этот раздел иначе называют “комбинаторный анализ”.
Сегодня мы будем рассматривать перестановки, размещения, сочетания, как соединения, как комбинаторные конфигурации.
Разделы комбинаторики: перечислительная, структурная, вероятностная, топологическая – слайд № 5.
Давайте вспомним известное вам из детства сказание о том, как богатырь или другой добрый молодец, доехав до развилки трех дорог, читает на камне: “Вперед поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься”. А дальше уже говорится, как он выходит из того положения, в которое попал в результате выбора. Но выбирать разные пути или варианты приходится и современному человеку. Эти пути и варианты складываются в самые разнообразные комбинации. И целый раздел математики, именуемый КОМБИНАТОРИКОЙ, занят поисками ответов на вопросы: сколько всего есть комбинаций в том или ином случае, как из всех этих комбинаций выбрать наилучшую – слайд № 6.
Итак, комбинаторика – раздел математики, в котором изучается, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
Перестановки-соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; число их
Количество всех перестановок из n элементов обозначают
Число n при этом называется порядком перестановки – слайд № 7–10.
Произведение всех натуральных чисел от n до единицы, обозначают символом n! (Читается “эн - факториал”). Используя знак факториала, можно, например, записать:
3! = 3 2 1 = 6,
4! = 4 3 2 1 = 24,
5! = 5 4 3 2 1 = 120.
Необходимо знать, что 0!=1
Термин “перестановки” употребил впервые Якоб Бернулли в книге “Искусство предположений”.
Примеры решения задач:
Задача №1. Сколькими способами 7 книг разных авторов можно расставить на полке в один ряд?
Перестановками называют комбинации, состоящие из одних и тех же п различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок обозначается Рп и оно равно п !, т.е. Рп = п !, где п ! = 1 * 2 * 3 * … п .
Решение: Р7 = 7!, где 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 =5040, значит существует 5040 способов осуществить расстановку книг.
Ответ: 5040 способов.
Задача № 2 (о квартете)
В знаменитой басне Крылова “Квартет” “Проказница мартышка, Осел, Козел да косолапый Мишка” исследовали влияние взаимного расположения музыкантов на качество исполнения.
Зададим вопрос: Сколько существует способов, чтобы рассадить четырех музыкантов?
Решение: на слайде
Размещения – соединения, содержащие по m предметов из числа n данных, различающихся либо порядком предметов, либо самими предметами; число их.
Cлайды № 11–13.
В комбинаторике размещением называется расположение “предметов” на некоторых “местах” при условии, что каждое место занято в точности одним предметом и все предметы различны.
В отличие от сочетаний размещения учитывают порядок следования предметов. Так, например, наборы < 2,1,3 > и < 3,2,1 > являются различными, хотя состоят из одних и тех же элементов {1,2,3} (то есть, совпадают как сочетания).
Термин “Размещение” употребил впервые Якоб Бернулли в книге “Искусство предположений”.
Примеры решения задач:
Задача № 1. Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны? Это пример задачи на размещение без повторений.
Размещаются здесь десять цифр по 6. Значит,
ответ на выше поставленную задачу будет: 
Ответ :151200 способов
Задача № 2. В группе ТД – 21 обучается 24 студентов. Сколькими способами можно составить график дежурства по техникуму, если группа дежурных состоит из трех студентов?
Решение: число способов равно числу размещений из 24 элементов по 3, т.е. равно А 24 3 . По формуле находим
Ответ: 12144 способа
Сочетания-соединения, содержащие по m предметов
из n, различающиеся друг от друга, по крайней мере,
одним предметом; число их 
.
Таким образом, количество вариантов при сочетании будет меньше количества размещений. Cлайды № 14–16.
В комбинаторике сочетанием из n по m называется набор m элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
Термин “сочетание” впервые встречается у Блеза Паскаля в 1665 году.
Примеры решения задач:
Задача №1. Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр?
Решение: Так как кнопки нажимаются одновременно, то выбор этих кнопок – сочетание. Отсюда возможно
Ответ: 120 вариантов.
Задача № 2. Сколько экзаменационных комиссий, состоящих из 3 членов, можно образовать из 10 преподавателей?
Решение: По формуле находим:
комиссий
Ответ: 120 комиссий.
Библиографическая справка – слайд № 17.
Общее у всех этих задач то, что их решением занимается отдельная область математики, называемая комбинаторикой. “Особая примета” комбинаторных задач – вопрос, который всегда можно сформулировать так, чтобы он начинался словами: “Сколькими способами…?”. Cлайд № 18.
3. Решение задач: тексты задач с решениями в приложении 1 – начало на слайде № 19.
4. Исторические сведения о комбинаторике на слайдах № 20–21 (частично даны сведения при изучении темы, остальные данные для проекта студенты возьмут из материалов для ВСР).
5. Связи комбинаторики на слайдах № 22–31 (частично даны сведения при изучении темы, остальные данные для проекта студенты возьмут из материалов для ВСР).
6. Выдвижение гипотезы. Гипотеза – это научное предположение, выдвигаемое для объяснения каких-нибудь явлений, вообще – предположение, требующее подтверждения.
Выдвигается гипотеза: Комбинаторика интересна и имеет широкий спектр практической направленности - слайд № 32.
7. Метод проектов: три группы студентов и группа преподавателей выполняют проект
КОМБИНАТОРИКА
Комбинаторика - раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.
Правила сложения и умножения в комбинаторике
Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить 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 букв. Следовательно, число перестановок с повторениями равно
ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ "КОМБИНАТОРИКА"
Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:
Введение. Множества и выборки.
В этой теме рассмотрим основные понятия комбинаторики: перестановки, сочетания и размещения. Выясним их суть и формулы, по которым можно найти их количество.
Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме "Понятие множества. Способы задания множеств" .
Очень краткий рассказ про множества : показать\скрыть
Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $\{1,5,9 \}$. Множество согласных букв в слове "тигрёнок" таково: $\{т, г, р, н, к\}$. Запись $5\in A$ означает, что элемент 5 принадлежит множеству $A=\{1,5,9 \}$. Количество элементов в конечном множестве называют мощностью этого множества и обозначают $|A|$. Например, для множества $A=\{1,5,9 \}$, содержащего 3 элемента, имеем: $|A|=3$.
Рассмотрим некое непустое конечное множество $U$, мощность которого равна $n$, $|U|=n$ (т.е. в множестве $U$ имеется $n$ элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем). Под выборкой объема $k$ из $n$ элементов (сокращённо $(n,k)$-выборкой) будем понимать набор элементов $(a_1, a_2,\ldots, a_k)$, где $a_i\in U$. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной.
Заметьте, что в определении выборки ничего не сказано про повторения элементов. В отличие от элементов множеств, элементы выборки могут повторяться.
Для примера рассмотрим множество $U=\{a,b,c,d,e\}$. Множество $U$ содержит 5 элементов, т.е. $|U|=5$. Выборка без повторений может быть такой: $(a,b,c)$. Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это $(5,3)$-выборка.
Выборка с повторениями может быть такой: $(a,a,a,a,a,c,c,d)$. Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это $(5,8)$-выборка.
Рассмотрим ещё две $(5,3)$-выборки: $(a,b,b)$ и $(b,a,b)$. Если мы полагаем наши выборки неупорядоченными, то выборка $(a,b,b)$ равна выборке $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Если мы полагаем наши выборки упорядоченными, то $(a,b,b)\neq(b,a,b)$.
Рассмотрим ещё один пример, немного менее абстрактный:) Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете - цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U=\{1,2,3,4,5,6\}$. Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты - это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.
Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=\{1,2,3,4 \}$ (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока - повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.
Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U=\{к,о,н,ф,е,т,а\}$. Допустим, из данных кубиков мы хотим составить "слова" из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д. Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков. Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.
Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество $U$ таково: $U=\{1,5,7,8\}$. Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная. Повторения допускаются, поэтому здесь мы имеем дело с упорядоченной (4,8)-выборкой с повторениями.
Размещения без повторений из $n$ элементов по $k$
Размещение без повторений из $n$ элементов по $k$ - упорядоченная $(n,k)$-выборка без повторений.
Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: $n≥ k$. Количество размещений без повторений из $n$ элементов по $k$ определяется следующей формулой:
\begin{equation}A_{n}^{k}=\frac{n!}{(n-k)!} \end{equation}
Что обозначает знак "!"? : показать\скрыть
Запись "n!" (читается "эн факториал") обозначает произведение всех чисел от 1 до n, т.е.
$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$
По определению полагается, что $0!=1!=1$. Для примера найдём 5!:
$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$
Пример №1
Алфавит состоит из множества символов $E=\{+,*,0,1,f\}$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.
Под трёхсимвольными словами будем понимать выражения вида "+*0" или "0f1". В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3. Вот примеры таких размещений:
$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$
Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:
$$ A_{5}^{3}=\frac{5!}{(5-3)!}=\frac{5!}{2!}=60. $$
Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться.
Ответ : 60.
Размещения с повторениями из $n$ элементов по $k$
Размещение с повторениями из $n$ элементов по $k$ - упорядоченная $(n,k)$-выборка с повторениями.
Количество размещений с повторениями из $n$ элементов по $k$ определяется следующей формулой:
\begin{equation}\bar{A}_{n}^{k}=n^k \end{equation}
Пример №2
Сколько пятизначных чисел можно составить из множества цифр $\{5,7,2\}$?
Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 - разные числа. Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):
$$ \bar{A}_{3}^{5}=3^5=243. $$
Следовательно, из заданных цифр можно составить 243 пятизначных числа.
Ответ : 243.
Перестановки без повторений из $n$ элементов
Перестановка без повторений из $n$ элементов - упорядоченная $(n,n)$-выборка без повторений.
По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из $n$ элементов определяется следующей формулой:
\begin{equation}P_{n}=n! \end{equation}
Эту формулу, кстати, легко получить, если учесть, что $P_n=A_{n}^{n}$. Тогда получим:
$$ P_n=A_{n}^{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$
Пример №3
В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения?
Пусть первому мороженому соответствует цифра 1, второму - цифра 2 и так далее. Мы получим множество $U=\{1,2,3,4,5\}$, которое будет представлять содержимое морозилки. Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:
$$ P_5=5!=120. $$
Следовательно, существует 120 порядков выбора очередности съедения.
Ответ : 120.
Перестановки с повторениями
Перестановка с повторениями – упорядоченная $(n,k)$-выборка с повторениями, в которой элемент $a_1$ повторяется $k_1$ раз, $a_2$ повторяется $k_2$ раза так далее, до последнего элемента $a_r$, который повторяется $k_r$ раз. При этом $k_1+k_2+\ldots+k_r=k$.
Общее количество перестановок с повторениями определяется формулой:
\begin{equation}P_{k}(k_1,k_2,\ldots,k_r)=\frac{k!}{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation}
Пример №4
Слова составляются на основе алфавита $U=\{a,b,d\}$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква "a" должна повторяться 2 раза; буква "b" - 1 раз, а буква "d" - 4 раза?
Вот примеры искомых слов: "aabdddd", "daddabd" и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ и т.д. Каждая такая выборка состоит из двух элементов "a", одного элемента "b" и четырёх элементов "d". Иными словами, $k_1=2$, $k_2=1$, $k_3=4$. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. $k=k_1+k_2+k_3=7$. Подставляя эти данные в формулу (4), будем иметь:
$$ P_7(2,1,4)=\frac{7!}{2!\cdot 1!\cdot 4!}=105. $$
Следовательно, общее количество искомых слов равно 105.
Ответ : 105.
Сочетания без повторений из $n$ элементов по $k$
Сочетание без повторений из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка без повторений.
Общее количество сочетаний без повторений из $n$ элементов по $k$ определяется формулой:
\begin{equation}C_{n}^{k}=\frac{n!}{(n-k)!\cdot k!} \end{equation}
Пример №5
В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?
Итак, в данной задаче исходное множество таково: $U=\{1,2,3,4,5,6,7,8,9,10\}$. Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны. Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки $(1,2,7,10)$ и $(10,2,1,7)$ или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится. Например, выборке $(1,2,7,10)$ и выборке $(10,2,1,7)$ будет соответствовать одно и то же число $1+2+7+10=10+2+1+7=20$. Вывод: из условия задачи следует, что мы имеем дело с неупорядоченными выборками. Т.е. нам нужно найти общее количество неупорядоченных (10,4)-выборок без повторений. Иными словами, нам нужно найти количество сочетаний из 10 элементов по 4. Используем для этого формулу (5):
$$ C_{10}^{4}=\frac{10!}{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$
Следовательно, общее количество искомых наборов равно 210.
Ответ : 210.
Сочетания с повторениями из $n$ элементов по $k$
Сочетание с повторениями из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка с повторениями.
Общее количество сочетаний с повторениями из $n$ элементов по $k$ определяется формулой:
\begin{equation}\bar{C}_{n}^{k}=\frac{(n+k-1)!}{(n-1)!\cdot k!} \end{equation}
Пример №6
Представьте себе, что мы находимся на конфетном заводе, - прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных "конфетных комбинаций" может оказаться в горсти?
Если принять, что первому сорту соответствует число 1, второму сорту - число 2 и так далее, то исходное множество в нашей задаче таково: $U=\{1,2,3,4\}$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями. Чтобы найти общее количество этих выборок используем формулу (6):
$$ \bar{C}_{4}^{20}=\frac{(4+20-1)!}{(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$
Следовательно, общее количество искомых комбинаций равно 1771.
Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиальновозможное количество различных вариантов развития событий.
Основная формула комбинаторики
Пусть имеется 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. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?
Реферат на тему:
Выполнил ученик 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
n!=1*2*3*...*n 0!=1
Значит, ответ на вышепоставленную задачу будет
Задача
Сколькими способами 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
Проказница Мартышка
Да косолапый Мишка
Затеяли играть квартет
Стой, братцы стой! –
Кричит Мартышка, - погодите!
Как музыке идти?
Ведь вы не так сидите…
И так, и этак пересаживались – опять музыка на лад не идет.