Он может пригласить в гости одного или несколько из них. Определите общее число возможных вариантов. №3 В 9 «а» классе учатся 25 учащихся, в 9 «б» - 20 учащихся, а в 9 «в» - 18 учащихся. Для работы на пришкольном участке надо выделить трёх учащихся из 9 «а», двух -из 9 «б» и одного – из 9 «в». Сколько существует способов выбора учащихся для работы на пришкольном участке? С №1 Пять мальчиков и четыре девочки хотят сесть на девятиместную скамейку так, чтобы каждая девочка сидела между двумя мальчиками. Сколькими способами они могут это сделать? №2 Из 12 солдат, в число которых входят Иванов и Петров, надо отправить в наряд трёх человек. Сколькими способами это можно сделать, если: а) Иванов и Петров должны пойти в наряд обязательно; б) Иванов и Петров должны остаться; в)Иванов должен пойти в наряд, а Петров –остаться? (Ответы) Устал - отдохни.
В №1 В шахматном кружке занимаются 16 человек. Сколькими способами тренер может выбрать из них для предстоящего турнира: а) команду из четырёх человек; б) команду из четырёх человек, указав при этом, кто из членов команды будет играть на первой, второй, третьей и четвёртой досках?
Презентация на тему:Элементы Комбинаторики!!!
Студента Группы ПР – 101(К) Савченко А.А Проверила Малыгина Г.С.
Комбинаторика! (Комбинаторный анализ) - раздел математики, изучающий дискретные объекты, множества (сочетания,перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики - алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике). Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».
Методы Комбинаторики Перестановкой из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n. Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений. Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел. Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.
Комбинаторные задачи Комбинаторика – от латинского слова combinare, что означает «соединять, сочетать». Методы комбинаторики находят широкое применение в физике, химии, биологии, экономики и др. областях знания. Комбинаторику можно рассматривать как часть теории множеств – любую комбинаторную задачу можно свести к задаче о конечных множествах и их отображениях.
I. Уровни решения комбинаторных задач 1. Начальный уровень. Задачи поиска хотя бы одного решения, хотя бы одного расположения объектов, обладающих заданным свойствами - отыскание такого расположения десяти точек на пяти отрезках, при котором на каждом отрезке лежит по четыре точки; - такого расположения восьми ферзей на шахматной доске, при котором они не бьют друг друга. Иногда удаётся доказать, что данная задача не имеет решения (например, нельзя расположить 10 шаров в 9 урнах так, что бы в каждой урне было не более одного шара – хотя бы в одной урне окажется не менее двух шаров). 6
2. Второй уровень. Если комбинаторная задача имеет несколько решений, то возникает вопрос о подсчете числа таких решений, описании всех решений данной задачи. 3. Третий уровень. Решения данной комбинаторной задачи отличаются друг от друга некоторыми параметрами. В этом случае возникает вопрос отыскания оптимального варианта решения такой задачи. Например: Путешественник хочет выехать из города А, посетить города В, С, и D. После чего вернуться в город А. 7
8 На рис. изображена схема путей, связывающих эти города . Различные варианты путешествий отличаются друг от друга порядком посещения городов В, С, и.D. Существует шесть вариантов путешествия. В таблице указаны варианты и длин каждого пути:
Правила суммы и произведения 1. Сколько различных коктейлей можно составить из четырёх напитков, смешивая их в равных количествах по два? AB, AC, AD, BC, BD, CD – всего 6 коктейлей 2. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3 ? Первой цифрой двузначного числа может одна из цифр 1, 2, 3 (цифра 0 не может быть первой). Если первая цифра выбрана, то вторая может быть любая из цифр 0, 1, 2, 3. Т.к. каждой выбранной первой соответствует четыре способа выбора второй, то всего имеется 4 + 4 + 4 = 4·3 = 12 различных двузначных чисел. 9 А D С В
2. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3 ? 4 + 4 + 4 = 4·3 = 12 различных двузначных чисел. Первая цифра вторая цифра 1 2 3 10 0 1 2 3 0 1 2 3 0 1 2 3
«Примеры решения комбинаторных задач: перебор вариантов, правило суммы, правило умножения». 11 Сколькими способами могут быть расставлены 4 участниц финального забега на четырёх беговых дорожках? Рп = 4· 3 ·2 ·1= 24 способа (перестановки из 4-х элементов) 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 3 4 2 4 2 3 4 3 4 2 3 2 3 4 1 4 3 1 4 3 4 1 1 3 2 4 1 4 1 2 4 2 4 1 2 1 2 3 1 3 1 2 3 2 3 1 2 1 1 дорожка 2 доржка 3доржка 4 дор. Р е ш е н о п е р е б о р о м в а р и а н т о в
Пример Задачи Комбинаторики При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, таких, что сумма очков на верхних гранях равна двенадцати? Решение: Каждый возможный исход соответствует функции (аргумент функции - это номер кости, значение - очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, такая, что сумма очков на верхних гранях равна двенадцати.
Разделы Комбинаторики!
Перечислительная комбинаторика Перечислительная комбинаторика (или исчисляющая комбинаторика) рассматривает задачи о перечислении или подсчёте количества различных конфигураций (например, перестановок) образуемых элементами конечных множеств, на которые могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п. Количество конфигураций, образованных несколькими манипуляциями над множеством, подсчитывается согласно правиламсложения и умножения. Типичным примером задач данного раздела является подсчёт количества перестановок. Другой пример - известная Задача о письмах.
Вероятностная комбинаторика! Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства у заданного множества.
Краткая историческая справка Первые работы, в которых зарождались основные понятия теории вероятностей, представляли собой попытки создания теории азартных игр (Кардано, Гюйгенс, Паскаль, Ферма и другие в XVI-XVII вв.). Следующий этап развития теории вероятностей связан с именем Якоба Бернулли (1654-1705). Доказанная им теорема, получившая впоследствии название «Закона больших чисел», была первым теоретическим обоснованием накопленных ранее фактов. Дальнейшими успехами теория вероятностей обязана Муавру, Лапласу, Гауссу, Пуассону и др. Новый, наиболее плодотворный период связан с именами П. Л. Чебышева (1821-1894) и его учеников А.А.Маркова(1856-1922) и А. М.Ляпунова (1857-1918). В этот период теория вероятностей становится стройной математической наукой. Ее последующее развитие обязано в первую очередь русским и советским математика м (С. Н. Бернштейн, В. И. Романовский, А. Н. Колмогоров, А. Я. Хинчин, Б. В. Гнеденко, Н. В. Смирнов и др.). В настоящее время ведущая роль в создании новых ветвей теории вероятностей также принадлежит советским
Элементыкомбинаторики.
Электронное учебно-методическое пособие
для учащихся 9-11 классов.
Автор-составитель:
Каторова О.Г.,
учитель математики
МБОУ «Гимназия №2»
г.Саров
Комбинаторика
Комбинаторика – это разделматематики, в котором изучаются
вопросы выбора или расположения
элементов множества в соответствии
с заданными правилами.
«Комбинаторика» происходит от латинского
слова «combina», что в переводе на русский
означает – «сочетать», «соединять».ИСТОРИЧЕСКАЯ СПРАВКА
Термин "комбинаторика" был
введён в математический обиход
всемирно
известным
немецким
учёным Г.В.Лейбницем, который в
1666 году опубликовал "Рассуждения
о комбинаторном искусстве".
Г.В.Лейбниц
В XVIII веке к решению комбинаторных задач обращались
и другие выдающиеся математики. Так, Леонард Эйлер
рассматривал задачи о разбиении чисел, о паросочетаниях, о
циклических расстановках, о построении магических и
латинских квадратов.Комбинаторика занимается
различного рода соединениями
(перестановки, размещения,
сочетания), которые можно
образовать из элементов
некоторого конечного множества.
Комбинаторные соединения
Перестановки1.
2.
Перестановки без повторений
Перестановки с повторениями
Размещения
1.
2.
Размещения без повторений
Размещения с повторениями
Сочетания
1.
2.
Сочетания без повторений
Сочетания с повторениямиПерестановки – соединения,
которые можно составить из n
элементов, меняя всеми
возможными способами их порядок.
Формула:
Историческая справка
В 1713 году было опубликованосочинение Я. Бернулли "Искусство
предположений", в котором с
достаточной полнотой были изложены
известные к тому времени
комбинаторные факты.
"Искусство
предположений" не было завершено
автором и появилось после его смерти.
Сочинение состояло из 4 частей,
комбинаторике была посвящена
вторая часть, в которой содержится
формула для числа перестановок из n
элементов.
Пример
Сколькими способами могут 8 человек встать вочередь к театральной кассе?
Решение задачи:
Существует 8 мест, которые должны занять 8 человек.
На первое место может встать любой из 8 человек, т.е. способов
занять первое место – 8.
После того, как один человек встал на первое место, осталось 7
мест и 7 человек, которые могут быть на них размещены, т.е.
способов занять второе место – 7. Аналогично для третьего,
четвертого и т.д. места.
Используя принцип умножения, получаем произведение. Такое
произведение обозначается как 8! (читается 8 факториал) и
называется перестановкой P8.
Ответ: P8 = 8!
Проверь себя
1) Сколькими способами можно поставитьрядом на полке четыре различные
книги?
РЕШЕНИЕ
Проверь себя
2) Сколькими способами можно положить10 различных открыток в 10 имеющихся
конвертов (по одной открытке в конверт)?
РЕШЕНИЕ
Проверь себя
3) Сколькими способами можно рассадитьвосьмерых детей на восьми стульях в столовой
детского сада?
РЕШЕНИЕ
Проверь себя
4) Сколько различных слов можно составить,переставляя местами буквы в слове
«треугольник» (считая и само это слово)?
РЕШЕНИЕ
Проверь себя
5) Сколькими способами можно установитьдежурство по одному человеку в день среди семи
учащихся группы в течение 7 дней (каждый
должен отдежурить один раз)?
РЕШЕНИЕ
Проверь себя
Перестановки сповторениями
Всякое размещение с повторениями, в
котором элемент а1 повторяется k1 раз, элемент
a2 повторяется k2 раз и т.д. элемент an
повторяется kn раз, где k1, k2, ..., kn - данные
числа, называется перестановкой с
повторениями порядка
m = k1 + k2 + … + kn, в которой данные
элементы a1, a2, …, an повторяются
соответственно k1, k2, .., kn раз.
Проверь себя
Перестановки сповторениями
Теорема. Число различных перестановок с
повторениями из элементов {a1, …, an}, в
которых элементы a1, …, an повторяются
соответственно k1, ..., kn раз, равно
(k1+k2+…+kn)!
m!
P
k1! k2! … kn!
k1! k2! … kn!
Проверь себя
ПримерСлова и фразы с переставленными буквами
называют анаграммами. Сколько анаграмм можно
составить из слова «макака»?
Решение.
Всего в слове «МАКАКА» 6 букв (m=6).
Определим сколько раз в слове используется каждая буква:
«М» - 1 раз (k1=1)
«А» - 3 раза (k2=3)
«К» - 2 раза (k3=2)
m!
Р=
k1! k2! …kn!
6!
4*5*6
Р1,3,2 =
= 2 = 60.
1! 3! 2!
Проверь себя
1) Сколько различных слов можно получить,переставляя буквы слова "математика" ?
РЕШЕНИЕ
Проверь себя
2) Сколькими способами можно расставить напервой горизонтали шахматной доски комплект
белых фигур (король, ферзь, две ладьи, два
слона и два коня)?
РЕШЕНИЕПроверь себя
3) У мамы 2 яблока, 3 груши и 4 апельсина.
Каждый день в течение девяти дней подряд она
дает сыну один из оставшихся фруктов.
Сколькими способами это может быть сделано?
РЕШЕНИЕИсторическая справка
Комбинаторные мотивы можно
заметить еще в символике китайской «Книги
перемен» (V век до н. э.).
В XII в. индийский математик Бхаскара в
своём основном труде «Лилавати» подробно
исследовал задачи с перестановками и
сочетаниями, включая перестановки с
повторениями.
Пример
РазмещенияРазмещением из n элементов по k
(k n) называется любое множество,
состоящее из любых k элементов, взятых в
определенном порядке из n элементов.
Два размещения из n элементов считаются
различными, если они отличаются самими
элементами или порядком их расположения.
А n(n 1)(n 2) ... (n (k 1))
k
n
Проверь себя
ПримерСколькими способами из 40 учеников класса
можно выделить актив в следующем составе:
староста, физорг и редактор стенгазеты?
Решение:
Требуется выделить упорядоченные трехэлементные
подмножества множества, содержащего 40
элементов, т.е. найти число размещений без
повторений из 40 элементов по 3.
40!
A=
=38*39*40=59280
37!
3
40
Проверь себя
1. Из семи различных книг выбираютчетыре. Сколькими способами это можно
сделать?
РЕШЕНИЕ
Проверь себя
2. В чемпионате по футболу участвуютдесять команд. Сколько существует
различных возможностей занять
командам первые три места?
РЕШЕНИЕ
Проверь себя
3. В классе изучаются 7 предметов. В среду 4урока, причем все разные. Сколькими
способами можно составить расписание на
среду?
РЕШЕНИЕ
Проверь себя
Размещения сповторениями
Размещения с повторениями –
соединения, содержащие n элементов,
выбираемых из элементов m различных
видов (n m) и отличающиеся одно от
другого либо составом, либо порядком
элементов.
Их количество в предположении
неограниченности количества элементов
каждого вида равно
Проверь себя
Пример использованияВ библиотеку, в которой есть много
одинаковых учебников по десяти
предметам, пришло 5 школьников,
каждый из которых хочет взять учебник.
Библиотекарь записывает в журнал по
порядку названия (без номера) взятых
учебников без имен учеников, которые их
взяли. Сколько разных списков в журнале
могло появиться?
Историческая справка
Решение задачиТак как учебники по каждому
предмету одинаковые, и библиотекарь
записывает лишь название (без
номера),то список – размещение с
повторением, число элементов
исходного множества равно 10, а
количество позиций – 5.
Тогда количество разных списков равно
= 100000.
Ответ: 100000
Размещения
Проверь себя!1. Телефонный номер состоит из 7 цифр.
Какое наибольшее число звонков
неудачник-Петя может совершить
прежде, чем угадает правильный номер.
РЕШЕНИЕ
РЕШЕНИЕ
Пример
Проверь себя!2. Сколькими способами можно
написать слово, составленное из
четырех букв английского алфавита?
РЕШЕНИЕ
Проверь себя
Проверь себя!3. В магазине, где есть 4 вида мячей,
решили поставить в ряд 8 мячей. Сколькими
способами можно это сделать, если их
расположение имеет значение?
РЕШЕНИЕ
Проверь себя
Проверь себя!4. Сколькими способами можно пришить на
костюм клоуна в линию шесть пуговиц
одного из четырех цветов, чтобы получить
узор?
РЕШЕНИЕ
Проверь себя
СочетанияСочетания – соединения, содержащие по
m предметов из n, различающихся друг от
друга по крайней мере одним предметом.
Сочетания – конечные множества, в
которых порядок не имеет значения.
Проверь себя
СочетанияФормула нахождения количества
сочетаний без повторений:
Проверь себя
Историческая справкаВ 1666 году Лейбниц опубликовал "Рассуждения
о комбинаторном искусстве". В своём сочинении
Лейбниц, вводя специальные символы, термины для
подмножеств и операций над ними, находит все k сочетания из n элементов, выводит свойства
сочетаний:
,
,
Проверь себя
Пример использования:Сколькими способами можно выбрать двух
дежурных из класса, в котором 25 учеников?
Решение:
m = 2 (необходимое количество дежурных)
n = 25 (всего учеников в классе)
Размещения с повторениями
Проверь себя!1) Сколькими способами можно
делегировать троих студентов на
межвузовскую конференцию из 9 членов
научного общества?
РЕШЕНИЕ
Пример использования
Проверь себя!2) Десять участников конференции
обменялись рукопожатиями, пожав руку
каждому. Сколько всего рукопожатий было
сделано?
РЕШЕНИЕ
Решение задачи
Проверь себя!3) В школьном хоре 6 девочек и 4 мальчика.
Сколькими способами можно выбрать из
состава школьного хора 2 девочек и 1 мальчика
для участия в выступлении окружного хора?
РЕШЕНИЕ
Проверь себя!
4) Сколькими способами можно выбрать 3спортсменов из группы в 20 человек для
участия в соревнованиях?
РЕШЕНИЕ
Проверь себя!
5) В классе 10 учебных предметов и 5 разныхуроков в день. Сколькими способами могут
быть распределены уроки в один день?
РЕШЕНИЕ
Проверь себя!
Сочетания с повторениямиОпределение
Сочетаниями с повторениями из m по
n называют соединения, состоящие из n
элементов, выбранных из элементов m
разных видов, и отличающиеся одно от
другого хотя бы одним элементом.
Число сочетаний из m по n
обозначают
Проверь себя!
Сочетания с повторениямиЕсли из множества, содержащего n элементов, выбирается
поочередно m элементов, причём выбранный элемент
каждый раз возвращается обратно, то количество способов
произвести неупорядоченную выборку – число сочетаний с
повторениями – составляет
Проверь себя!
Историческая справкаКрупнейший индийский математик
Бхаскара Акария (1114–1185) также
изучал различные виды комбинаторных
соединений. Ему принадлежит трактат
"Сидханта–Широмани" ("Венец учения"),
переписанный в XIII в. на полосках
пальмовых листьев. В нём автор дал
словесные правила для нахождения
и
,указав их применения и поместив
многочисленные примеры
Проверь себя!
Пример использованияЗадача №1
Сколько наборов из 7 пирожных
можно составить, если в распоряжении
имеются 4 сорта пирожных?
Решение:
Проверь себя!
Пример использованияЗадача №2
Сколько костей находится в обычной
игре "домино"?
Решение: Кости домино можно рассматривать как
сочетания с повторениями по две из семи цифр
множества (0,1,2,3,4,5,6).
Число всех таких
сочетаний равно
Проверь себя!
Проверь себяЗадача 1.
В буфете Гимназии продаются 5 сортов
пирожков: с яблоками, с капустой,
картошкой, мясом и грибами. Скольким
числом способов можно сделать покупку из
10 пирожков?
РЕШЕНИЕ
Сочетания
Проверь себяЗадача 2.
В коробке лежат шары трех цветов-
красного, синего и зеленого. Сколькими
способами можно составить набор из двух
шаров?
РЕШЕНИЕ
Сочетания
Проверь себяЗадача 3.
Сколькими способами можно выбрать 4
монеты из четырех пятикопеечных монет и из
четырех двухкопеечных монет?
РЕШЕНИЕПроверь себя
Задача 4.
Сколько будет костей домино,
если в их
образовании использовать все цифры?
РЕШЕНИЕПроверь себя
Задача 5.
Палитра юного импрессиониста состоит из 8
различных красок. Художник берет кистью
наугад любую из красок и ставит цветное
пятно на ватмане. Затем берет следующую
кисть, окунает её в любую из красок и делает
второе пятно по соседству. Сколько
различных комбинаций существует для
шести пятен?
РЕШЕНИЕИспользуемая литература
Алгебра и начала математического
анализа.11 класс/ Ю.М.Колягин, М.В.Ткачева,
Н.Е.Федорова, М.И.Шабунин. –
М.:Просвещение, 2011.
Виленкин Н.Я. Комбинаторика. – М., 1969
Виленкин Н.Я. Комбинаторика. – МЦМНО,
2010
ru.wikipedia.org›wiki/История комбинаторики