Комбинаторика лекции. Решение комбинаторных задач. Размещения с повторениями

комбинаторика - рассматриваются взаимосвязано.

Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Например, сколькими способами могли быть распределены золотая, серебряная и бронзовая медали на Олимпийских играх в Сеуле по баскетболу; или сколькими различными способами можно разместить здания на площади ? Задачи такого типа называются комбинаторными .

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

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

Теоретические исследования вопросов комбинаторики предприняли Паскаль и Ферма, Бернулли, Лейбниц и Эйлер и др.

Для инженерных специальностей университета комбинаторные задачи приходится решать в следующих случаях:

1. при конструировании :
   • для оптимального размещения элементов системы;
   • для размещения микросхем на плате или элементов на кристалле;
   • при трассировке (выборе маршрута);
2. синтезе схем и проектирования:
   • при решении вопроса, какой набор стандартных микросхем выбрать, чтобы реализовать разработанную схему устройства;
   • при разработке схемы на подсхемы для реализации различными блоками и т. д.;
3. при контроле, выбирая-перебирая последовательность тестирующих сигналов;
4. в организации систем, решая вопрос, каким выбрать оптимальный маршрут передачи информации по сети и т. п.

Общие правила комбинаторики

Рассмотрим некоторые конкретные задачи.

Задача. 1 . "Суеверные велосипедисты"

"Опять восьмерка" - воскликнул председатель клуба велосипедистов, - а все потому, что у меня билет № 008. Надо менять номера и проводить перерегистрацию".

Итак, сколько членов было в клубе, если известно, что использованы все трехзначные номера, не содержащие ни одной цифры 8?

00	01	02	....................	09
10	11	12	....................	19
20	21	22	....................	29
30	31	32	....................	39
40	.	.	....................	.
50	.	.	....................	.
60	.	.	....................	.
70	.	.	....................	.
80	.	.	....................	.
90	.	.	....................	.

Для решения этой задачи определим сначала, сколько однозначных номеров не содержит цифру 8? Это 0, 1, 2, 3, 4, 5, 6, 7, 9 - всего девять цифр, а теперь найдем все двузначные номера: их ( таблица ). За каждым двузначным номером можно поставить любую допустимую цифру, следовательно, . Значит в клубе было 729 велосипедистов.

В другом клубе велосипедисты были ещё суевернее и решили, что цифра 0 тоже похоже на вытянутое колесо и они отказались от этой цифры.

Сколько членов было в клубе, если номера билетов были трехзначными и не включали цифр 0 и 8? .

Задача 2 . "Секретный замок"

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

Всего попыток , одна из которых удачная, следовательно неудачных попыток .

Задача 3 . " Команда космического корабля"

В случае, когда число возможных выборов на каждом шаге зависит от того какие элементы были выбраны ранее, удобно решение изображать в виде "дерева". Сначала из одной точки проводят столько отрезков, сколько различных выборов можно сделать на 1-м шаге. Из конца каждого отрезка проводят столько отрезков, сколько можно сделать на 2-м шаге и т. д. В результате получается " дерево решений ".

Рассмотрим задачу о формировании команды космического корабля. Известно, что возникнет вопрос психологической совместимости. Предположим, надо составить команду из 3-х человек: командира, инженера и врача. На место командира есть четыре кандидата: , на место инженера три - , на место врача три - . Проведенная проверка показала, что совместим с ; совместим с ; совместим с и ; совместим с ; не совместим с ; не совместим с ; не совместим с .

Рис. 5.1.

Сколькими способами при этих условиях может быть составлена команда корабля? По результатам совместимости строится дерево решений ( рис. 5.1). Итак, всего 11 комбинаций, а без ограничения .

Упорядоченные множества. Перестановки

Множество называется упорядоченным , если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от до где - число элементов множества .

Всякое конечное множество можно сделать упорядоченным, если, например, переписать все элементы множества в некоторый список (.), а затем каждому элементу присвоить номер.

Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком.

Различные упорядоченные множества , которые отличаются лишь порядком элементов, называются перестановками этого множества .

Пример . Перестановки множества из 3-х элементов имеют вид .

Число перестановок из элементов !

Задача 1 . Сколькими способами можно разместить на плате 4 элемента? .

Задача 2 . Сколькими способами можно выстроить в линейку 10 человек (5 девушек и 5 юношей) с условием, чтобы девушки и юноши чередовались, первая - девушка? 5 девушек можно разместить ! способами, а 5 юношей аналогично !. Следовательно, всего способов .

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

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

Пусть - множество из элементов и -

План:

1. Элементы комбинаторики.

2. Общие правила комбинаторики.

4. Применение графов (схем) при решении комбинаторных задач.

1. Комбинаторика и ее возникновение.

Комбинаторика - это область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству.

Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры (карты, кости). Широко были распространены лотереи. Первоначально комбинаторные задачи касались в основном азартных игр: сколькими способами можно получить данное число очков, бросая 2 или 3 кости или сколькими способами можно получить 2-ух королей в некоторой карточной игре. Эти и другие проблемы азартных игр являлись движущей силой в развитии комбинаторики и далее в развитии теории вероятностей.

Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицы (числа способов выпадения k очков на r костях). Однако, он не учел, одна и та же сумма очков может выпасть различными способами, поэтому его таблицы содержали большое количество ошибок.

Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские математики Блез Паскаль и Ферма. Исходным пунктом их исследований были так же проблемы азартных игр.

Дальнейшее развитие комбинаторики связано с именами Я. Бернулли, Г. Лейбница, Л. Эйлера. Однако, и в их работах основную роль играли приложения к различным играм.

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

2. Общие правила комбинаторики.

Правило суммы: Если некоторый объект А может быть выбран m способами, а объект В- k способами, то объект «либо А, либо В» можно выбрать m +k способами.

Примеры:

1. Допустим, что в ящике находится n разноцветных шаров. Произвольным образом вынимается 1 шарик. Сколькими способами это можно сделать?

Ответ: n способами.

