Сочетания и размещения формулы – . : , ,

Основные формулы комбинаторики: размещения, перестановки, сочетания.

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

Формула размещения:

 

Пусть имеются три буквы А, В и С. Составим всевозможные комбинации только из двух букв: АВ, ВА, АС, СА, ВС, СВ. Эти комбинации отличаются друг от друга только расположением букв или самими буквами. 

Пример 1

На третьем курсе изучается 9 предметов. Сколькими способами можно составить расписание занятий на один день, если в учебный день разрешается проводить занятия только по четырем разным предметам? 

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

 Ответ: 3024

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

Формула перестановки:      Р_n=n!

Пусть имеются три буквы А, В и С. Составим всевозможные комбинации из этих букв: ABC, АСВ, ВСА, ВАС, CAB, CBA. Эти комбинации отличаются друг от друга только расположением букв. 

Пример 1

 В турнире участвуют семь команд. Сколько вариантов распределения мест между ними возможно? 

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

Р₇=7!=1*2*3*4*5*6*7=5040

Ответ: 5040

  Комбинации из n элементов по m элементам, которые отличаются друг от друга хотя бы одним элементом, называются сочетаниями.

Формула сочетания:

 

Пусть имеются три буквы А, В и С. Составим всевозможные комбинации только из двух букв, которые отличаются друг от друга хотя бы одним элементом: АВ, АС, ВС. Нетрудно увидеть, что их в два раза меньше, чем размещений из этих элементов.  Пример 1

  Сколькими способами можно распределить три путевки в один санаторий между пятью желающими? 

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

2. Виды случайных событий.

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

Виды событий:

• Элементарные события — возможно исключающие друг друга события опыта.

• Невозможное событие — не может произойти в результате опыта.

• Достоверное событие – в результате опыта обязательно произойдет.

• Случайное событие – при осуществлении некоторых условий может произойти или не произойти.

• Несовместные события – появление одного из них исключает появление других событий в одном и том же испытании.

• Совместные события – в результате опыта могут появиться одновременно.

• Равновозможные события – одинакова возможность появления в результате опыта.

• Равносильные события – событие А влечет за собой событие В, а событие В влечет за собой событие А.

3. Алгебра событий.

• Суммой (объединением) событий А и В называется событие С, состоящее в появлении события А или событие В или одновременно событий А и В.

  С=А+В

• Произведением (пересечением) событий А и В называется событие С, состоящее в совместном появлении событий А и В. С=А*В

• Разностью событий А и В называется событие С, состоящее в появлении событии А и не появлении события В. С=А-В

4. Классическое определение вероятности события. Свойства вероятности.

Вероятностью р события А называется отношение числа m-благоприятствующих случаев к числу всех возможных случаев n, образующих полную группу равновозможных несовместимых событий:

P (A)=

Свойства вероятности:

1. Число появления m-любого события входит в интервал 0<P<1.

2. Вероятность достоверного события равна 1.

3. Вероятность невозможного события равна 0.

5. Теоремы сложения вероятностей несовместных событий.

Теорема 1. Вероятность появления одного из двух несовместных событий, безразлично какого, равна сумме вероятностей этих событий:

Р (А + В) = Р (А) + Р (В).

Доказательство: Введем обозначения: n — общее число возможных элементарных исходов испытания; m₁ — число исходов, благоприятствующих событию A; m₂— число исходов, благоприятствующих событию В.

Число элементарных исходов, благоприятствующих наступлению либо события А, либо события В, равно m₁ + m₂. Следовательно,

Р (A + В) = (m₁ + m₂) / n = m₁ / n + m₂ / n.

Приняв во внимание, что m₁ / n = Р (А) и m₂ / n = Р (В), окончательно получим

Р (А + В) = Р (А) + Р (В).

Теорема 2. Сумма вероятностей событий А

1 , А₂ , …, А_n , образующих полную группу, равна единице:

Р (A₁) + Р (А₂) + … + Р (А_n) = 1.

Доказательство: Так как появление одного из событий полной группы достоверно, а вероятность достоверного события равна единице, то

Р (A₁ + A₂ + … + A_n) = 1.     (*)

Любые два события полной группы несовместны, поэтому можно применить теорему сложения:

Р (А₁ + А₂ + … + А_n) = Р (A₁) + Р (A₂) + … + Р (А_n).    (**)

Сравнивая (*) и (**), получим

