Комбинаторика и бином Ньютона

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

ФГБОУ ВПО Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых

по дисциплине: Теория вероятностей и математическая статистика

на тему: «Комбинаторика и бином Ньютона»

Гусь-Хрустальный 2013

Содержание

Введение

1. Понятие вероятности и зарождение науки о закономерности случайных явлений

1.1 Основные понятия теории вероятности

1.2 Событие: достоверное, невозможное, случайное

2. Комбинаторика

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

2.2 Размещения

2.3 Сочетания

3. Бином Ньютона

Задачи

Литература

Введение

1.1 Основные понятия теории вероятности

Как наука теория вероятности зародилась в 17 в. Возникновение понятия вероятности было связано как с потребностями страхования, получившего значительное распространение в ту эпоху, когда заметно росли торговые связи и морские путешествия, так и в связи с запросами азартных игр. Слово «азарт», под которым обычно понимается сильное увлечение, горячность, является транскрипцией французского слова hazard, буквально означающего «случай», «риск». Азартными называют те игры, а которых выигрыш зависит главным образом не от умения игрока, а от случайности. Схема азартных игр была очень проста и могла быть подвергнута всестороннему логическому анализу. Первые попытки этого рода связаны с именами известных учёных -- алгебраиста Джероламо Кардана (1501- 1576) и Галилео Галилея (1564 -- 1642). Однако честь открытия этой теории, которая не только даёт возможность сравнивать случайные величины, но и производить определенные математические операции с ними, принадлежит двум выдающимися ученым -- Блезу Паскалю (1623 -- 1662) и Пьеру Ферма. Всё началось с игры в кости.

На развитие теории вероятностей оказали влияние более серьёзные потребности науки и запросы практики, в первую очередь страховое дело, начатое в некоторых странах ещё в 16в. В 16-17вв. учреждение страховых обществ и страхование судов от пожара распространились во многих европейских странах. Азартные игры были для ученых только удобной моделью для решения задач и анализа понятий теории вероятности. Об этом заметил ещё Гюйгенс в своей книге «О расчётах в азартной игре» (1657), которая была первой книгой в мире по теории вероятностей. Гюйгенс впервые ввёл важное для теории вероятностей понятие математического ожидания, которое получило дальнейшее развитие а трудах Даниила Бернулли, Даламбера и др. Понятие математического ожидания находит немало применений а разных других областях человеческой деятельности.

Таким образом, в 60-е годы 17в. были выработаны первые понятия и некоторые элементы теории вероятностей. В последующие два века учёные столкнулись с множеством новых задач, связанных с исследованием случайных явлений. Играет ли природа в кости?

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

1.2 Событие: достоверное, невозможное, случайное

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

· Да, оно произошло.

· Нет, оно не произошло.

Например, у меня есть лотерейный билет. После опубликования результатов розыгрыша лотереи интересующее меня событие - выигрыш тысячи рублей либо происходит, либо не происходит. Любое событие происходит вследствие испытания (или опыта). Под испытанием (или опытом) понимают те условия, в результате которых происходит событие. Например, подбрасывание монеты - испытание, а появление на ней «герба» - событие. Событие принято обозначать заглавными латинскими буквами: A,B,C,… . События в материальном мире можно разбить на три категории - достоверные, невозможные и случайные.

Достоверное событие - это такое событие, о котором заранее известно, что оно произойдёт. Его обозначают буквой W. Так, достоверным является выпадение не более шести очков при бросании обычной игральной кости, появление белого шара при извлечении из урны, содержащей только белые шары, и т.п.

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

Случайное событие - это событие, которое может произойти или не произойти в результате испытания. События А и В называют несовместными, если наступление одного из них исключает возможность наступления другого. Так появление любого возможного числа очков при бросании игральной кости (событие А) несовместно с появлением иного числа (событие В). Выпадение чётного числа очков несовместно с выпадением нечётного числа. Наоборот, выпадение чётного очков (событие А) и числа очков, кратного трём (событие В),не будут несовместными, ибо выпадение шести очков означает наступление и события А, и события В, так что наступление одного из них не исключает наступление другого. С событиями можно совершать операции. Объединением двух событий С=АUВ называется событие С, которое происходит тогда и только тогда, когда происходит хотя бы одно из этих событий А и В. Пересечением двух событий D=A?? В называется событие, которое происходит тогда и только тогда, когда происходят события и А и В.

2. Комбинаторика

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

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

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

Возьмём n различных элементов: a₁ , a₂ , a₃ , …, a_n . Будем переставлять их всеми возможными способами, сохраняя их количество и меняя лишь порядок их расположения. Каждая из полученных таким образом комбинаций называется перестановкой. Общее количество перестановок из n элементов обозначается P_n . Это число равно произведению всех целых чисел от 1 до n :

P_n = n! P_n = 1•2•3•…• (n -- 1)•n=n!

Символ n! (называется факториал) - сокращённая запись произведения: 1 · 2 · 3 · … · (n - 1) · n .

Пример. Найти число перестановок из трёх элементов: a, b, c.

Решение. В соответствии с приведенной формулой:

P₃ = 1 · 2 · 3 = 6.

Действительно, мы имеем 6 перестановок: abc, acb, bac, bca, cab, cba.

2.2 Размещения

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

Их общее количество обозначается: и равно произведению:

Пример. Найти число размещений из четырёх элементов a, b, c, d по два.

Решение. В соответствии с формулой получим:

Вот эти размещения: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc.

2.3 Сочетания