Распределим эти n шариков по двум ящикам: в первый- m шариков, во второй- k шариков. Произвольным образом из произвольно выбранного ящика вынимается 1 шарик. Сколькими способами это можно сделать?

Решение: Из первого ящика шарик можно вынуть m способами, из второго- k способами. Тогда всего способов m+k=n .

2. Морской семафор.

В морском семафоре каждой букве алфавита соответствует определенное положение относительно тела сигнальщика двух флажков. Сколько таких сигналов может быть?

Решение: Общее число складывается из положений, когда оба флажка расположены по разные стороны от тела сигнальщика и положений, когда они расположены по одну сторону от тела сигнальщика. При подсчете числа возможных положений применяется правило суммы.

Правило произведения: Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора объекта А) k способами, то пары объектов «А и В» можно выбрать m *k способами.

Примеры:

1. Сколько двузначных чисел существует?

Решение: Число десятков может быть обозначено любой цифрой от 1 до 9. Число единиц может быть обозначено любой цифрой от 0 до 9. Если число десятков равно 1, то число единиц может быть любым (от 0 до 9). Таким образом, существует 10 двузначных чисел, с числом десятков- 1.Аналогично рассуждаем и для любого другого числа десятков. Тогда можно посчитать, что существует 9 *10 = 90 двузначных чисел.

2. Имеется 2 ящика. В одном лежит m разноцветных кубиков, а в другом- k разноцветных шариков. Сколькими способами можно выбрать пару «Кубик-шарик»?

Решение: Выбор шарика не зависит от выбора кубика, и наоборот. Поэтому, число способов, которыми можно выбрать данную пару равно m *k .

3. Генеральная совокупность без повторений и выборки без повторений.

Генеральная совокупность без повторений - это набор некоторого конечного числа различных элементов a 1 , a 2 , a 3 , ..., a n .

Пример: Набор из n разноцветных лоскутков.

Выборкой объема k (k n ) называется группа из m элементов данной генеральной совокупности.

Пример: Пестрая лента, сшитая из m разноцветных лоскутков, выбранных из данных n .

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

- число размещений из n по k .

Число размещений из n по k можно определить следующим способом: первый объект выборки можно выбрать n способами, далее второй объект можно выбрать n -1 способом и т.д.

Преобразовав данную формулу, имеем:

Следует помнить, что 0!=1.

Примеры:

1. В первой группе класса А первенства по футболу участвует 17 команд. Разыгрываются медали: золото, серебро и бронза. Сколькими способами они могут быть разыграны?

Решение: Комбинации команд-победителей отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 17 по 3.

2. Научное общество состоит из 25-ти человек. Необходимо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами это можно сделать?

Решение: Комбинации руководящего состава общества отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 25 по 4.

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

Число перестановок.

Примеры:

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

Решение: Имеем перестановки из 5 элементов. 2. Сколькими способами можно собрать 6 разноцветных лоскутков в пеструю ленту?
Решение: Имеем перестановки из 6 элементов.

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

- число сочетаний из n по k

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

1. Если в полуфинале первенства по шахматам участвует 20 человек, а в финал выходят лишь трое, то сколькими способам и можно определить эту тройку?

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки, вышедшие в финал, являются сочетаниями из 20 по 3.

2. Сколькими способами можно выбрать трех делегатов из десяти человек на конференцию?

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки делегатов являются сочетаниями из 10 по 3.

Конспект:

4.Применение графов (схем) при решении комбинаторных задач.

В случае, когда число возможных выборов на каждом шагу зависит от того, какие элементы были выбраны ранее, можно изобразить процесс составления комбинаций в виде «дерева». Сначала из одной точки проводят столько отрезков, сколько различных выборов можно сделать на первом шагу. Из конца каждого отрезка проводят столько отрезков, сколько можно сделать выборов на втором шагу, если на первом шагу был выбран данный элемент и т.д.

Задача:

При составлении команд космического корабля учитывается вопрос и психологической совместимости участников путешествия. Необходимо составить команду космического корабля из 3 человек: командира, инженера и врача. На место командира есть 4 кандидата: a 1 , a 2 , a 3 , a 4 .На место инженера- 3: b 1 , b 2 , b 3 . На место врача- 3: c 1 , c 2 , c 3 . Проведенная проверка показала, что командир a 1 психологически совместим с инженерами b 1 и b 3 и врачами c 1 и c 3 . Командир a 2 - с инженерами b 1 и b 2 . и всеми врачами. Командир a 3 - с инженерами b 1 и b 2 и врачами c 1 и c 3 . Командир a 4 -со всеми инженерами и врачом c 2 . Кроме того, инженер b 1 не совместим с врачом c 3 , b 2 - с врачом c 1 и b 3 - с врачом c 2 . Сколькими способами при этих условиях может быть составлена команда корабля?

Решение:

Составим соответствующее «дерево».

Ответ: 10 комбинаций.

Такое дерево является графом и применяется для решения комбинаторных задач.