Р (А₁) + Р (А₂) + … + Р (А_n) = 1.

Пример: Консультационный пункт института получает пакеты с контрольными работами из городов А, В и С. Вероятность получения пакета из города А равна 0,7, из города В — 0,2. Найти вероятность того, что очередной пакет будет получен из города С.

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

0,7 + 0,2 + p =1.

Отсюда искомая вероятность

р = 1 — 0,9 = 0,1.

Теорема 3. Сумма вероятностей противоположных событий равна единице:

.

Доказательство: Пусть дано А и . Тогда А+ будет достоверным. Сумма достоверного события равно 1. Тогда

.

З а м е ч а н и е 1. Если вероятность одного из двух противоположных событий обозначена через р, то вероятность другого события обозначают через q. Таким образом, в силу предыдущей теоремы

p + q = l

З а м е ч а н и е 2. При решении задач на отыскание вероятности события А часто выгодно сначала вычислить вероятность противоположного события, а затем найти искомую вероятность по формуле

.

studfiles.net

Сочетания и размещения

Вопросы занятия:

• вывести формулу числа сочетаний из n элементов по k;

• вывести формулу числа размещений из n элементов по k;

• познакомить с треугольником Паскаля и с закономерностью получения его чисел.

Материал урока

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

Так же мы активно применяли правило умножения.

Из курса алгебры 9 класса вам известны понятие факториал и теорема о перестановках.

Вспомним их.

Определение.

Произведение подряд идущих первых n натуральных чисел называют n факториал.

Теорема 1.

Решим задачу.

Школьники смастерили 4 скворечника.

Сколькими способами в них могут разместиться 4 скворца?

Решение заключается в том, чтобы найти число перестановок из четырёх элементов.

Сколькими же способами в них могут разместиться 4 скворца, если один прилетела раньше всех и уже занял себе домик?

Понятно, что остаётся разместить оставшиеся 3 птицы в 3 домика.

А теперь представим себе такую ситуацию. Каждые 2 из 7 городов соединены мостами. Определим их количество.

Представим города в виде точек. Каждый мост соединяет только 2 города.

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

Запишем теорему о выборе двух элементов.

Теорема 2.

Определение.

Тогда теорему 2 кратко можно записать в виде формулы.

Решим задачу.

Рассмотрим другую ситуацию.

Пример.

Теорема 3.

Определение.

Тогда теорему можно записать так:

Решим задачу.

Запишем определения.

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

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

n элементов по k.

Как же находить число сочетаний и размещений из n элементов по k?

Запишем теорему.

Теорема 4.

Для любых натуральных чисел n и k, таких, что k < n, справедливы следующие соотношения.

Этими формулами мы и будем пользоваться при вычислении числа сочетаний и размещений.

Решим уравнение.

Так мы с помощью изученных формул решили уравнение, а теперь решим задачу.

Пример.

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

Он выглядит так.

Закономерность образования строк заключается в следующем: каждое число в треугольнике Паскаля равно сумме двух чисел, стоящих над ним в предыдущей строке. 5=1+4, 10=4+6, 6=3+3 и так далее.

Кратко эту закономерность можно записать в виде такой формулы.

Подведём итоги нашего урока.

Сегодня мы рассмотрели такие инструменты комбинаторики как сочетание и размещение.

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

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

videouroki.net

Основные формулы комбинаторики. Комбинаторика: формула перестановки, размещения

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

Итак, что же это за раздел? Комбинаторика занимается вопросом подсчета каких-либо объектов. Но в данном случае объектами выступают не сливы, груши или яблоки, а нечто иное. Комбинаторика помогает нам находить вероятность какого-либо события. Например, при игре в карты – какова вероятность того, что у противника есть козырная карта? Или такой пример – какова вероятность того, что из мешка с двадцатью шариками вы достанете именно белый? Именно для подобного рода задач нам и нужно знать хотя бы основы данного раздела математики.

Комбинаторные конфигурации

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

• размещение;
• перестановка;
• сочетание;
• композиция числа;
• разбиение числа.

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

Разделы

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

• перечислительная;
• структурная;
• экстремальная;
• теория Рамсея;
• вероятностная;
• топологическая;
• инфинитарная.