Будем составлять группы из m различных элементов, взятых из множества, состоящего из n элементов, не принимая во внимание порядок расположения этих m элементов. Тогда мы получим сочетания из n элементов по m .

Их общее количество обозначается и может быть вычислено по формуле:

Из этой формулы ясно, что

Заметим, что можно составить только одно сочетание из n элементов по n, которое содержит все n элементов. Формула числа сочетаний даёт это значение, если только принять, что 0! = 1, что является определением 0! .

В соответствии с этим определением получим:

Общее число сочетаний можно вычислить, пользуясь и другим выражением:

Пример . Найти число сочетаний из пяти элементов: a, b, c, d, e по три.

Решение :

Эти сочетания: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.

3. Бином Ньютона

Бином Ньютона - это отношение, позволяющее представить выражение (a + b)ⁿ (n ? Z⁺) в виде многочлена, а именно:

(a + b)ⁿ = aⁿ + С_n¹a^{n - 1}b + С_n²a^{n - 2}b² + ... + С_n^ka^{n - k}b^k + ... + С_n^{n - 1}ab^{n - 1} + bⁿ.

Числа С_n¹, С_n², ... , С_n^{n - 1} называются биномиальными коэффициентами.

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

Первая строка в этой таблице содержит биномиальные коэффициенты для n = 1; вторая - для n = 2; третья - для n = 3 и т.д. Поэтому, если необходимо, например, разложить выражение:

( a + b )⁷ ,

мы можем получить результат моментально, используя таблицу:

Свойства биномиальных коэффициентов

1. Сумма коэффициентов разложения ( a + b ) ⁿ равна 2 ⁿ .

Для доказательства достаточно положить a = b = 1. Тогда в правой части разложения бинома Ньютона мы будем иметь сумму биномиальных коэффициентов, а слева:

2. Коэффициенты членов, равноудалённых от концов разложения, равны.

Это свойство следует из соотношения:

3. Сумма коэффициентов чётных членов разложения равна сумме коэффициентов нечётных членов разложения; каждая из них равна

Для доказательства воспользуемся биномом:

комбинаторика бином ньютон

Здесь чётные члены имеют знак « + » , а нечётные - « - ». Так как в результате разложения получается 0, то следовательно, суммы их биномиальных коэффициентов равны между собой, поэтому каждая из них равна: что и требовалось доказать.

Задачи

1. У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?

Решение. Имеем набор {я, я, г, г, г}. Всего перестановок пятиэлементного множества 5!, но мы не должны учитывать перестановки, в которых объекты одного типа меняются местами несколько раз, поэтому нужно поделить на возможное число таких перестановок: 2! · 3!

Получаем в итоге

Ответ: 10 способов.

2. Предприятие может предоставить работу по одной специальности 4 женщинами, по другой - 6 мужчинам, по третьей - 3 работникам независимо от пола. Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?

Решение. Имеем 14 претендентов и 13 рабочих мест. Сначала выберем работников на первую специальность, то есть 4 женщин из 6:

Далее независимо аналогичным образом выберем мужчин на вторую специальность:

Осталось 2 женщины, 2 мужчин и 3 вакантных места, которые, по условию, могут занять любые из четырех оставшихся человек. Это может быть сделано 2 вариантами:

1. 1 женщина и 2 мужчин (выбираем женщину C1 2 = 2 способами)

2. 1 мужчина и 2 женщины (выбираем мужчину C1 2 = 2 способами).

В итого получаем 15 · 28(2 + 2) = 1680 способов.

Ответ: 1680 способов.

3. Сколькими способами могут восемь человек стать в очередь к театральной кассе?

Решение. Существует 8 мест, которые должны занять 8 человек. На первое место может стать любой из 8 человек, т.е. способов занять первое место - 8. После того, как один человек стал на первое место, осталось 7 мест и 7 человек, которые могут быть на них размещены, т.е. способов занять второе место - семь. Аналогично для третьего, четвертого и т.д. места. Используя принцип умножения, получаем произведение - . Такое произведение обозначается как 8! (читается 8 факториал) и называется перестановкой P8.

Ответ: P8 = 8!

4. Алфавит некоторого языка содержит 30 букв. Сколько существует шестибуквенных слов (цепочка букв от пробела до пробела), составленных из букв этого алфавита, если:

- буквы в словах не повторяются?

- буквы в словах могут повторяться?

Решение. Существует шесть мест, на которые нужно разместить 30 букв.

1. Буквы не должны повторяться. Используя принцип умножения, получаем произведение:

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

1=== == = А

формула для размещений.

2. Буквы повторяются. Используя принцип умножения, получаем: 303030303030 = 30⁶ = Г - формула для размещений с повторениями.

Ответ: 1) А; 2) Г.

5. Сколько слов можно образовать из букв слова фрагмент, если слова должны состоять:

(а) из восьми букв, (б) из семи букв, (в) из трех букв?

Решение. В слове фрагмент 8 букв алфавита.

(а) Всевозможные перестановки 8 букв по восьми местам:

А = =P₈.

(б) Размещения 8 букв по 7 местам: А.

(в) Размещения 8 букв по 3 местам: А.

Ответ: P₈, А, А.

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

Решение. Из 20-ти элементов необходимо сделать три выборки, причем порядок внутри выборок значения не имеет. Поэтому используем формулу для сочетаний. Чтобы выбрать из 20-ти элементов 3, существует С способов. Остается 17 элементов, из которых выбирается 5 элементов - С способами. Остается 12 элементов, из которых выбирается 12 элементов. Это можно сделать С= 1, т.е. одним способом. Используя принцип произведения, получаем: С С С.