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

Элементы комбинаторики, правила суммы и произведения. Вывести формулы для числа сочетаний и размещений с повторением и без повтора 1. Правило суммы. Если некоторое действие α можно выполнить т способами, а действие β выполнить и способами, причём любой способ выполнения действия α отличен от любого способа выполнения действия Д то сложное действие « или α, или β » можно выполнить т + п способами. Это правило достаточно очевидно. Задачи, которые можно решить применением одного лишь правила суммы, чаще всего тривиальны. Обычно правило суммы ис­пользуют вместе с правилом произведения. 2. Правило умножения (произведения). Если некоторое действие α может быть выполнено т способами, а для каждого из этих способов некоторое другое действие β можно осуществить n способами, то сложное действие « и α, и β » можно осуществить т*п способами. Пусть опыт состоит в выборе т элементов из и различных элементов множест­ва X без возвращения и с упорядочиванием их в последовательную цепочку. Раз­личными исходами данного опыта будут упорядоченные m - элементные подмно­жества множества X, отличающиеся друг от друга либо набором элементов, либо порядком их следования. Получаемые при этом комбинации элементов (элементар­ные исходы) называются размещениями без повторений из п элементов по т. Чис­ло всех таких размещений из n элементов по т обозначается символом Аmn.На первом месте в упорядоченной цепоч­ке может оказаться любой из и элементов множества X. После того, как заполнено первое место, на втором месте может оказаться любой из оставшихся n - 1 элемен­тов и т.д. Пользуясь правилом произведения, находим Аmn =п(п-1)(п-2)...(п-т+1)= n!/(п-т)! В частном случае т=п опыт фактически состоит в произвольном упорядочи­вании множества X и сводится к случайной перестановке элементов всего множе­ства (т.е. перестановка п элементов это размещение из n элементов по n). Число всех перестановок и элементов обозначается символом Рn, при этом Pn= Аmn= п(п-1)(п-2)...2*1= n! Пусть опыт состоит в выборе т элементов из n различных элементов множест­ва X без возвращения и без упорядочивания. Различными исходами следует считать т - элементные подмножества множества X, отличающиеся друг от друга хотя бы одним элементом. Получаемые при этом комбинации элементов (элементарные исходы) называются сочетаниями без повторений из п элементов по т. Число всех таких сочетаний обозначается символом Сmn. Легко убедиться, что Сmn = Аmn /Pm =п(п-1)(п-2)...(п-т+1)/m!= п! /(n-m)!m! Пусть опыт состоит в выборе т элементов из множества X = {x1, ..., хn} с возвращением и с упорядочиванием их в последовательную цепочку. Различными исходами будут всевозможные т - элементные наборы (вообще говоря, с повторе­ниями), отличающиеся либо составом элементов, либо порядком их следования. Например, при т = 4 множества ω1= {x1, x2, x1, x1}, ω2 = {x1, x1, x2,x1}, ω3 = {x1, x1, x1, x2} являются различными исходами данного опыта. Получаемые в результате комбинации называются размещениями из п элементов по т с повто­рениями, а их общее число определяется с помощью правила умножения формулой =nm. Если опыт состоит в выборе с возращением т элементов множества X = {x1, ..., хn}, но без последующего упорядочивания, то различными исхо­дами такого опыта будут всевозможные т - элементные наборы, отличающиеся хотя бы одним элементом. Например, при т= 4 наборы {x1, x2, x1, x1} и {x1, x1, x2,x1} совпадают, а набор {x1, x3, x1, x1} отличен от любого из предыдущих. Получающиеся в результате данного опыта комбинации называются сочета­ниями с повторениями из п элементов по т, а их общее число определяется фор­мулой . Аксиоматическое определение вероятности, понятие сигмы-алгебры, сформулировать и доказать следствия из аксиом теории вероятности Понятие σ-алгебры. Привести примеры вероятностных пространств, классическая схема, дискретное вероятностное пространство, геометрическая вероятность, решить задачу Буффона Геометрическая вероятность – вероятность попадания точки в область (отрезок, часть плоскости и т.д.). Пусть отрезок l составляет часть отрезка L. На отрезке L наудачу поставлена точка. Если предположить, что вероятность попадания точки на отрезок l пропорциональна длине этого отрезка и не зависит от его расположения относительно отрезка L, то вероятность попадания точки на отрезок l определяется: P= длина l/ длина L. Определение пространства элементарных событий случайного опыта. Понятие случайного события, операции над событиями, привести примеры. Понятие условной вероятности, свойства условных вероятностей, понятие независимости событий, свойства независимых событий с доказательствами Условной вероятностью события при условии, что произошло событие , называется число Будем считать, что условная вероятность определена только в случае, когда . Следующее свойство называется "теоремой умножения": , если соответствующие условные вероятности определены (то есть если , ). Теорема умножения для большего числа событий: , если соответствующие условные вероятности определены. События и называются независимыми, если Если события и несовместны, то они независимы если и только если или . Если , то события и независимы . Если , то события и независимы . Лемма: Если события и независимы, то независимы и события и , и , и . Доказательство. Так как , и события и несовместны, то .Поэтому . События называются независимыми в совокупности, если для любого набора Если события независимы в совокупности, то они попарно независимы, то есть любые два события независимы. Вывести формулы полной вероятности и Байеса Набор попарно несовместных событий таких, что для всех и , называется полной группой событий или разбиением пространства . События , образующие полную группу событий, часто называют гипотезами. При подходящем выборе гипотез для произвольного события могут быть сравнительно просто вычислены (вероятность событию произойти при выполнении «гипотезы» ) и собственно (вероятность выполнения «гипотезы» формула полной вероятности. Пусть  —  полная группа событий. Тогда вероятность любого события может быть вычислена по формуле: Доказательство. Заметим, что , и события попарно несовместны. Поэтому (используем в первом равенстве -аддитивность вероятностной меры, а во втором — теорему умножения) формула Байеса: Пусть  —  полная группа событий и  —  некоторое событие положительной вероятности. Тогда условная вероятность того, что имело место событие , если в результате эксперимента наблюдалось событие , может быть вычислена по формуле: Доказательство. По определению условной вероятности, Последнее равенство следует из теоремы умножения и формулы полной вероятности. Последовательность независимых испытаний, вывести формулы Бернулли, полиномиальная схема испытаний. Схемой Бернулли называется последовательность независимых испытаний, в каждом из которых возможны лишь два исхода — «успех» и «неудача», при этом «успех» в одном испытании происходит с вероятностью , «неудача» — с вероятностью . формула Бернулли. Обозначим через число успехов в испытаниях схемы Бернулли. Тогда для любого Доказательство. Событие означает, что в испытаниях схемы Бернулли произошло ровно успехов. Рассмотрим один из благоприятствующих событию элементарных исходов: . Здесь буквами «у» и «н» обозначены, соответственно, успешный и неудачный результаты испытаний. Поскольку испытания независимы, вероятность такого элементарного исхода (первые испытаний завершились успехом, остальные неудачей) равна . Другие благоприятствующие событию элементарные исходы отличаются от рассмотренного выше лишь расположением успехов на местах. Есть ровно способов расположить успехов на местах. Поэтому событие состоит из элементарных исходов, вероятность каждого из которых равна Предельная теорема в схеме Бернулли, вывести формулы Пуассона, сформулировать локальные и интегральные схема Лапласа теорема Пуассона: Пусть , так, что . Тогда для любого вероятность получить успехов в испытаниях схемы Бернулли с вероятностью успеха стремится к величине Доказательство. Положим . при фиксированном и при . Тогда В ф-ле мы использовали свойства и . Докажем последнее свойство: Дать определение случайной величины, определение функции распределения, сформулировать и доказать свойства функции распределения Функция называется случайной величиной, если для любого множество элементарных исходов является событием, то есть принадлежит -алгебре событий . Функцией распределения случайной величины называется функция , при каждом равная Функция распределения обладает следующими свойствами: F1)  Функция распределения не убывает: ; F2)  Существуют пределы и . F3)  Функция распределения непрерывна слева: . Доказательство свойства (F1). Если , то . Поэтому . Q.D.E. Доказательство свойства (F2). Замечание 12. Если ряд, составленный из неотрицательных слагаемых , сходится, то есть существует , то «хвост» ряда стремится к нулю: . Замечание 13. Существование пределов в свойствах (F2), (F3) вытекает из монотонности и ограниченности функции . Так что остается доказать равенства , и . Замечание 14. Если существует , то для произвольной последовательности такой, что , имеет место равенство .   По замечанию 14, для доказательства достаточно доказать, что при . Представим событие (например) как счетное объединение событий: Используя -аддитивность вероятности, и помня, что , получим: и, по замечанию 12, Но и сходимость к нулю при доказана. По замечанию 14, для доказательства достаточно доказать, что при , или что . Представим событие (например :-)) как счетное объединение событий: В силу -аддитивности вероятности, и, по замечанию 12, Но и сходимость к единице при доказана. Доказательство свойства (F3). Согласно замечанию 14, достаточно доказать, что при . Или, что то же самое, доказать, что Представим событие как счетное объединение событий: В силу -аддитивности вероятности, поэтому снова Но , и эта вероятность, как мы только что видели, стремится к нулю с ростом . Тогда, по (12), при (непрерывность слева). F4)   В любой точке   разница   равна  : или, иначе, F5)   Для любой случайной величины имеет место равенство . Если же функция распределения   непрерывна (для любого , или только в точках и ), то Доказательство. Доказывать нужно только равенство , поскольку все остальные равенства следуют из него с учетом следствия 4. Напомню, что этим равенством мы уже много раз пользовались, доказывая свойства (F2), (F3). Заметим, что , и первые два события несовместны. Поэтому или , что и требовалось доказать. Свойство 6. Случайная величина имеет дискретное распределение тогда и только тогда, когда функция распределения  —  ступенчатая функция. При этом возможные значения  —  точки скачков , и  —  величины скачков Дискретная случайная величина, ряд распределения. Вывести законы распределения для геометрического и гипергеометрического распределений, биномиальное распределение и распределение Пуассона Говорят, что случайная величина имеет дискретное распределение, если существует конечный или счетный набор чисел такой, что: а) для всех ; б) . То есть случайная величина имеет дискретное распределение, если она принимает не более чем счетное число значений. Геометрическое распределение. Говорят, что случайная величина имеет геометрическое распределение с параметром , где , и пишут , если принимает значения с вероятностями . Случайная величина с таким распределением имеет смысл номера первого успешного испытания в схеме Бернулли с вероятностью успеха  . Таблица распределения имеет вид    1   2   ...      ...   ...   ...    Распределение Пуассона. Говорят, что случайная величина имеет распределение Пуассона с параметром , где , и пишут , если принимает значения с вероятностями . Таблица распределения имеет вид    0   1   ...      ...   ...   ...    Гипергеометрическое распределение. Говорят, что случайная величина имеет гипергеометрическое распределение с параметрами , и , где , , если принимает целые значения от до с вероятностями . Случайная величина с таким распределением имеет смысл числа белых шаров среди шаров, выбранных наудачу и без возвращения из урны, содержащей белых шаров и не белых. Непрерывные случайные величины. Функция плотности и ее свойства с доказательствами (нормальное, показательное и равномерное распределения) Случайная величина имеет абсолютно непрерывное распределение, если существует неотрицательная функция такая, что для любого функция распределения представима в виде При этом функция называется плотностью распределения случайной величины . Теорема 20. Плотность распределения обладает свойствами: (f1)   для любого ; (f2)    . Доказательство. (f1) выполнено по определению плотности. Докажем (f2). по свойству (F2) функций распределения. Q.D.E. Эти два свойства полностью характеризуют класс плотностей: Лемма 3. Если функция обладает свойствами (f1) и (f2), то существует вероятностное пространство и случайная величина на нем, для которой является плотностью распределения. Доказательство. Пусть есть область, заключенная между осью абсцисс и графиком функции («подграфик» функции ). Площадь области равна 1 по свойству (f2). И пусть случайная величина есть абсцисса точки, наудачу брошенной в эту область. Тогда (вспомнить геометрическую вероятность) для любого   то есть является плотностью распределения случайной величины . Q.D.E.