В первом случае речь идет об исчисляющей комбинаторике, задачи рассматривают перечисление или подсчет разных конфигураций, которые образованы элементами множеств. На данные множества, как правило, накладываются какие-либо ограничения (различимость, неразличимость, возможность повтора и так далее). А количество этих конфигураций подсчитывается при помощи правила сложения или умножения, о которых мы поговорим немного позже. К структурной комбинаторике относятся теории графов и матроидов. Пример задачи экстремальной комбинаторики – какова наибольшая размерность графа, который удовлетворяет следующим свойствам… В четвертом пункте мы упомянули теорию Рамсея, которая изучает в случайных конфигурациях наличие регулярных структур. Вероятностная комбинаторика способна нам ответить на вопрос – какова вероятность того, что у заданного множества присутствует определенное свойство. Как нетрудно догадаться, топологическая комбинаторика применяет методы в топологии. И, наконец, седьмой пункт – инфинитарная комбинаторика изучает применение методов комбинаторики к бесконечным множествам.

Правило сложения

Среди формул комбинаторики можно найти и довольно простые, с которыми мы достаточно давно знакомы. Примером является правило суммы. Предположим, что нам даны два действия (С и Е), если они взаимоисключаемы, действие С выполнимо несколькими способами (например а), а действие Е выполнимо b-способами, то выполнить любое из них (С или Е) можно а+b способами.

В теории это понять достаточно трудно, постараемся донести всю суть на простом примере. Возьмем среднюю численность учеников одного класса — допустим, это двадцать пять. Среди них пятнадцать девочек и десять мальчиков. Ежедневно в классе назначается один дежурный. Сколько есть способов назначить дежурного по классу сегодня? Решение задачи достаточно простое, мы прибегнем к правилу сложения. В тексте задачи не сказано, что дежурными могут быть только мальчики или только девочки. Следовательно, им может оказаться любая из пятнадцати девочек или любой из десяти мальчиков. Применяя правило суммы, мы получаем достаточно простой пример, с которым без труда справится школьник начальных классов: 15 + 10. Подсчитав, получаем ответ: двадцать пять. То есть существует всего двадцать пять способов назначить на сегодня дежурного класса.

Правило умножения

К основным формулам комбинаторики относится и правило умножения. Начнем с теории. Допустим, нам необходимо выполнить несколько действий (а): первое действие выполняется с1 способами, второе – с2 способами, третье – с3 способами и так далее до последнего а-действия, выполняемого са способами. Тогда все эти действия (которых всего у нас а) могут быть выполнены N способами. Как высчитать неизвестную N? В этом нам поможет формула: N = с1 * с2 * с3 *…* са.

Опять же, в теории ничего не понятно, переходим к рассмотрению простого примера на применение правила умножения. Возьмем все тот же класс из двадцати пяти человек, в котором учится пятнадцать девочек и десять мальчиков. Только на этот раз нам необходимо выбрать двух дежурных. Ими могут быть как только мальчики или девочки, так и мальчик с девочкой. Переходим к элементарному решению задачи. Выбираем первого дежурного, как мы решили в прошлом пункте, у нас получается двадцать пять возможных вариантов. Вторым дежурным может быть любой из оставшихся человек. У нас было двадцать пять учеников, одного мы выбрали, значит вторым дежурным может быть любой из оставшихся двадцати четырех человек. Наконец, применяем правило умножения и получаем, что двоих дежурных можно избрать шестью сотнями способов. Мы данное число получили умножением двадцати пяти и двадцати четырех.

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

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

