Реферат: Комбинаторика
План:
Предмет комбинаторики. 2
Краткая историческая справка. 4
Основные комбинаторные задачи. 5
Основные формулы комбинаторики_ 7
Правило суммы. 7
Правило произведения. 9
Предмет комбинаторики.
Наблюдаемые нами события(явления) можно подразделить на следующие три вида: достоверные, невозможные ислучайные.
Достоверным называютсобытие, которое обязательно произойдет, если будет осуществлена определеннаясовокупность условий S. Например, если в сосуде содержится вода при нормальноматмосферном давлении и температуре 20°, то событие «вода в сосуде находится вжидком состоянии» есть достоверное. В этом примере заданные атмосферноедавление и температура воды составляют совокупность условий S.
Невозможным называютсобытие, которое заведомо не произойдет, если будет осуществлена совокупностьусловий S. Например, событие «вода в сосуде находится в твердом состоянии»заведомо не произойдет, если будет осуществлена совокупность условийпредыдущего примера.
Случайным называютсобытие, которое при осуществлении совокупности условий S может либо произойти,либо не произойти. Например, если брошена монета, то она может упасть так, чтосверху будет либо герб, либо надпись. Поэтому событие «при бросании монетывыпал «герб» — случайное. Каждое случайное событие, в частности выпадение«герба», есть следствие действия очень многих случайных причин (в нашемпримере: сила, с которой брошена монета, форма монеты и многие другие).Невозможно учесть влияние на результат всех этих причин, поскольку число ихочень велико и законы их действия неизвестны. Поэтому теория вероятностей неставит перед собой задачу предсказать, произойдет единичное событие или нет, —она просто не в силах это сделать.
По-иному обстоит дело, еслирассматриваются случайные события, которые могут многократно наблюдаться приосуществлении одних и тех же условий S, т. е. если речь идет о массовыходнородных случайных событиях. Оказывается, что достаточно большое числооднородных случайных событий независимо от их конкретной природы подчиняетсяопределенным закономерностям, а именно вероятностным закономерностям.Установлением этих закономерностей и занимается теория вероятностей.
Итак, предметом теориивероятностей является изучение вероятностных закономерностей массовыходнородных случайных событий.
Знание закономерностей, которымподчиняются массовые случайные события, позволяет предвидеть, как эти событиябудут протекать. Например, хотя, как было уже сказано, нельзя напередопределить результат одного бросания монеты, но можно предсказать, причем снебольшой погрешностью, число появлений «герба», если монета будет брошенадостаточно большое число раз. При этом предполагается, конечно, что монетубросают в одних и тех же условиях.
Методы теории вероятностей широкоприменяются в различных отраслях естествознания и техники: в теории надежности,теории массового обслуживания, в теоретической физике, геодезии, астрономии,теории стрельбы, теории ошибок наблюдений, теории автоматического управления,общей теории связи и во многих других теоретических и прикладных науках. Теориявероятностей служит также для обоснования математической и прикладнойстатистики, которая в свою очередь используется при планировании и организациипроизводства, при анализе технологических процессов, предупредительном иприемочном контроле качества продукции и для многих других целей.
В последние годы методы теориивероятностей все шире и шире проникают в различные области науки и техники,способствуя их прогрессу.
Краткая историческаясправка.
Первые работы, в которыхзарождались основные понятия теории вероятностей, представляли собой попыткисоздания теории азартных игр (Кардано, Гюйгенс, Паскаль, Ферма и другие вXVI—XVII вв.).
Следующий этап развития теориивероятностей связан с именем Якоба Бернулли (1654—1705). Доказанная им теорема,получившая впоследствии название «Закона больших чисел», была первымтеоретическим обоснованием накопленных ранее фактов.
Дальнейшими успехами теориявероятностей обязана Муавру, Лапласу, Гауссу, Пуассону и др.
Новый, наиболее плодотворныйпериод связан с именами П. Л. Чебышева (1821—1894) и его учениковА.А.Маркова(1856—1922) и А. М.Ляпунова (1857—1918). В этот период теориявероятностей становится стройной математической наукой. Ее последующее развитиеобязано в первую очередь русским и советским математикам (С. Н. Бернштейн, В.И. Романовский, А. Н. Колмогоров, А. Я. Хинчин, Б. В. Гнеденко, Н. В. Смирнов идр.). В настоящее время ведущая роль в создании новых ветвей теориивероятностей также принадлежит советским математикам.
Основные комбинаторныезадачи.
Основными и типичными операциямии связанными с ними задачами комбинаторики являются следующие:
1) образованиеупорядоченных множеств, состоящее в установлении определенного порядкаследования элементов множества друг за другом, — составление перестановок;
2) образованиеподмножеств, состоящее в выделении из данного множества некоторой части егоэлементов, — составление сочетаний;
3) образованиеупорядоченных подмножеств — составление размещений.
ТИПЫ КОМБИНАТОРНЫХ ЗАДАЧ.
1. Магическийквадрат — квадратная таблица (n * n) целых чисел от 1 до n¤ такая, чтосуммы чисел вдоль любого столбца, любой строки и двух диагоналей таблицы равныодному и тому же числу s=n(n¤+1)/2. Число n называют порядом магическогоквадрата.
Доказано, что магический квадратможно построить для любого n Є 3. Уже в средние века был известен алгоритмпостроения магических квадратов нечетного порядка. Существуют магическиеквадраты, удоволетворяющие ряду дополнительных условий, например магическийквадрат с n=8, который можно разделить на четыре меньших магических квадрата4x4. В Индии и некоторых других странах магические квадраты употреблялись какталисманы. Однако общей теории магических квадратов не существует. Неизвестнодаже общее число магических квадратов порядка n.
2. Латинскийквадрат — квадратная матрица порядка n, каждая строка и каждый столбецкоторой являются перестановками элементов конечного множества S, состоящего изn элементов.
3. Задачаразмещения — одна из классических комбинаторных задач, в которойтребуется определить число способов размещения m различных предметов в nразличных ячейках с заданным числом r пустых ячеек. Это число равно
r n-r m
C (r)=Cдельта O, r=0,1,2,...,n,
nm n
где
k m k j j m
дельта O=сигма (-1) C (k-j)
j=0 k
4. Задачакоммивояжера, задача о бродячем торговце – комбинаторная задача теорииграфов. В простейшем случае формулируется следующим образом: даны n городов иизвестно расстояние между каждыми двумя городами; коммивояжер, выходящий изкакого-нибудь города, должен посетить n-1 других городов и вернуться висходный. В каком порядке должен он посещать города (по одному разу каждый)чтобы общее пройденное расстояние было минимальным?
Методы решения задачикоммивояжера, по существу, сводятся к организации полного перебора вариантов.
МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХЗАДАЧ
1. Методрекуррентных соотношений.
Метод рекуррентных соотношенийсостоит в том, что решение комбинаторной задачи с n предметами выражается черезрешение аналогичной задачи с меньшим числом предметов с помощью некоторогосоотношения, которое называется рекуррентным. Пользуясь этим соотношением,искомую величину можно вычислить, исходя из того, что для небольшого количествапредметов решение задачи легко находится.
2. Методвключения и исключения.
Пусть N(A) — число элементовмножества A. Тогда методом математической индукции можно доказать, что
N(A1U A2 U… An) = N(A1) +… + N(An) -
— {N(A1 П A2) +… + N(An-1 ПAn)} +
+{N(A1 П A2 П A3) +… + N(An-2П An-1 П An)} — ...
…+(-1)^n-1*N(A1 П A2 П… П An-1 П An).
Метод подсчета числа элементовобъединения множеств по этой формуле, состоящий в поочередном сложении ивычитании, называется методом включения и исключения.
3. Методтраекторий.
Для многих комбинаторных задачможно указать такую геометрическую интерпретацию, которая сводит задачу кподсчету числа путей (траекторий), обладающих определенным свойством.
Основные формулыкомбинаторики
Комбинаторика изучает количествакомбинаций, подчиненных определенным условиям, которые можно составить изэлементов, безразлично какой природы, заданного конечного множества. Принепосредственном вычислении вероятностей часто используют формулы комбинаторики.Приведем наиболее употребительные из них.
Перестановками называюткомбинации, состоящие из одних и тех же n различных элементов и отличающиесятолько порядком их расположения. Число всех возможных перестановок
Pn = n!,
где n! = 1 * 2 * 3… n.
Заметим, что удобно рассматривать0!, полагая, по определению, 0! = 1.
Размещениями называюткомбинации, составленные из n различных элементов по m элементов, которыеотличаются либо составом элементов, либо их порядком. Число всех возможныхразмещений
Amn = n (n — 1)(n — 2)…(n — m + 1).
Сочетаниями называюткомбинации, составленные из n различных элементов по m элементов, которыеотличаются хотя бы одним элементом. Число сочетаний
С mn = n! /(m! (n — m)!).
примеры перестановок, размещений,сочетаний
Подчеркнем, что числа размещений,перестановок и сочетаний связаны равенством
Amn = PmC mn.
За м е ч а н и е. Выше предполагалось, что все n элементов различны. Если женекоторые элементы повторяются, то в этом случае комбинации с повторениямивычисляют по другим формулам. Например, если среди n элементов есть n1элементов одного вида, n2 элементов другого вида и т.д., то числоперестановок с повторениями
Pn (n1, n2, ...) = n!/ (n1! n2!… ),
гдеn1 + n2 +… = n.
При решении задач комбинаторикииспользуют следующие правила:
Правило суммы.Если некоторый объект А можетбыть выбран из совокупности объектов m способами, а другой объект В может бытьвыбран n способами, то выбрать либо А, либо В можно m + n способами.
Суммой А + В двухсобытий А и В называют событие, состоящее в появлении события А, илисобытия В, или обоих этих событий. Например, если из орудия произведены двавыстрела и А — попадание при первом выстреле, В — попадание при второмвыстреле, то А + В — попадание при первом выстреле, или при втором, или в обоихвыстрелах.
В частности, если два события А иB — несовместные, то А + В — событие, состоящее в появлении одного из этихсобытий, безразлично какого.
Суммой нескольких событий называютсобытие, которое состоит в появлении хотя бы одного из этих событий. Например,событие А + В + С состоит в появлении одного из следующих событий: А, В, С, А иВ, А и С, В и С, А и В и С.
Пусть события A и В —несовместные, причем вероятности этих событий известны. Как найти вероятностьтого, что наступит либо событие A, либо событие В? Ответ на этот вопрос даеттеорема сложения.
Теорема. Вероятностьпоявления одного из двух несовместных событий, безразлично какого, равна суммевероятностей этих событий:
Р (А + В) = Р (А) + Р (В).
Доказательство:
Введем обозначения: n — общеечисло возможных элементарных исходов испытания; m1 — число исходов, благоприятствующих событию A; m2— число исходов, благоприятствующихсобытию В.
Число элементарных исходов, благоприятствующихнаступлению либо события А, либо события В, равно m1 + m2.Следовательно,
Р (A + В) = (m1 + m2)/ n = m1 / n + m2 / n.
Приняв во внимание, что m1 / n = Р (А) и m2 / n = Р (В), окончательно получим
Р (А + В) = Р (А) + Р (В).
С л е д с т в и е. Вероятностьпоявления одного из нескольких попарно несовместных событий, безразличнокакого, равна сумме вероятностей этих событий:
Р (A1 + A2 +… + An) = Р (A1) + Р (A2) +… + Р (An).
Доказательство:
Рассмотрим три события: А, В и С.Так как рассматриваемые события попарно несовместны, то появление одного изтрех событий, А, В и С, равносильно наступлению одного из двух событий, A + В иС, поэтому в силу указанной теоремы
Р ( А + В + С) = Р [(А + В) + С]= Р (А + В) + Р (С) = Р (А) + Р (В) + Р (С).
Для произвольного числа попарнонесовместных событий доказательство проводится методом математической индукции.
Полная группа событий.
Теорема Суммавероятностей событий А1,А2, ..., Аn, образующих полную группу, равнаединице:
Р(A1) + Р (А2) +… + Р (Аn) = 1.
Доказательство:
Так как появление одного изсобытий полной группы достоверно, а вероятность достоверного события равнаединице, то
Р (A1 + A2 +… +An) = 1. (*)
Любые два события полной группынесовместны, поэтому можно применить теорему сложения:
Р (А1 + А2 +… + Аn) = Р (A1) + Р (A2) +… + Р (Аn). (**)
Сравнивая (*) и (**), получим
Р (А1) + Р (А2)+… + Р (Аn) = 1.
Противоположные события.
Противоположными называютдва единственно возможных события, образующих полную группу. Если одно из двухпротивоположных событий обозначено через A, то другое принято обозначать
/>
Теорема. Суммавероятностей противоположных событий равна единице:
/>.
Доказательство базируется на том,что противоположные события образуют полную группу, а сумма вероятностейсобытий, образующих полную группу, равна единице (см. Теорему о полной группесобытий).
За м е ч а н и е 1. Если вероятность одного из двух противоположных событийобозначена через р, то вероятность другого события обозначают через q. Такимобразом, в силу предыдущей теоремы
p+ q = l
За м е ч а н и е 2. При решении задач на отыскание вероятности события А частовыгодно сначала вычислить вероятность противоположного события, а затем найтиискомую вероятность по формуле
/>.
Правило произведения.Если объект А можно выбрать изсовокупности объектов m способами и после каждого такого выбора объект В можновыбрать n способами, то пара объектов (А, В) в указанном порядке может бытьвыбрана mn способами.
Произведение событий. Произведениемдвух событий А и В называют событие АВ, состоящее в совместном появлении(совмещении) этих событий. Например, если А — деталь годная, В — детальокрашенная, то АВ — деталь годна и окрашена.
Произведением несколькихсобытий называют событие, состоящее в совместном появлении всех этихсобытий. Например, если А, В, С — появление «герба» соответственно в первом,втором и третьем бросаниях монеты, то АВС — выпадение «герба» во всех трехиспытаниях.
Условная вероятность. Вовведении случайное событие определено как событие, которое при осуществлениисовокупности условий S может произойти или не произойти. Если при вычислениивероятности события никаких других ограничений, кроме условий S, не налагается,то такую вероятность называют безусловной; если же налагаются и другиедополнительные условия, то вероятность события называют условной.Например, часто вычисляют вероятность события В при дополнительном условии, чтопроизошло событие А. Заметим, что и безусловная вероятность, строго говоря,является условной, поскольку предполагается осуществление условий S.
Условной вероятностью РA (В) называют вероятность события В,вычисленную в предположении, что событие А уже наступило.
Исходя из классическогоопределения вероятности, формулу РA(В) = Р (АВ) / Р (А) (Р (А) > 0 можно доказать. Это обстоятельство и служитоснованием для следующего общего (применимого не только для классическойвероятности) определения.
Условная вероятностьсобытия В при условии, что событие А уже наступило, по определению, равна
РA (В) = Р (АВ) / Р (А) (Р(A)>0).
Рассмотрим два события: А и В;пусть вероятности Р (А) и РA(В) известны. Как найти вероятность совмещения этих событий, т. е. вероятностьтого, что появится и событие А и событие В? Ответ на этот вопрос дает теоремаумножения.
Теорема. Вероятность совместногопоявления двух событий равна произведению вероятности одного из них на условнуювероятность другого, вычисленную в предположении, что первое событие уженаступило:
Р (АВ) = Р (А) РA (В). (*)
Доказательство:
По определению условнойвероятности,
РA (B) = Р (АВ) / Р (A).
Отсюда
Р (АВ) = Р (А) РA (В).
За м е ч ан и е. Применив формулу (*) к событию ВА, получим
Р(ВА) = Р (В) РB (А),
или,поскольку событие ВА не отличается от события АВ,
Р(АВ)= Р (В) РB (А). (**)
Сравниваяформулы (*) и (**), заключаем о справедливости равенства
Р(А) РA (В) = Р (В) РB (А). (***)
С л е д с т в и е. Вероятностьсовместного появления нескольких событий равна произведению вероятности одногоиз них на условные вероятности всех остальных, причем вероятность каждогопоследующего события вычисляется в предположении, что все предыдущие событияуже появились:
/>
где
/>
является вероятностью события An, вычисленной в предположении, чтособытия А1, А2,..., Аn— 1 наступили. В частности, для трех событий
Р (AВС) = Р (А) РA (В) РAB(С).
Заметим, что порядок, в которомрасположены события, может быть выбран любым, т. е. безразлично какое событиесчитать первым, вторым и т. д.
Пусть вероятность события В независит от появления события А.
Событие В называют независимымот события А, если появление события А не изменяет вероятности события В,т. е. если условная вероятность события В равна его безусловной вероятности:
РA (В) = Р (В). (*)
Подставив (*) в соотношение (***)предыдущего параграфа, получим
Р (A) Р (В) = Р (В) РB (A).
Отсюда
РB (A) = Р (A),
т. е. условная вероятностьсобытия A в предположении что наступило событие В, равна его безусловнойвероятности. Другими словами, событие A не зависит от события В.
Итак, если событие В не зависитот события A, то событие A не зависит от события В; это означает, что св о й с т в о н е з а в и с и м о с т и с о б ы т и й в за и м н о.
Для независимых событий теоремаумножения Р (АВ) = Р (А) РA(В) имеет вид
Р (АВ) = Р (А) Р (В), (**)
т. е. вероятность совместногопоявления двух независимых событий равна произведению вероятностей этихсобытий.
Равенство (**) принимают вкачестве определения независимых событий.
Два события называют независимыми,если вероятность их совмещения равна произведению вероятностей этих событий; впротивном случае события называют зависимыми.
На практике о независимостисобытий заключают по смыслу задачи. Например, вероятности поражения цели каждымиз двух орудий не зависят от того, поразило ли цель другое орудие, поэтомусобытия «первое орудие поразило цель» и «второе орудие поразило цель»независимы.
За м е ч а н и е 1. Если события А и В независимы, то независимы также события
/>
Действительно,
/>
Следовательно,
/>
Отсюда
/>
т.е. события А и В независимы.
Независимость событий
/>
являетсяследствием доказанного утверждения.
Несколько событий называютпопарно независимыми, если каждые два из них независимы. Например,события А, В, С попарно независимы, если независимы события А и В, А и С, В иС.
Для того чтобы обобщить теоремуумножения на несколько событий, введем понятие независимости событий всовокупности.
Несколько событий называютнезависимыми в совокупности (или просто независимыми), еслинезависимы каждые два из них и независимы каждое событие и все возможныепроизведения остальных. Например, если события A1, A2, А3, независимы в совокупности, тонезависимы события A1 и А2, А1и А3, А2 и A3;А1 и A2A3,A2 и A1A3,А3 и A1A2.Из сказанного следует, что если события независимы в совокупности, то условнаявероятность появления любого события из них, вычисленная в предположении, чтонаступили какие-либо другие события из числа остальных, равна его безусловнойвероятности.
Подчеркнем, что если несколькособытий независимы попарно, то отсюда еще не следует их независимость всовокупности. В этом смысле требование независимости событий в совокупностисильнее требования их попарной независимости.
Поясним сказанное на примере.Пусть в урне имеется 4 шара, окрашенные: один — в красный цвет (А), один — всиний цвет (В), один — в черный цвет (С) и один — во все эти три цвета (АВС).Чему равна вероятность того, что извлеченный из урны шар имеет красный цвет?
Так как из четырех шаров дваимеют красный цвет, то Р(А) = 2 / 4 = 1 / 2. Рассуждая аналогично, найдем Р (В)= 1 / 2, Р (С) = 1/ 2. Допустим теперь, что взятый шар имеет синий цвет, т. е.событие В уже произошло. Изменится ли вероятность того, что извлеченный шаримеет красный цвет, т. е. изменится ли вероятность события А? Из двух шаров,имеющих синий цвет, один шар имеет и красный цвет, поэтому вероятность событияА по-прежнему равна 1 / 2. Другими словами, условная вероятность события А,вычисленная в предположении, что наступило событие В, равна его безусловнойвероятности. Следовательно, события А и В независимы. Аналогично придем квыводу, что события A и С, В и С независимы. Итак, события А, В и С попарнонезависимы.
Независимы ли эти события всовокупности? Оказывается, нет. Действительно, пусть извлеченный шар имеет двацвета, например синий и черный. Чему равна вероятность того, что этот шар имеети красный цвет? Лишь один шар окрашен во все три цвета, поэтому взятый шаримеет и красный цвет. Таким образом, допустив, что события В и С произошли,приходим к выводу, что событие А обязательно наступит. Следовательно, этособытие достоверное и вероятность его равна единице. Другими словами, условнаявероятность РBC (A)= 1 событияА не равна его безусловной вероятности Р (А) = 1 / 2. Итак, попарно независимыесобытия А, В, С не являются независимыми в совокупности.
Приведем теперь следствие изтеоремы умножения.
С л е д с т в и е. Вероятностьсовместного появления нескольких событий, независимых в совокупности, равнапроизведению вероятностей этих событий:
Р (А1А2… Аn) = Р (А1) Р (А2)… Р (Аn).
Доказательство:
Рассмотрим три события: А, В и С.Совмещение событий А, В и С равносильно совмещению событий АВ и С, поэтому
Р (AВС) = Р (АВ * С).
Так как события А, В и Снезависимы в совокупности, то независимы, в частности, события АВ и С, а такжеА и В. По теореме умножения для двух независимых событий имеем:
Р (АВ * С) = Р (АВ) Р (С) и Р(АВ) = Р (А) Р (В).
Итак, окончательно получим
Р (AВС) = Р (А) Р (В) Р (С).
Для произвольного nдоказательство проводится методом математической индукции.
За м е ч а н и е. Если события А1, А2, ..., Аn независимы в совокупности, то и противоположные имсобытия
/>
такженезависимы в совокупности.
Пусть в результате испытаниямогут появиться n событий, независимых в совокупности, либо некоторые из них (вчастности, только одно или ни одного), причем вероятности появления каждого изсобытий известны. Как найти вероятность того, что наступит хотя бы одно из этихсобытий? Например, если в результате испытания могут появиться три события, топоявление хотя бы одного из этих событий означает наступление либо одного, либодвух, либо трех событий. Ответ на поставленный вопрос дает следующая теорема.
Теорема. Вероятностьпоявления хотя бы одного из событий А1, А2, ..., Аn, независимых в совокупности, равнаразности между единицей и произведением вероятностей противоположных событий
/>
Р (A) = 1 — q1q2… qn.(*)
Доказательство:
Обозначим через А событие,состоящее в появлении хотя бы одного из событий А1, А2,...,An. События А и
/>
(ни одно изсобытий не наступило) противоположны, следовательно, сумма их вероятностейравна единице:
/>
Отсюда, пользуясь теоремойумножения, получим
/>
или
/>
Ч а с т н ы й с л у ч а й.Если события А1, А2, ..., Аn имеют одинаковую вероятность, равную р,то вероятность появления хотя бы одного из этих событий
P (A) = l — qn. (**)