1. 1. ДИСКРЕТНАЯ МАТЕМАТИКА Курс лекций Московский государственный университет имени М.В.Ломоносова Экономический факультет 1
2. 2. Лекция 4 Комбинаторика 2
3. 3. Комбинаторика 3 В этой лекции мы узнаем, как подсчитывать элементы конечных множеств, удовлетворяющих определенным свойствам. Мы познакомимся с типичными ситуациями, в каждой из которых можно для упрощения расчетов использовать определенную свою формулу. Мы познакомимся также с главной областью приложения комбинаторики - расчетом вероятностей, полная теория которых изучается на втором курсе.
4. 4. Основная задача комбинаторики 4 С элементами конечных множеств можно производить различные действия: упорядочивать их, объединять в группы, отбирать подмножества по дополнительным признакам и свойствам, и т.д. При этом возникают новые, более сложные (комбинированные) множества, элементы которых тоже нужно уметь пересчитывать. . Иногда комбинаторику определяют также как науку о подсчете числа подмножеств, удовлетворяющих определенным свойствам. Предмет комбинаторики: подсчет числа способов выполнить определенные действия.
5. 5. Основные принципы комбинаторики. 5 Большинство задач комбинаторики можно решить, используя один из двух простых принципов, интуитивно очевидных, легко проверяемых на примерах, и используемых в качестве аксиом. Практически гораздо чаще применяется принцип умножения, поскольку очень часто сложные действия приходится разлагать на последовательность простых. Принцип сложения применим к ситуациям, когда есть выбор между двумя альтернативными действиями (когда два действия исключают друг друга). Принцип умножения, напротив, применяется к действиям, которые выполняются совместно (последовательно или одновременно)
6. 6. Принцип сложения 6 Принцип сложения: если действие 1 можно выполнить n способами, а действие 2 можно выполнить m способами, то сложное действие, состоящее в выполнении одного из действий 1 или 2 (но не обоих), можно выполнить n+m способами. Пример: как провести вечер: куда пойти? В кино В гости «Она» «Помпеи 3D» Миша Маша Леша Всего 2 + 3 = 5 способов провести вечер.
7. 7. Принцип умножения 7 Принцип умножения: если действие A можно выполнить n способами, а действие B можно выполнить m способами, то сложное действие, состоящее в выполнении обоих действий A и B (одновременно или последовательно) можно выполнить nm способами. В кино!!! (но с кем?) Наташа Таня Оля «Академия вампиров» «В спорте только девушки» Всего: 2*3=6 способов сходить в кино.
8. 8. Вероятность 8 Вероятность - мера уверенности в том, что некоторое событие произойдет (измеряется числом от 0 до 1). В простейшем случае вероятность вычисляется комбинаторно. Практически, вычисление всегда начинают со знаменателя, разбираются с тем, что считать действием, какие действия считать различными, вычисляют общее количество таких действий, и только после этого переходят к числителю. Разбивают сложный благоприятный исход на простейшие или стандартные, и используют принципы комбинаторики. Определение вероятности для простейшего случая равновероятных исходов – отношение числа благоприятных действий (или их исходов) к общему числу действий (их исходов): n m p 
9. 9. 9 Один из студентов каждую минуту задумывает одну из цифр (от 0 до 9), и записывает ее, а другой, находящийся в другом месте, пытается ее «принять телепатически», и также записывает (часы синхронизированы). В предположении, что телепатии не существует, какова вероятность, что задуманная цифра будет угадана правильно? Какова вероятность, что три задуманные подряд цифры будут угаданы правильно? Телепатия. Потусторонняя задача…
10. 10. Применение принципа умножения 10 ПРИМЕР: камера хранения. Для того, чтобы открыть камеру хранения, используется комбинация из 4 цифр (от 0 до 9), набираемая на 4 колесиках. а) Найти вероятность наугад открыть камеру хранения. РЕШЕНИЕ: Устанавливаем цифры на каждом из колесиков по очереди; каждый раз у нас есть 10 вариантов (цифры от 0 до 9), по принципу умножения они перемножаются: 10101010 = 10000 вариантов. Открывает дверцу из них только один, так что вероятность наудачу открыть ее равна 1/10000 = 0,0001. Довольно безнадежное занятие. Даже в простейших случаях удобно раскладывать сложные действия на простейшие, например, представляя себе, что они выполняются поочередно.
11. 11. Ценность информации 11 В результате использования дополнительной информации в сообщении перебор сократился вдвое, отсюда можно в принципе подсчитать, сколько стоит сообщенная информация, если ее можно было бы купить. Продолжение: б) Найти вероятность наугад открыть камеру хранения, если дополнительно стало известно, что все цифры на правильном номере разные. РЕШЕНИЕ: Теперь на втором колесике нужно не повторить цифру, набранную на первом, так что число вариантов сокращается до 9, далее уже две цифры становятся запрещенными, так что всего вариантов остается 8, а на последнем – уже 7 вариантов: 10987 = 5040 вариантов. Открывает дверцу по-прежнему только один, откуда вероятность открыть дверцу становится 1/5040  0,0002.
12. 12. Задачка на дом 12 1. N человек становятся случайным образом в очередь на концерт известной группы. Какова вероятность того, что два определенных человека (назовем их A и B) будут стоять рядом (и будут иметь шанс как бы случайно познакомиться). 2. N человек приглашены в гости и располагаются за круглым столом. Какова вероятность того, что те же A и B случайно окажутся на соседних местах. А и B сидели …и стояли.
13. 13. Задачка на дом 13 В ночной электричке, состоящей из 8 вагонов, едут 6 человек. При посадке каждый человек выбирает свой вагон наугад и далее в другой вагон не переходит. Найти вероятность того, что: 1. все едут в разных вагонах 2. не менее двух человек оказываются в одном вагоне. 3. все набьются в один вагон и будут дрожать вместе. Последняя электричка
14. 14. Стандартные действия комбинаторики 14 Основных правил для решения комбинаторных задач в принципе достаточно. Но практически их используют только в нестандартных задачах. Большинство же решаемых в комбинаторике задач являются типовыми, стандартными. Для них удобнее прямо использовать готовые формулы, каждая из которых ассоциируется с определенным стандартным действием. Стандартные действия комбинаторики: Перестановки Размещения Выборки Разбиения (на группы)
15. 15. Перестановки 15 Две перестановки отличаются друг от друга только порядком элеметов, все элементы у них общие. Первый элемент можно поставить на любое из n мест, следующий – на любое из (n-1) мест, и так далее. Последний элемент занимает единственное оставшееся место. Это приводит к формуле n!=n(n-1)(n-2)...1 (n-факториал). ПРИМЕР: Число перестановок 5 книг на полке равно 5!.
16. 16. Размещения 16 Два размещения отличаются друг от друга составом и порядком элементов. k nA – число размещений k элементов по n местам. Для первого элемента есть n мест, далее– (n-1) мест, и так далее. Для последнего k-го элемента остается (n–k+1) мест. Это приводит к формуле)1)...(2)(1( knnnnAk n . ("недоделанный факториал"). По сути это перестановка k элементов на n местах k
17. 17. Задачка на дом 17 Студентка садится в лифт вместе с другими 6 студентами (до этого момента они не были знакомы). Лифт идет на любой из 7 этажей (не считая нижнего). Выйдя из лифта на своем этаже, девушка заметила, что вместе с ней вышел юноша. Следует ли ей рассматривать это как нечто большее, чем случайность? А может это… .
18. 18. Задачка на дом 18 Будем считать, что день рождения наугад выбранного человека может прийтись на любой день из 365 дней в году. Какова вероятность того, что в группе из 23 человек у двух или более человек день рождения придется на один и тот же день? Гулянка по крупному.
19. 19. 19 Один человек придумал, как ему кажется, способ наверняка выиграть в рулетку. Он рассуждает так: шарик может остановиться на любом из 36 чисел: 1, 2, …36 (для простоты будем игнорировать 0). Если я буду ставить на определенное число 36 раз, я наверняка выиграю хотя бы раз. Прав ли он? Какова на самом деле вероятность хотя бы одного выигрыша? Найдите способ оценить ее приближенно без калькулятора). Утешительный приз Задачка на дом
20. 20. Выбор 20 Две выборки отличаются друг от друга только составом элементов, их порядок безразличен (поэтому в знаменателе появляется факториал числа элементов). Число способов выбора k элементов из имеющихся n элементов ввиду стандартности и широкой распространенности задачи выбора носит специальное название – число сочетаний из n элементов по k. ПРИМЕР: Число способов распределить 5 флаеров на дискотеку в компании из 7 человек равно 21 12345 345675 7    C . Число выборок, обозначаемое k nC , равно!)1)...(2)(1(k knnnn Ck n  
21. 21. Вывод формулы для числа сочетаний 21 Для получения формулы для числа выборок сводим задачу к уже изученному случаю (размещение с учетом порядка). Таким образом, мы исходим из числа размещений, но которое теперь (поскольку порядок k элементов безразличен) требуется разделить на число перестановок k элементов: !)1)...(2)(1(! k knnnn k A C k nk n   . Обратите внимание, что в числителе всего k сомножителей, столько же, сколько и в знаменателе.
22. 22. Свойство симметрии сочетаний 22 Выбранные и оставшиеся с точки зрения разбиения на группы равноправны, поэтому число способов выбрать k элементов равно числу способов оставить невыбранными n-k элементов kn n k n CC   ПРИМЕР: В задаче о распределении флаеров получаем гораздо более удобную формулу 21 12 672 7 5 7     CC .
23. 23. Вероятность для учебы 23 Каждый студент получает на экзамене 3 вопроса, случайно выбранных из 25 вопросов программы. Студент получит «5», если ответит правильно на все вопросы, «4» – только на два, «3» – только на один, и «2» - ни на один. Каковы вероятности получения пятерки, четверки, тройки и двойки? Экзаменационная ловушка.
24. 24. Математика риска 24 Лет двадцать назад в России была популярна лотерея «Спортлото», где нужно было, купив билет, зачеркнуть 6 названий видов спорта из 45. В еженедельном тираже объявлялись 6 выигрышных видов. Призовой фонд делился между угадавшими. Какова вероятность угадать три вида спорта? Все шесть? Счастливый билетик
25. 25. Выбор как разбиение на две группы 25 Можно придать формуле для сочетаний удобный для запоминания симметричный вид. Умножим числитель и знаменатель на (n-k)!, дополняющий числитель до полного факториала.)!(! ! 123)...(! 123)...()1)...(2)(1(knk n knk knknnnn     Итак,)!(! ! knk n Ck n   Симметрия поученной формулы позволяет рассматривать выбор как ситуацию разбиения на две группы (выбранные – оставшиеся) Итак, число способов),(knkPn  разбить множество, состоящее из n элементов, на две группы, первая из которых содержит k элементов, а вторая – n-k элементов, равно)!(! !),(knk n knkPn  
26. 26. Сложная выборка из двух типов элементов 26 Сложная выборка – это выборка из неоднородной совокупности, которая включает элементы двух или более типов. Чтобы составить сложную выборку, нужно сначала выбрать m элементов из M, обладающих нужным свойством, а затем отдельно выбрать n-m элементов из N-M не обладающих нужным свойством: mn MN m M CC   Вероятность такого факта равна n N mn MN m M C CC p   Пусть совокупность содержит N элементов, из которых только M обладают некоторым свойством (а значит N-M им не обладают).
27. 27. Приложение сложной выборки 27 Практически удобно представлять себе, что действия по формированию составляющих частей сложной выборки производятся отдельно, например, различными людьми В курсе теории вероятностей эта формула получит гордое имя гипергеометрического распределения. ПРИМЕР: Покупка телевизора на Митинском рынке. В ларьке имеется 10 телевизоров, из которых только 6 работают. За день продано 7 телевизоров. Найти вероятность того, что из них 4 работают. Рассчитываем по формуле сложной выборки 2 1 123 8910 4 21 56 7 10 3 4 4 6        C CC p
28. 28. Сложная выборка. Общий случай. 28 Рассмотрим теперь случай k различных типов элементов. Пусть совокупность содержит n элементов, из которых только n1 обладают свойством 1, n2 обладают свойством 2, …, nk обладают свойством k. Действуя по аналогии с случаем двух групп, и набирая в выборке элементы разных типов по отдельности, получаем k k n nnn n nnn n nn n n CCCC 11 3 21 2 1 1 ......  Прямым подсчетом можно убедиться, что это равно!!...! ! 21 knnn n 
29. 29. Разбиения на группы 29 Два разбиения отличаются друг от друга составом элементов групп, порядок элементов в группах безразличен, порядок групп существенен. Для вывода формулы для числа разбиений на группы можно пойти и другим путем: обобщить на случай k групп симметричную формулу для сочетаний. Количество способов)...,(21 kn nnnP , которыми можно разбить множество из n предметов на k различимых групп, содержащих соответственно 1n , 2n , …, kn предметов, равно!!...! ! 21 knnn n  ПРИМЕР: руководитель отдела, состоящего из 10 сотрудников, составляет график дежурств по пяти дням недели (каждый день должны дежурить два сотрудника, каждый сотрудник дежурит один день). У нас пять групп. По стандартной формуле числа разбиений получаем 10!/(2!2!2!2!2!)=1134000.
30. 30. Задачка на дом 30 На карточках складной азбуки написаны буквы: две «М», три «А», две «Т», и по одной «Е», «И» и «К». Маленький ребенок играет с карточками, прикладывая их друг к другу. Какова вероятность того, что случайно с первого раза он получит слово «МАТЕМАТИКА»? . Юный математический гений
31. 31. Задачка на дом 31 Найти вероятность того, что при вытаскивании трех карт из колоды из 52 карт получатся тройка, семерка и туз. Бедный Германн.
32. 32. Основные формулы комбинаторики. 32 Подведем итог, соберем вместе полученные результаты. Перестановки различаются только порядком элементов. Число перестановок n элементов равно n!=n(n-1)(n-2)...1 Размещения различаются составом и порядком элементов. Число размещений k элементов по n местам равно)1)...(2)(1( knnnnAk n . Выборки отличаются друг от друга составом элементов, порядок безразличен. Число выборок по k элементов из n элементов равно!)1)...(2)(1(k knnnn Ck n   Число разбиений множества из n предметов на k групп, содержащих 1n , 2n , …, kn элементов, равно k k n nnn n nn n n k kn CCC nnn n nnnP 11 2 1 1 ... 21 21 ... !!...! !),...,(  
33. 33. Конец лекции

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

Решение. Действием в данном случае является составление набора из ручки, карандаша и линейки; действие распадается на три этапа (части): выбрать ручку, выбрать линейку и выбрать карандаш. Первую часть действия – выбрать ручку – можно выполнить пятью способами, вторую часть действия – выбрать карандаш – можно выполнить семью способами, третью часть действия – выбрать линейку – можно выполнить десятью способами. Тогда все действие можно выполнить 5*7*10 =350 Число способов. Т.е. возможно 350 вариантов такого набора.

Пример. В столовой предлагают два различных первых блюда а1 и а2, три различных вторых блюда b1, b2, b3 и два вида десерта с1 и с2. Сколько различных обедов из трех блюд может предложить столовая? Решение. Пусть А – множество первых блюд, В – множество вторых блюд, а С – множество третьих блюд. По условию известно, что

Пример. "Команда космического корабля" Рассмотрим задачу о формировании команды космического корабля. Известно, что возникнет вопрос психологической совместимости. Предположим, надо составить команду из 3-х человек: командира, инженера и врача. На место командира есть четыре кандидата: a1, a2, a3, a4, на место инженера три - b1, b2, b3, на место врача три – c1, c2, c3. Проведенная проверка показала, что a1 совместим с b1, b2, c2,c3; a2 совместим с b1, b2,c1,c2,c3; a3 совместим с b1 и b2, c1, c3; a4 совместим с b1, b2, b3, c2 ; b1 не совместим с c3 ; b2 не совместим с c1 ; b3 не совместим с c2.

Расположение n различных элементов в определенном порядке называется перестановкой без повторений из n элементов. Например, на множестве из трех элементов {a,b,c} возможны следующие перестановки: abc, acb, bca, bac, cab, cba. Число различных перестановок без повторений из элементов обозначается P n и равно n!, т.е.

Таблица вариантов КБСКСБ БСКБКС СБКСКБ Дерево вариантов Правило умножения 1 полоса 3 способа 2 полоса 2 способа 3 полоса 1 способ = 6 Ответ: 6 способов Подсчет перестановок

Сочетанием без повторений из n элементов по k называется неупорядоченное k-элементное подмножество n-элементного множества. Число сочетаний без повторений из элементов по равно: Например, требуется подсчитать, сколькими способами можно составить бригаду из трех человек для дежурства в группе из 30 человек. Поскольку порядок расположения людей в бригаде не фиксируется и люди не повторяются, то мы имеем случай сочетаний из 30 элементов по 3 без повторений: Таким образом, бригаду дежурных из трех человек в группе из 30 человек можно выбрать 4060 различными способами.

Задача. У одного меломана есть 6 дисков известной поп-группы, у другого 8. Сколькими способами они могут обменяться тремя дисками? Решение: Каждый меломан должен выбрать из своих дисков три, которые он будет менять. Первый может сделать это C63 способами, а второй C83 способами. Так как выбор независим, то все вариантов C63*C83. Посчитаем: C 6 3 = 6*5*4/3! = 6*5*4/6 = 5*4 = 20. C 8 3 = 8*7*6/3! = 8*7*6/6 = 8*7 = 56. Ответ: 20*56=1120.

Рассмотрим выборку с повторениями Пусть имеется выборка из n элементов, причем k элементов из них - одинаковые. Число различных перестановок на элементах такой выборки равно: - число перестановок с k повторениями на множестве из n элементов Сочетание с повторениями из элементов по - неупорядоченная выборка элементов с возвращением из множества, содержащего элементов: - число различных сочетаний с повторениями из n элементов по k Размещения с повторениями из элементов по - расположение различных шаров по различным ячейкам - число различных размещений с повторениями

Пример. Сколько перестановок можно получить из букв слова КОЛОКОЛА? Решение. Требуется найти число перестановок с повторениями на множестве из 8 букв, среди которых: буква К повторяется 2 раза; буква О повторяется 3 раза; буква Л повторяется 2 раза буква А повторяется 1 раз. Таким образом,

Пример. Сколькими способами можно составить набор из 5 шоколадок, если имеются шоколадки трех сортов в количестве по 10 штук каждого вида? Решение. Поскольку при составлении шоколадного набора порядок расположения шоколадок не важен, то используем для подсчета формулу сочетаний с повторениями:

Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно Число всех возможных комбинаций из 30 букв по две равно Если учесть возможность того, что буквы могут повторяться, то число повторяющихся комбинаций равно 30 (одна возможность повтора для каждой буквы). Итого, полное количество комбинаций по две буквы равно 900. Если к номеру добавляется еще одна буква из алфавита в 30 букв, то количество комбинаций увеличивается в 30 раз, т.е. достигает комбинаций. Окончательно, т.к. каждой буквенной комбинации можно поставить в соответствие числовую комбинацию, то полное количество автомобильных номеров равно Пример. Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.

Транскрипт

1 Лекция 1. Тема: «Элементы комбинаторики» Определение. Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиально возможное количество различных вариантов развития событий. Основные правила комбинаторики Большинство комбинаторных задач решается с помощью двух основных правил - правила суммы и правила произведения. Правило суммы. Если некоторый объект можно выбрать способами, а другой объект можно выбрать способами, то выбор "либо, либо " можно осуществить способами. Правило произведения. Если объект можно выбрать способами, а после каждого такого выбора другой объект можно выбрать (независимо от выбора объекта) способами, то пары объектов и можно выбрать способами. Пример 1. Сколько существует двузначных чисел? Решение. Поскольку в двузначном числе цифра, обозначающая число десятков, должна быть отлична от нуля, то = {1, 2,..., 9}, = {0, 1, 2,..., 9} и Основные формулы комбинаторики 1. Выборки элементов без повторений Определение. Размещениями из элементов по называются такие выборки, которые, имея по элементов, выбранных из числа данных элементов, отличаются одна от другой либо составом элементов, либо порядком их расположения. Число размещений из элементов по обозначим Используя основное правило комбинаторики, получаем 1

2 Пример 2. Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные? Решение. Т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет: Пример 3. Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из пяти языков: русского, английского, немецкого, французского, испанского - на любой другой из этих пяти языков? Решение. Поскольку важен порядок, с какого языка задается перевод на другой, то для ответа на вопрос необходимо найти число размещений из пяти по два. Определение. Если, то - число таких размещений, которые отличаются только порядком расположения элементов. Такие размещения называются перестановками. Их число находится по формуле Пример 4. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд? Решение. Эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг. Определение. Выборки из элементов, взятых из данных, отличающихся только составом элементов, называются сочетаниями из элементов по. Число таких сочетаний находится Пример 5. В соревнованиях на первенство университета по волейболу участвуют 8 команд. Насколько более продолжительным будет турнир, организованный по круговой системе, чем по олимпийской? Решение. При проведении турнира по круговой системе каждый участник встречался с каждым и порядок их вхождения в пару не важен. Следовательно, по круговой системе потребуется провести встреч, а по олимпийской только - 7 (четыре встречи в полуфинале и одна в финале). финала, две - в 2

3 Пример 6. Сколькими способами читатель может выбрать две книжки из шести имеющихся? Решение. Число способов равно числу сочетаний из шести книжек по две, т.е. равно: Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно. Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов). Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны. И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере. Пример 7. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек? Решение. В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5. Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок, которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5. Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *...*n k. Пример 8. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n 1 элементов, а вторая - из n 2 элементов. Сколько различных пар элементов можно составить из этих двух 3

4 групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n 2. Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n 2. Так как в первой группе всего n 1 элемент, всего возможных вариантов будет n 1 *n 2. Пример 9. Сколько трехзначных четных чисел можно составить из цифр 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= Выборки элементов с повторениями В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =...n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k. Такой способ выбора в комбинаторики носит название выборки с возвращением. В данных выборках допускается повторение элементов, что является достаточно естественным (например, в телефонных и автомобильных номерах возможно использование одной цифры несколько раз). Пример 10. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8? Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625. Число размещений из элементов по с повторениями обозначается и находится каким образом Число перестановок, в которых 1-й элемент повторяется раз, 2-й - раз, а -й - раз, находится следующим образом: Пример 11. Сколько "слов" можно получить, переставляя буквы в слове МАТЕМАТИКА? Решение. Заметим, что если бы все буквы были различны, то получили бы новых "слов", но буква "М" употребляется в "слове" 2 раза, "А" - 3 раза, 4

5 "Т" - 2 раза, оставшиеся три буквы - по разу. Следовательно, искомое число будет в раз меньше, чем, и равно Число сочетаний с повторениями из элементов по выражается через число сочетаний без повторений: Пример 12. В кафе в продаже имеются 5 сортов пирожных. Сколькими способами 8 студенток могут заказать себе по одному пирожному? Решение. Зашифруем каждую покупку 8 пирожных единицами по 5 сортам, разделяя сорта нулями. Тогда каждой покупке будет соответствовать упорядоченный набор из 8 единиц и 4 (= 5-1) разделительных нулей, а общее число покупок будет соответствовать числу перестановок этих нулей и единиц. Таким образом, Задачи для самопроверки 1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться? 2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево? 3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день? 4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек? 5. Сколькими способами можно разложить восемь различных писем по восьми различным конвертам, если в каждый конверт кладется только одно письмо? 6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать? 5

6 Задачи 1. В чемпионате России по футболу участвуют 16 команд. Сколькими способами может определиться тройка призеров? 2. Из колоды, содержащей 36 карт, вынули 10 карт. Сколькими различными способами это можно сделать? В скольких случаях среди этих карт окажется хотя бы один туз? В скольких случаях окажется ровно один туз? 3. Сколькими способами 8 человек могут встать в очередь друг за другом? 4. Сколькими способами можно расставить на книжной полке 5 учебников по комбинаторике, 4 - по алгебре и 3 - по математическому анализу, если учебники по каждому предмету одинаковые? 5. На физмате работают 76 преподавателей. Из них 49 знают английский язык, 32 - немецкий и 15 - оба языка. Сколько преподавателей на физмате не знает ни английского, ни немецкого языков? 6. В цветочном магазине продаются цветы 4 сортов. Сколько можно составить различных букетов из пяти цветов в каждом? 7. В азбуке Морзе буквы представляются последовательностями тире и точек. Сколько символов потребуется, чтобы закодировать буквы русского алфавита? 8. Какова вероятность выиграть хотя бы один из призов в спортлото? 6

КОМБИНАТОРИКА 1. Общие правила комбинаторики На практике часто приходиться выбирать из некоторого множества объектов подмножество элементов, обладающих теми или иными свойствами, располагать элементы одного

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» ЛЕКЦИЯ ПО ТЕОРИИ

Практическая работа 15 Расчет количества выборок Цель работы: научиться определять количество выборок, используя правила комбинаторики и основные формулы. Содержание работы. Основные понятия. 1 Правило

С О Д Е Р Ж А Н И Е 1 ТЕМА II. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ... 2 1. СПРАВОЧНЫЕ МАТЕРИАЛЫ И ПРИМЕРЫ... 2 1.1. ПРИМЕРЫ... 2 2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ И ФОРМУЛЫ... 3 3. ПРАВИЛА КОМБИНАТОРИКИ... 4 4.

Тема 48 «Поочередный и одновременный выбор» Наука, изучающая способы составления и количество множеств и их подмножеств, называется комбинаторикой. Каждое конкретное подмножество, составленное из элементов

КОМБИНАТОРНЫЕ ЗАДАЧИ Вендина Алла Анатольевна Доцент кафедры математики и информатики Ставропольского государственного педагогического института Вендина А.А. Комбинаторные задачи. Задачи на выбор элементов

1) Имеется слово из 12 [неповторяющихся] букв. Сколькими способами можно переставить буквы в этом слове, чтобы получились всевозможные различные наборы букв? Поскольку все буквы различны, то n P12 12!

