Лекционный курс в ПДФ (1119925)
Текст из файла
Комбинаторные формулыПусть имеется множество, состоящее из n элементов. Обозначим его Un.Перестановкой из n элементов называется заданный порядок во множестве Un.Примеры перестановок:1)распределение n различных должностей среди n человек;2)расположение n различных предметов в одном ряду.Сколько различных перестановок можно образовать во множестве Un? Числоперестановок обозначается Pn (читается Р из n).Чтобы вывести формулу числа перестановок, представим себе n ячеек,пронумерованных числами 1,2,...n.
Все перестановки будем образовывать, располагаяэлементы Un в этих ячейках. В первую ячейку можно занести любой из n элементов (иначе:первую ячейку можно заполнить n различными способами). Заполнив первую ячейку, можноn-1 способом заполнить вторую ячейку (иначе: при каждом способе заполнения первойячейки находится n-1 способов заполнения второй ячейки). Таким образом существует n(n-1)способов заполнения двух первых ячеек. При заполнении первых двух ячеек можно найти n2 способов заполнения третьей ячейки, откуда получается, что три ячейки можно заполнитьn(n-1)(n-2) способами.
Продолжая этот процесс, получим, что число способов заполнения nячеек равно n n - 1n - 2...3 × 2 × 1. ОтсюдаPn = n(n - 1)(n - 2)...×3×2×1Число n(n - 1)(n - 2)...×3×2×1, то есть произведение всех натуральных чисел от 1 до n,называется "n-факториал" и обозначается n!. Отсюда Pn =n!Пример. 5 ! = 5 × 4 × 3 × 2 = 120 .По определению считается: 1!=1; 0!=1.Размещениями из n элементов по k элементов будем называть упорядоченныеподмножества, состоящие из k элементов, множества Un - (множества, состоящего из nэлементов). Число размещений из n элементов по k элементов обозначается Ank (читается "Аиз n по k").Примеры задач, приводящих к необходимости подсчета1) Сколькими способами можно выбрать из 15 человек 5 кандидатов и назначить их на 5различных должностей?2) Сколькими способами можно из 20 книг отобрать 12 и расставить их в ряд на полке?В задачах о размещениях полагается k<n.
В случае, если k=n, то легко получитьkAn = Pn = n!Для подсчета Ank используем тот же метод, что использовался для подсчета Pn,только здесь возьмем лишь k ячеек. Первую ячейку можно заполнить n способами, вторую,при заполненной первой, можно заполнить n-1 способами.
Можно продолжать этот процессдо заполнения последней k-й ячейки. Эту ячейку при заполненных первых k-1 ячейкахможно заполнить n-(k-1) способами (или n-k+1). Таким образом все k ячеек заполняютсячислом способов, равнымn(n - 1)(n - 2)...(n - k + 2)(n - k + 1) =Отсюда получаем: Ank =n!(n - k ) !n!( n- k ) !1Пример. Сколько существует различных вариантов выбора 4-х кандидатур из 9-тиспециалистов для поездки в 4 различных страны?A94 =9!9!== 9 × 8 × 7 × 6 = 3024(9 - 4) ! 5 !Сочетаниями из n элементов по k элементов называются подмножества, состоящиеиз k элементов множества Un (множества, состоящего из n элементов).Одно сочетание от другого отличается только составом выбранных элементов (но непорядком их расположения, как у размещений).Число сочетаний из n элементов по k элементов обозначается Cnk (читается "C из n поk").Примеры задач, приводящих к необходимости подсчета числа сочетаний:1) Сколькими способами можно из 15 человек выбрать 6 кандидатов для назначения наработу в одинаковых должностях?2) Сколькими способами можно из 20 книг отобрать 12 книг?Выведем формулу для подсчета числа сочетаний.
Пусть имеется множество Un инужно образовать упорядоченное подмножество множества Un, содержащее k элементов (тоесть образовать размещение). Делаем это так:1) выделим какие-либо k элементов из n элементов множестваUn Это, согласносказанному выше, можно сделать Cnk способами;2) упорядочим выделенные k элементов, что можно сделать Pk = k ! способами. Всегоможно получить Cnk × Pk вариантов (упорядоченных подмножеств), откуда следует:Ank = Cnk × Pk ,то естьCnkAnkn!==Pk(n - k)! k !Пример: 6 человек из 15 можно выбрать числом способов, равнымC156 =15 × 14 × 13 × 12 × 11 × 1015 !== 50059! 6!6 × 5× 4× 3× 2Задачи на подсчет числа подмножеств конечного множества называютсякомбинаторными. Рассмотрим некоторые комбинаторные задачи.1.Из семи заводов организация должна выбрать три для размещения трех различныхзаказов.
Сколькими способами можно разместить заказы?Так как все заводы различны, и из условия ясно, что каждый завод может либополучить один заказ, либо не получить ни одного, здесь нужно считать число размещенийA73 =7!= 7 × 6 × 5 = 2104!2.Если из текста задачи 1 убрать условие различия трех заказов, сохранив всеостальные условия, получим другую задачу. Теперь способ размещения заказов определяетсятолько выбором тройки заводов, так как все эти заводы получат одинаковые заказы, и числовариантов определяется как число сочетаний.2C73 =7!= 354 !× 3 !3.Имеются 7 заводов.
Сколькими способами организация может разместить на нихтри различных производственных заказа? (Заказ нельзя дробить, то есть распределять его нанесколько заводов).В отличие от условия первой задачи, здесь организация может отдать все три заказапервому заводу или, например, отдать два заказа второму заводу, а один - седьмому.Задача решается так. Первый заказ может быть размещен семью различнымиспособами (на первом заводе, на втором и т.д.). Разместив первый заказ, имеем семьвариантов размещения второго (иначе, каждый способ размещения первого заказа можетсопровождаться семью способами размещения второго).
Таким образом, существует 7×7=49способов размещения первых двух заказов. Разместив их каким-либо образом, можем найти7 вариантов размещения третьего (иначе, каждый способ размещения первых двух заказовможет сопровождаться семью различными способами распределения третьего заказа).Следовательно, существуют 49×7=73 способов размещения трех заказов. (Если бы заказовбыло n, то получилось бы 7n способов размещения).4.Как решать задачу 3, если в ее тексте вместо слов "различных производственныхзаказа" поставить "одинаковых производственных заказа"?5.Добавим к условию задачи 1 одну фразу: организация также должна распределитьтри различных заказа на изготовление деревянных перекрытий среди 4-х лесопилок.Сколькими способами могут быть распределены все заказы?Каждый из A73 способов распределения заказов на заводах может сопровождаться A43способами размещения заказов на лесопилках.
Общее число возможных способовразмещения всех заказов будет равноÀ73 × À43 =7! 4!×= 7!4 ! 1!Случайный эксперимент, элементарные исходы, события.Случайным (стохастическим) экспериментом или испытанием называетсяосуществление какого-либо комплекса условий, который можно практически или мысленновоспроизвести сколь угодно большое число раз.Примеры случайного эксперимента: подбрасывание монеты, извлечение одной картыиз перетасованной колоды, подсчет числа автомобилей в очереди на бензоколонке в данныймомент.Явления, происходящие при реализации этого комплекса условий, то есть врезультате случайного эксперимента, называются элементарными исходами.
Считается,что при проведении случайного эксперимента реализуется только один из возможныхэлементарных исходов.Если монету подбросить один раз, то элементарными исходами можно считатьвыпадение герба (Г) или цифры (Ц).Если случайным экспериментом считать троекратное подбрасывание монеты, тоэлементарными исходами можно считать следующие:ГГГ, ГГЦ, ГЦГ, ЦГГ, ГЦЦ, ЦГЦ, ЦЦГ, ЦЦЦ.3Множество всех элементарных исходов случайного эксперимента называетсяпространством элементарных исходов .
Будем обозначать пространство элементарныхисходов буквой W (омега большая) i-й элементарный исход будем обозначатьwi (w-омегамалая).Если пространство элементарных исходов содержит n элементарных исходов, тоW=(w1, w2 ,..., wn ).Для троекратного подбрасывания монеты,W=(ГГГ, ГГЦ,...ЦЦЦ).Если случайный эксперимент - подбрасывание игральной кости, то W=(1,2,3,4,5,6).Если W конечно или счетно, то случайным событием или просто событиемназывается любое подмножество W.Множество называется счетным, если между ним и множеством N натуральных чиселможно установить взаимно-однозначное соответствие.Пример счетного множества: множество возможных значений времени прилетаинопланетян на Землю, если время отсчитывать с настоящего момента и исчислять сточностью до секунды.Примеры несчетных множеств: множество точек на заданном отрезке, множествочисел x, удовлетворяющих неравенству 1< x £ 2.В случае несчетного множества W будем называть событиями только подмножества,удовлетворяющие некоторому условию (об этом будет сказано позже).Приведем примеры событий.
Пусть бросается игральная кость, и элементарнымисходом считается выпавшее число очков: W=(1,2,3,4,5,6). A — событие, заключающееся втом, что выпало четное число очков: А=(2,4,6); B — событие, заключающееся в том, чтовыпало число очков, не меньшее 3-х: B=(3,4,5,6).Говорят, что те исходы, из которых состоит событие А, благоприятствуют событию А.События удобно изображать в виде рисунка, которыйназывается диаграммой Венна. На рисунке 1 пространствоэлементарных исходов W изображено в виде прямоугольника,а множество элементарных исходов, благоприятствующихсобытию A, заключено в эллипс. Сами исходы на диаграммеВенна не изображаются, а информация о соотношении междуих множествами содержится в расположении границРис.1соответствующих областей.Суммой (объединением) двух событий А и B (обозначается AUB ) называетсясобытие, состоящее из всех элементарных исходов,принадлежащих по крайней мере одному из событий А или B.Событие AUB происходит, если происходит по крайней мереодно из событий А или B.Приведем пример объединения событий.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