Похожие:

	Вопросы к экзамену по курсу «Высшая математика часть 2» Элементы теории соединений. Размещения без повторений. Две формулы для подсчёта числа размещений		Элементы комбинаторного анализа Одной из основных задач комбинаторного анализа (комбинаторики) является подсчет числа элементов конечных множеств, заданных каким-либо...
	Ф ормула суммы Цели урока: вывести формулу суммы первых членов арифметической прогрессии; рассмотреть задания с применением этой формулы; рассмотреть...		Комбинаторика и комбинаторные алгоритмы Предварительные понятия и принципы комбинаторики. Принципы перечисления Числа Белла. Числа Стирлинга Подстановки и их перечисление....
	Формула суммы n-первых членов Цель: вывести вместе с учащимися формулы суммы n-первых членов арифметической прогрессии; сформировать навыки использования этих...		Программа элективного курса Элементы теории графов и комбинаторики Учитель Курс “Элементы теории графов и комбинаторики” является дополнительным к стандартному курсу математики 5 класса для образовательных...
	Программа курса "дискретная математика" Дискретные множества. Характеристический век­тор множества и операции над множествами. Мощность прямого произведения множеств. Число...		* в формуле 40) дадут перечисление неупорядоченных к -выборок без повторений, т е. сочетаний без повторений из Если заменить числа на объекты, то коэффициенты при в формуле 40 дадут перечисление неупорядоченных к -выборок без повторений, т...
	Элементы комбинаторики. Перестановки Сколько чисел можно составить из цифр 1, 2, 3, 4 (без их повторения), таких, которые больше 3000		Технологическая карта Изучить понятие геометричес-кой прогрессии; вывести формулы n-го члена и суммы n-первых членов геометричес-кой прогрессии