Урок 2.Размещения и сочетания Цели урока: образовательные: научить учащихся решать задачи с помощью формул сочетаний и размещений; различать комбинаторные соединения; научить решать задачи из жизни; воспитательные:

Комбинаторика Методы решения задач Румянцева ЛС Правило суммы Если конечные множества не пересекаются, то число элементов X U Y {или} равно сумме числа элементов множества X и числа элементов множества

{ определение правила равенства, суммы и произведения принцип включений исключений обобщение правила произведения общее правило произведения выборки перестановки и сочетания перестановки и сочетания с

Кафедра математики и информатики Математика Учебно-методический комплекс для студентов СПО, обучающихся с применением дистанционных технологий Модуль 6 Элементы теории вероятностей и математической статистики

Министерство образования Московской области Государственное бюджетное образовательное учреждение среднего профессионального образования Московской области «Балашихинский промышленно-экономический колледж»

И. В. Яковлев Материалы по математике MathUs.ru Комбинаторика. Правило произведения При решении комбинаторных задач часто приходится умножать число способов выбора одного объекта на число способов выбора

Теория вероятностей и математическая статистика Доктор физ.-мат. наук профессор Михаил Павлович Харламов «Страница» с методическими материалами http://inter.vags.ru/hmp Волгоградский филиал РАНХиГС (ФГОУ

С А Лавренченко ТЕОРИЯ ВЕРОЯТНОСТЕЙ «Три карты три карты три карты!» (Опера «Пиковая дама») Практическое занятие 1 11 Классическое определение вероятности 111 Простейшие задачи на классическое определение

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

Теория множеств и основы комбинаторики План лекции П.. Определение множества и подмножества... П.. Множества и отношения... П.. Операции над множествами... П. 4. Свойства операций над множествами... 4

Примеры комбинаторных задач и общие принципы комбинаторики Пример, навеянный сказкой Андерсена «Снежная королева». Помните, когда Герда нашла Кая в чертогах Снежной королевы, тот безуспешно складывал

ЗАНЯТИЕ 1 ЭЛЕМЕНТЫ КОМБИНАТОРИКИ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО МАТЕМАТИКЕ МИСИС 2013 УТВЕРЖДАЮ: Д.Е. Капуткин Председатель Учебно-методической комиссии по реализации Соглашения с Департаментом образования

Лекция 1 Элементы комбинаторики Комбинаторика это раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами

РЕШЕНИЕ ЗАДАЧ ПО ТЕОРИИ ВЕРОЯТНОСТЕЙ 1 В теории вероятностей часто приходится иметь дело с задачами, в которых необходимо подсчитывать число возможных способов совершения каких-либо действий. Задачи такого

4 Комбинаторика Перестановка это упорядоченный набор чисел 1 обычно трактуемый как биекция на множестве { 1 } которая числу i ставит в соответствие i-й элемент из набора Число при этом называется порядком

Пособие для учителей учреждений общего среднего образования Рекомендовано Научно-методическим учреждением «Национальный институт образования» Министерства образования Республики Беларусь М о з ы р ь «Белый

Пособие для учителей учреждений общего среднего образования Рекомендовано Научно-методическим учреждением «Национальный институт образования» Министерства образования Республики Беларусь М о з ы р ь 2

Тема 53 «Комбинированные задачи». Задачи, рассмотренные в данном разделе, обобщают сведения комбинаторики, статистики и теории вероятностей. Основные формулы комбинаторики. Без повторений С повторениями

Разработчик курса доцент кафедры высшей математики кандидат технических наук Некряч Е.Н. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ МНОЖЕСТВА И ОПЕРАЦИИ НАД НИМИ Такое понятие, как множество, вообще говоря, не определяется,

Теория вероятностей и математическая статистика Доктор физ.-мат. наук профессор Михаил Павлович Харламов Интернет-ресурс с методическими материалами http://www.vlgr.ranepa.ru/pp/hmp Волгоградский филиал

009-00 уч. год. 6, 0 кл. Математика. Элементы комбинаторики. Комбинаторикой (от латинского combinare соединять, сочетать) называют раздел математики, в котором изучаются задачи следующего типа: сколько

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ. Правило произведения. Если существует n вариантов выбора первого элемента и для каждого из них имеется m вариантов выбора второго элемента, то всего существует n m различных пар

Представляю разбор контрольных работ из сборника «Л.А. Александрова. Алгебра 9 класс. Контрольные работы» Иногда трудно самостоятельно разобраться со всеми заданиями, предлагаемыми на контрольных, особенно

НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им Н И ЛОБАЧЕВСКОГО Факультет вычислительной математики и кибернетики Кафедра математической логики и высшей алгебры ЭЛЕМЕНТЫ КОМБИНАТОРИКИ (Пособие для студентов

1 Основные понятия комбинаторики 1 Приложение Определение Произведение всех натуральных чисел от 1 до n включительно называют n-факториалом и пишут Пример Вычислить 4! 3! n! 1 3 n 4!-3!= 1 3 4 1 3 4 18

Задачи по теории вероятностей Н.М. Ефимова, учитель математики МБОУ «Гимназия» Теория вероятностей и математическая статистика занимаются построением и исследованием моделей различных ситуаций, связанных

Тема 49 «Формулы числа сочетаний. Бином Ньютона». Основные формулы комбинаторики. Без повторений С повторениями A = n! n k! A = n Порядок важен P = A = n! P = A = n Pk, k, k = (k + k + + k)! k! k! k!

1.1. Классическое определение вероятности Основным понятием теории вероятностей является понятие случайного события. Случайным событием называется событие, которое при осуществлении некоторых условий может

И. В. Яковлев Материалы по математике MathUs.ru Содержание Десятичная запись 1 Всероссийская олимпиада школьников по математике................ 1 2 Московская математическая олимпиада........................

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение дополнительного образования детей «Заочная физико-техническая школа Московского физико-технического

III ОСНОВЫ КОМБИНАТОРИКИ Общие правила комбинаторики Комбинаторика это раздел дискретной математики, который изучает способы подсчета числа элементов различных конечных множеств Многие правила комбинаторики

Математика (БкПл-100) М.П. Харламов 2011/2012 учебный год, 1-й семестр Лекция 5. Тема: Комбинаторика, введение в теорию вероятностей 1 Тема: Комбинаторика Комбинаторика это раздел математики, изучающий

Лекция 2: перечслительная комбинаторика Дискретная математика, ВШЭ, факультет компьютерных наук (Осень 2014 весна 2015) Задачи перечислительной кмбинаторики имеют типовой вид: «сколько способов сделать

ВЕРОЯТНОСТЬ СЛУЧАЙНОГО СОБЫТИЯ Аксиомы Колмогорова В 1933 г. А. Н. Колмогоров в книге «Основные понятия теории вероятностей» дал аксиоматическое обоснование теории вероятностей. «Это означает, что, после

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

Задачи и головоломки 1. Десятичная система счисления Десятичная система счисления является позиционной. В позиционных системах счисления вклад цифры в число зависит от положения этой цифры в записи числа.

Муниципальное автономное общеобразовательное учреждение «Лицей 38» города Белгорода Учебное занятие по теме: «Комбинаторное правило умножения» Учитель математики МАОУ «Лицей 38» г.белгорода Реуцкая Людмила

Достоверное событие. Событие называется достоверным, если оно обязательно произойдет при осуществлении определенной совокупности условий. Обозначение: Ω (истина). Невозможное событие. Событие, которое

ЛЕКЦИЯ 1 ТЕМА: ВИДЫ КОМБИНАТОРНЫХ ЗАДАЧ. ОСНОВНЫЕ ПРИНЦИПЫ КОМБИНАТОРИКИ. План 1. История комбинаторики 2. Некоторые задачи комбинаторики 3. Структура и методы 4. Примеры решения задач 1. История комбинаторики

В лекции использовались материалы из книги И.А. Лаврова ѕматематическая логикаї и из сборника Т.В. Андреевой ѕдискретная математика для социологовї. 1 Размещения n предметов по k ящикам, перестановки.

Лекция 1. Тема: ОСНОВНЫЕ ПОДХОДЫ К ОПРЕДЕЛЕНИЮ ВЕРОЯТНОСТИ Предмет теории вероятностей. Историческая справка Предметом теории вероятностей является изучение закономерностей, возникающих при массовых, однородных

Элементы комбинаторики профессор кафедры физико-математического образования ИПК и ПРО, дфмн Мищенко С.П. џ1. Декартово произведение множеств Элементарная комбинаторика связана с одним простым результатом

Заочный физико-математический лицей «Авангард» Е. Н. Филатов АЛГЕБРА 8 Экспериментальный учебник Часть 1 МОСКВА 2016 СОДЕРЖАНИЕ 1. Делимость. 2. Чёт нечет 3. Множества. 4. Забавные задачи. 5. Комбинаторика

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. Р.Е. Алексеева

1 Классическое определение вероятности 1 Колода из 3-х карт тщательно перетасована Найти вероятность того, что все четыре туза лежат в колоде один за другим, не перемежаясь другими картами Решение Число

Югорский физико-математический лицей В.П. Чуваков Делимость целых чисел в задачах Сборник задач Ханты-Мансийск 05 Делимость целых чисел в задачах: Сборник задач, - Ханты-Мансийск, Югорский физико-математический

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Ухтинский государственный технический университет (УГТУ) КОМБИНАТОРИКА Методические

Воробьев В.В. «Лицей» г.калачинска Омской области Практикум по решению задач по теории вероятностей и математической статистике Большую роль при изучении тем по теории вероятностей и статистики играют

ПРКТИКУМ Основные формулы комбинаторики Виды событий Действия над событиями Классическая вероятность Геометрическая вероятность Основные формулы комбинаторики Комбинаторика изучает количества комбинаций,

Комбинаторика ДИСКРЕТНАЯ МАТЕМАТИКА C. Элементы комбинаторики (в рамках теории множеств) Tallinn University of Technology Комбинаторика раздел математики, посвящённый решению задач выбора и расположения

Математика 6 класс Множества и комбинаторика блок содержания знать уметь п/п 1 Понятие множества. Понятие множества, описывать совокупности Виды множеств. подмножества, предметов или объектов, конечного,

Двоичное кодирование 1.3 Двоичное кодирование Ключевые слова: дискретизация алфавит мощность алфавита двоичный алфавит двоичное кодирование разрядность двоичного кода 1.3.1. Преобразование информации из