Схемы выбора конечного числа элементов из заданного множества.
Дата добавления: 2014-03-24 ; просмотров: 9280 ; Нарушение авторских прав
Правило умножения и правило сложения.
Комбинаторика.
История возникновения теории вероятностей.
Предмет теории вероятностей.
6. Элементы комбинаторики: сочетание, размещение, перестановка.
Каждодневный опыт убеждает нас в том, что в обыденной жизни, практических ситуациях, а также в научных исследованиях постоянно приходится сталкиваться с положениями, когда привычные нам закономерности строгого детерминизма, уже не имеют места. При решении многих задач нам приходится учитывать и случайные факторы, придающие исходу элемент неопределенности. Например, при стрельбе из орудия по цели наблюдается так называемое рассеивание снарядов. Уклонение очки попадания снаряда от центра цели заранее указать нет возможности – оно случайно. Невозможно предсказать, какая сторона выпадет при бросании монеты. Одной констатации факта наличия случайности для уверенного использования явлений природы или управления технологическими процессами совершенно недостаточно, необходимо научиться количественно оценивать случайные явления, прогнозировать их течение. Этим занимаются две математические науки – теория вероятностей и математическая статистика.
Теория вероятностей – математическая наука, изучающая закономерности, присущие массовым случайным явлениям.
Предметом теории вероятностей являются математические модели случайных явлений. То есть теория вероятностей рассматривает не сами реальные явления, а их упрощенные схемы – математические модели. Под случайным явлением понимают явление, предсказать исход которого невозможно (при неоднократном воспроизведении одного и того же опыта оно протекает каждый раз несколько по-иному).
Возникновение теории вероятностей относится к середине 17 в. и связано с попыткой создания теории азартных игр. Первую книгу по теории вероятностей «О расчетах в азартной игре» опубликовал голландский математик Х.Гюйгенс. Становление теории вероятностей как науки связано с именами Якоба Бернулли, К. Гаусса, П Лапласа, С. Пуассона. Ученые были убеждены в том, что на базе массовых случайных явлений могут возникать четкие закономерности.
С половины 19 столения развитие теории вероятностей связано в значительной мере с именами русских ученых – В.Я Бунявского ( был написан им первый в Росси курс теории вероятностей), П.Л.Чебышева, А.А.Маркова, А.М.Ляпунова. ими было введено в качестве объекта систематического изучения и широко использовано понятие случайной величины.
В настоящее время нет практически ни одной области науки, в которой в той или иной степени не применялись бы вероятностные методы.
Во многих задачах классической теории вероятностей используется комбинаторика – раздел математики, в котором изучаются различные соединения (комбинации) элементов конечных множеств.
Многие комбинаторные задачи могут быть решены с помощью двух важных правил:
1. Правило умножения: если из некоторого конечного множества первый объект (элемент ) можно выбрать способами, а второй объект (элемент ) — способами, то оба объекта ( и ) в указанном порядке можно выбрать способами.
Это правило распространяется на случай трех и более объектов.
Пример. Сколькими способами могут быть распределены три призовых места среди 16 соревнующихся?
Решение. Имеется 16 различных способов распределения 1-го места. После того как первое место занято, осталось 15 соревнующихся, претендующих на 2-ое место. После занятия второго места, осталось 14 спортсменов, претендующих на 3-е место. Так как нам надо распределить 1-ое и 2-ое и 3-е места среди соревнующихся, то воспользуемся правилом умножения: (способов).
Ответ. Существует 3360 способов распределения трех призовых мест среди 16 соревнующихся.
Пример. Если подбросить одновременно три игральные кости, то сколько имеется различных возможных комбинаций выбранных очков?
Решение. Первая кость – 6 возможных комбинаций, вторая кость – 6 возможных комбинаций, третья кость – 6 возможных комбинаций. Так как одновременно подбрасываются 1-ая кость и 2-я и 3-я, то воспользуемся правилом умножения: (способов).
Ответ. При подбрасывании одновременно трех игральных костей имеется 216 способов различных возможных комбинаций выпавших очков.
2. Правило сложения: если некоторый объект можно выбрать способами, а объект — способами, причем первые и вторые способы не пересекаются, то любой из указанных объектов ( или ) можно выбрать способами.
Данное правило распространяется на любое конечное число объектов.
Пример. Сколькими способами можно выбрать один цветок из корзины, в которой имеется 12 гвоздик, 15 роз и 7 хризантем?
Решение. Одну гвоздику мы можем выбрать 12 способами, одну розу – 15 способами, одну хризантему – 7 способами. Так как выбрать надо только один цветок из корзины, то это будет или 1 гвоздика или 1 роза или 1 хризантема. Воспользуемся правилом сложения: 12+15+7=34 (способа).
Ответ. Один цветок из корзины можно выбрать 34 способами.
Пример. В студенческой группе 12 девушек и 16 юношей. Сколькими способами можно выбрать для вручения призов двух студентов одного пола?
Решение. Сначала найдем сколькими способами для вручения призов можно выбрать двух девушек их 12. Воспользуемся правилом умножения: (способа). Теперь найдем сколькими способами можно выбрать двух юношей: (способов). Так как по условию задачи призы вручают или две девушки или два юноши, то воспользуемся правилом сложения: 132+240=372 способа.
Ответ. Для вручения призов двух студентов одного пола можно выбрать 372 способами.
Решение вероятностных задач часто облегчается, если использовать комбинаторные формулы. Каждая из них определяет число всевозможных исходов в некотором опыте, состоящем в выборе наудачу элементов из различных элементов рассматриваемого множества.
Существует две схемы выбора элементов ( ) из исходного множества:
· без возвращения – выбранные элементы не возвращаются в исходное множество;
· с возвращением – выбор осуществляется поэлементно с обязательным возвращением отобранного элемента на каждом шаге.
Элементы комбинаторики (схема выбора без возвращения).
Пусть имеется множество из различных элементов, т.е. элементы имеют или разные названия или разные номера. Пусть , .
Определение. Сочетанием из элементов по элементов называется любое подмножество, которое содержит элементов, взятых из данных элементов.
Из определения следует, что сочетания – это выборки (комбинации), каждая из которых состоит из элементов, взятых из данных элементов, и которые различаются друг от друга только элементами, входящими в них; порядок, в котором они расположены не имеет значения.
Число различных сочетаний из элементов по можно найти по формуле
Значения могут быть найдены не расчетом по формуле количества сочетаний, а с помощью так называемого треугольника Паскаля (Блез Паскаль (1623 – 1662) – французский математик).
Источник
ПОДРОБНЫЕ ОТВЕТЫ!
3. Сколькими способами могут быть распределены три призовых места среди 16 соревнующихся?
4. Сколько различных «слов» состоящих из трех букв, можно образовать из букв слова ЛЕТО?
Ответ:
Пошаговое объяснение:
16*15*14=3360 (если первое второе и третье место разное по наградам)
Х стр. — всего
(0,5х — 18) — прочитано в первый день
1) х — (0,5х — 18) = 0,5х + 18 (стр.) — остаток после первого дня
2) (0,5х + 18) * 0,5 — 8 = 0,25х + 9 — 8 = 0,25х + 1 (стр.) — прочитано за второй день
3) (0,5х + 18) — (0,25х + 1) = 0,5х + 18 — 0,25х — 1 = 0,25х + 17 (стр.) — остаток после двух первых дней
4) (0,25х + 17) * 0,5 — 3 = 0,125х + 8,5 — 3 = 0,125х + 5,5 (стр.) — прочитано за третий день
5) (0,25х + 17) — (0,125х + 5,5) = 0,25х + 17 — 0,125х — 5,5 = 0,125х + 11,5 (стр.) — осталось после трёх дней, что равно 23 страницам
6) 0,125х + 11,5 = 23
0,125х = 11,5
х = 11,5 : 0,125
х = 92 стр. — всего в книге
7) 92 * 0,5 — 18 = 28 стр. — прочитано в первый день
8) 92 — 28 = 64 стр. — остаток
9) 64 * 0,5 — 8 = 24 стр. — прочитано во второй день.
Узнаем про третий день, но в вопросе об этом не спрашивается :
10) 64 — 24 = 40 стр. — остаток после двух первых дней
11) 40 * 0,5 — 3 = 17 стр. — прочитано в третий день.
Проверяем:
28 + 24 + 17 + 23 = 92 стр. — всего в книге.
Источник
Элементы комбинаторики
Составитель преподаватель кафедры высшей математики Ищанов Т.Р.
Занятие №1. Элементы комбинаторики
Теория.
Правило умножения: если из некоторого конечного множества первый объект (элемент «a») можно выбрать n1 способами, а второй объект (элемент «b») — n2 способами, то оба объекта (a и b) в указанном порядке можно выбрать» width=»49
» style=»vertical-align: -4px;»/> способами.
» width=»49 Правило сложения: если некоторый объект «a» можно выбрать n1 способами, а объект «b» можно выбрать n2 способами, причем первые и вторые способы не пересекаются, то любой из объектов (a или b) можно выбрать 
» width=»58
» style=»vertical-align: -4px;»/> способами.
Практический материал.
1.(6.1.44. Л) Сколько различных трехзначных чисел можно составить из цифр 0; 1; 2; 3; 4 если:
а) цифры не могут повторяться;
б) цифры могут повториться;
в) числа должны быть четными (цифры могут повторяться);
г) число должно делиться на 5 (цифры не могут повторяться)
(Ответ: а) 48; б) 100; в) 60; г) 12)
2. (6.1.2.) Сколько чисел, содержащих не менее трех различных цифр, можно составить из цифр 3; 4; 5; 6; 7? (Ответ: 300.)
3. (6.1.39) Сколько можно составить четырехзначных чисел так, чтобы любые две соседние цифры были различными? (Ответ: 6561)
Теория. Пусть дано множество, состоящее из «n» различных элементов. Размещением из «n» элементов по «k» элементов (
» style=»vertical-align: -3px;»/>) называется любое упорядоченное подмножество данного множества, содержащее «k» элементов.
» width=»77 Два размещения различны, если они отличаются друг от друга либо составом элементов, либо порядком их следования. Число размещений из «n» элементов по «k» обозначаются символом 
» width=»21
» style=»vertical-align: -4px;»/> и вычисляется по формуле:
px;»> 
» width=»115
» alt=»\[A_n^k=\frac
Практический материал.
4. (6.1.9 Л.) Составить различные размещения по два элемента из элементов множества A= <3,4,5>и подсчитать их число. (Ответ: 6)
5. (6.1.3 Л) Сколькими способами могут быть распределены три призовых места среди 16 соревнующихся? (Ответ: 3360)
6. (6.1.11. Л) Сколько имеется пятизначных чисел, все цифры у которых различны? Указание: учесть тот факт, что цифры вида 02345, 09782 и т.д. не считаем пятизначными. (Ответ: 27 216)
7. (6.1.12.Л.) Сколькими способами можно составить трехцветный полосатый флаг (три горизонтальных полосы), если имеется материя 5 различных цветов? (Ответ: 60.)
Теория. Сочетанием из «n» элементов по «k» элементов (
» style=»vertical-align: -3px;»/>) называется любое подмножество данного множества, которое содержит «k» элементов.
Любые два сочетания отличаются друг от друга только составом элементов. Число сочетаний из «n» элементов по «k» обозначается символом
» style=»vertical-align: -4px;»/> и вычисляется по формуле:
» width=»21 px;»> 
» width=»129
» alt=»\[C_n^k=\frac
Практический материал.
8.(6.1.20.) Составить различные сочетания по два элемента из элементов множества A= <3,4,5>и подсчитать их число. (Ответ: 3.)
9. (6.1.25.) Группа туристов из 12 юношей и 7 девушек выбирает по жребию 5 человек для приготовления ужина. Сколько существует способов при которых в эту «пятерку» попадут:
а) одни девушки; б) 3 юноши и 2 девушки;
в) 1 юноша и 4 девушки; г) 5 юношей; д) туристы одного пола.
(Ответ: а) 21; б) 4620; в) 420; г) 792; д) 813.)
Теория. Перестановкой из «n» элементов называется размещение из «n» элементов по «n» элементов. Таким образом, указать ту или иную перестановку данного множества из «n» элементов значит выбрать определенный порядок этих элементов. Поэтому любые две перестановки отличаются друг от друга только порядком следования элементов. Число перестановок из «n» элементов обозначается символом
» style=»vertical-align: -3px;»/> и вычисляется по формуле:
» width=»19 px;»> 
» width=»105
» alt=»\[P_n=A_n^n=n!\]» title=»Rendered by QuickLaTeX.com»/>
10.(6.1.14.Л) Составить различные перестановки из элементов множества A=<5;8;9>. (Ответ: 6)
11.(6.1.15.Л) Сколькими способами можно расставить на книжной полке десятитомник произведений Д. Лондона, располагая их:
а) в произвольном порядке;
б) так, чтобы 1, 5, 9 тома стояли рядом (в любом порядке);
в) так, чтобы 1, 2, 3 тома не стояли рядом (в любом порядке).
(Ответ: а) 10! б) 8!?3! в) 
» width=»85
» style=»vertical-align: -4px;»/>)
12. (1.6.16.Л.) В комнате имеется 7 стульев. Сколькими способами можно разместить на них 7 гостей? 3 гостя? (Ответ: 5040; 210)
Схема выбора с возвращением.
Теория. Если при упорядоченной выборке «k» элементов из «n», элементы возвращаются обратно, то полученные выборки представляют собой размещения с повторениями. Число всех размещений с повторениями из «n» элементов по «k» обозначается символом
» style=»vertical-align: -4px;»/> и вычисляется по формуле:
» width=»21 px;»> 
» width=»69
» alt=»\[\bar A_n^k=n^k.\]» title=»Rendered by QuickLaTeX.com»/>
Если при выборке «k» элементов из «n», элементы возвращаются обратно без последующего упорядочивания (таким образом, одни и те же элементы могут выниматься по нескольку раз, т.е. повторяться), то полученные выборки есть сочетания с повторениями. Число всех сочетаний с повторениями из «n» элементов по «k» обозначается символом 
» width=»21
» style=»vertical-align: -4px;»/> и вычисляется по формуле:
px;»> 
» width=»102
» alt=»\[\bar C_n^k=C^k_
13.(6.1.29.) Из элементов (цифр) 2, 4, 5 составить все размещения и сочетания с повторениями по два элемента. (Ответ: 9; 6)
14. (6.1.31.Л.) Пять человек вошли в лифт на 1-м этаже девятиэтажного дома. Сколькими способами пассажиры могут выйти из лифта на нужных этажах? (Ответ: 
» width=»130
» style=»vertical-align: -5px;»/>)
15. (6.1.59.Л.) В кондитерской имеется 7 видов пирожных. Сколькими способами можно приобрести в ней: а) 3 пирожных одного вида; б) 5 пирожных? (Ответ: а) 7; б) 462)
Теория. Пусть в множестве из «n» элементов есть «k» различных типов элементов, при этом 1-й тип элементов повторяется n1 раз, 2-й — n2 раз, . . . , k-й — nk раз, причем
» style=»vertical-align: -4px;»/>. Тогда перестановки элементов данного множества представляют собой перестановки с повторениями.
Число перестановок с повторениями (иногда говорит о числе разбиений множества) из n элементов обозначается символом
» style=»vertical-align: -4px;»/> и вычисляется по формуле:
» width=»178 
» width=»135 px;»> 
» width=»300
» alt=»\[P_n (n_1,n_2,\cdot\cdot\cdot,n_k )=\frac
16.(6.1.32.) Сколько различных «слов» (под «словом» понимается любая комбинация букв) можно составить, переставляя буквы в слове АГА? MISSISSIPPI?
Решение.
Вообще из трех букв можно составить
» style=»vertical-align: -3px;»/> различных трехбуквенных «слов». В слове АГА буква «А» повторяется, а перестановка одинаковых букв не меняет «слова». Поэтому число перестановок с повторениями меньше числа перестановок без повторений во столько раз, сколько можно переставлять повторяющиеся буквы. В данном слове две буквы (1-я и 3-я) повторяются; поэтому различных перестановок трехбуквенных «слов» из букв слова АГА можно составить столько:
» width=»89 px;»> 
» width=»143
» alt=»\[P_3/P_2 =3!/2!=3.\]» title=»Rendered by QuickLaTeX.com»/>
Впрочем, ответ можно получить и проще: 
» width=»165
» style=»vertical-align: -5px;»/>. По этой же формуле найдем число одиннадцатибуквенных «слов» при перестановке букв в слове MISSISSIPPI. Здесь n=11; n1=1; n2=4 (4 буквы S); n3=4 (4 буквы I); n4=2, поэтому
px;»> 
» width=»438
» alt=»\[P_ <11>(1,4,4,2)=\frac<11!><1!4!4!2!>=\frac<5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11><1\cdot 24\cdot 2>=34 650.\]» title=»Rendered by QuickLaTeX.com»/>
17.(6.1.38.Л.) Сколько существует различных перестановок букв в слове ТРАКТАТ? А в «слове» АААУУАУУУУ? (Ответ: 420; 210)
Источник