Начнем, если у нас нет шаров, то и вариантов расстановки у нас так же ноль. А если у нас шар один, то и расстановка тоже одна (математически это можно записать следующим образом: Р1 = 1). Два шара можно расставить двумя разными способами: 1,2 и 2,1. Следовательно, Р2 = 2. Три шара можно расставить уже шестью способами (Р3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. А если таких шаров не три, а десять или пятнадцать? Перечислять все возможные варианты очень долго, тогда нам на помощь приходит комбинаторика. Формула перестановки поможет нам найти ответ на интересующий нас вопрос. Pn = n *P (n-1). Если попытаться упростить формулу, то получаем: Pn = n* (n — 1) *…* 2 * 1. А это и есть произведение первых натуральных чисел. Такое число называется факториалом, а обозначается как n!

Рассмотрим задачу. Вожатый каждое утро выстраивает свой отряд в шеренгу (двадцать человек). В отряде есть три лучших друга – Костя, Саша и Леша. Какова вероятность того, что они будут стоять рядом? Чтобы найти ответ на вопрос, нужно вероятность «хорошего» исхода поделить на общее количество исходов. Общее число перестановок составляет 20! = 2,5 квинтиллиона. Как посчитать количество «хороших» исходов? Предположим, что Костя, Саши и Леша – это один сверхчеловек. Тогда мы имеем всего восемнадцать субъектов. Число перестановок в данном случае равняется 18 = 6,5 квадриллионов. При всем этом, Костя, Саша и Леша могут произвольно перемещаться между собой в своей неделимой тройке, а это еще 3! = 6 вариантов. Значит всего «хороших» расстановок у нас 18! * 3! Нам остается только найти искомую вероятность: (18! * 3!) / 20! Что равняется примерно 0,016. Если перевести в проценты, то это получается всего 1,6%.

Размещение

Сейчас мы рассмотрим еще одну очень важную и необходимую формулу комбинаторики. Размещение – это наш следующий вопрос, который предлагаем вам рассмотреть в данном разделе статьи. Мы идем на усложнение. Предположим, что мы хотим рассмотреть возможные перестановки, только не из всего множества (n), а из меньшего (m). То есть мы рассматриваем перестановки из n предметов по m.

Основные формулы комбинаторики стоит не просто заучивать, а понимать их. Даже несмотря на то, что они усложняются, так как у нас не один параметр, а два. Предположим, что m = 1, то и А = 1, m = 2, то А = n * (n — 1). Если далее упрощать формулу и перейти на запись при помощи факториалов, то получится вполне лаконичная формула: А = n! / (n — m)!

Сочетание

Мы рассмотрели практически все основные формулы комбинаторики с примерами. Теперь перейдем к заключительному этапу рассмотрения базового курса комбинаторики – знакомство с сочетанием. Сейчас мы будем выбирать m предметов из имеющихся у нас n, при этом всем мы будем выбирать всеми возможными способами. Чем же тогда это отличается от размещения? Мы не будем учитывать порядок. Этот неупорядоченный набор и будет являться сочетанием.

Сразу введем обозначение: С. Берем размещения m шариков из n. Мы перестаем обращать внимание на порядок и получаем повторяющиеся сочетания. Чтобы получить число сочетаний нам надо поделить число размещений на m! (m факториал). То есть С = А / m! Таким образом, способов выбрать из n шаров немножко, равняется примерно столько, сколько выбрать почти все. Этому есть логическое выражение: выбрать немножко все равно, что выкинуть почти все. Еще в данном пункте важно упомянуть и то, что максимальное число сочетаний можно достигнуть при попытке выбрать половину предметов.

Как выбрать формулу для решения задачи?

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

1. Задайте себе вопрос: порядок размещения элементов учитывается в тексте задачи?
2. Если ответ нет, то воспользуйтесь формулой сочетания (С = n! / (m! * (n — m)!)).
3. Если ответ нет, то необходимо ответить на еще один вопрос: все ли элементы входят в комбинацию?
4. Если ответ да, то воспользуйтесь формулой перестановки (Р = n!).
5. Если ответ нет, то воспользуйтесь формулой размещения (А = n! / (n — m)!).

Пример

Мы рассмотрели элементы комбинаторики, формулы и некоторые другие вопросы. Теперь перейдем к рассмотрению реальной задачи. Представьте, что перед вами лежат киви, апельсин и банан.

Вопрос первый: сколькими способами их можно переставить? Для этого воспользуемся формулой перестановок: Р = 3! = 6 способов.

Вопрос второй: сколькими способами можно выбрать один фрукт? Это очевидно, у нас всего три варианта – выбрать киви, апельсин или банан, но применим формулу сочетаний: С = 3! / (2! * 1!) = 3.

Вопрос третий: сколькими способами можно выбрать два фрукта? Какие есть у нас вообще варианты? Киви и апельсин; киви и банан; апельсин и банан. То есть три варианта, но это легко проверить при помощи формулы сочетания: С = 3! / (1! * 2!) = 3

Вопрос четвертый: сколькими способами можно выбрать три фрукта? Как видно, выбрать три фрукта можно одним-единственным способом: взять киви, апельсин и банан. С = 3! / (0! * 3!) = 1.

Вопрос пятый: сколькими способами можно выбрать хотя бы один фрукт? Это условие подразумевает, что мы можем взять один, два или все три фрукта. Следовательно, мы складываем С1 + С2 + С3 =3 + 3 + 1 = 7. То есть у нас есть семь способов взять со стола хотя бы один фрукт.

fb.ru