Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Элементы комбинаторики

Читайте также:
  1. III. Элементы аналитической геометрии на плоскости и в пространстве.
  2. P-элементы VI группы
  3. P-элементы VI группы
  4. P-элементы VI группы
  5. P-элементы VI группы
  6. p-элементы VI группы
  7. s-, p-Элементы, переходные элементы
  8. VBA. Циклический алгоритм, понятие, основные элементы. Виды циклических алгоритмов.
  9. Административно-правовой статус гражданина РФ, его элементы
  10. Аккреционная структура Сихоте-Алинь-Сахалинской области, основные тектонические элементы и этапы формирования

Пусть имеется множество, состоящее из n различных элементов, например, множество букв русского алфавита: (а, б, в, г, … э, ю, я).

Из этих элементов можно составить наборы (множества) из k элементов, отличающиеся друг от друга, как составом, так и порядком элементов. Эти наборы будем называть соединениями (кортежами) длины k.Если в соединении каждый элемент исходного множества встречается только один раз, то этот способ выбора элементов характеризуется словами «без повторений», в противном случае - «с повторениями». В первом случае число элементов в соединении не превышает числа элементов в исходном множестве, т.е. k ≤ n, а во втором может быть и больше. Рассмотрим сначала выборы без повторений.

1. Перестановки без повторений - соединения из n элементов, различающиеся только порядком элементов.

Число перестановок

2. Размещения без повторений соединения, различающиеся порядком или составом. Число таких размещений из n элементов по k обозначается

(2)

Действительно, первый элемент в соединении может быть выбран n способами, второй – (n-1) - м способом, …….. k – й - (n-(k-1)) способами, общее же число вариантов равно произведению числа этих способов.

Пример 1. Выписать размещения из трех букв a, б, в по две.

 

3 .Сочетания без повторений соединения из n элементов по k, различающиеся только составом, порядок элементов не учитывается. Число таких сочетаний из n элементов по k обозначается и равно

. (3)

Смысл этой формулы понять нетрудно: число размещений , отличающиеся порядком или составом, в k! больше числа сочетаний , отличающиеся только составом.

 

4. Перестановки с повторениями - соединения длиной , содержащие элементов , элементов ,… элементов .

Перестановке с повторениями можно сопоставить числовое множество ,

где каждое (фиксированное) число равно числу элементов го вида. Перестановки с повторениями различаются только порядком (состав одинаковый)

Число перестановок с повторениями равно

(4)

Действительно, число перестановок из k элементов равно k!. Учитывая, что каждую группу элементов можно переставить ! способами, не получая новой перестановки, получим формулу (4).

Пример. Сколько «слов» можно составить, переставляя буквы в слове «город»?

Число слов равно . Букв «г», «р», «д» по одной, «о» повторяется два раза.

5. Размещения с повторениями соединения из k элементов, каждый из которых может быть любого из n типов.Размещения с повторениямиотличаются друг от друга порядком или составом (т.е элементами и кратностью их повторения). Число размещений с повторениямиравно

, (5)

поскольку каждый элемент может быть выбран n способами.

Пример 1. Сколько способов выхода из лифта пяти человек на трех этажах?

Поскольку каждый человек имеет 3 варианта, то общее число вариантов равно произведению 3·3·3·3·3 = = .

Замечание. Столь большое число вариантов выхода объясняется тем, что люди имеют имена, а этажи - номера, и способы выхода различаются как фамилиями вышедших и их порядком, так и номером этажа, хотя в большинстве учебников задача формулируется именно таким «безликим» способом.

Пример 2. Сколько существует способов N заполнить квадратную таблицу нулями и единицами так, чтобы симметричные относительно главной диагонали клетки содержали разные числа? - Общее число способов равно числу способов заполнить треугольную таблицу, включающую главную диагональ и клетки под ней (верхняя часть заполнится альтернативно); таким образом N= .

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

Так же, как и для перестановок с повторениями, каждый состав сочетания может быть

задан числовым множеством , где каждое (изменяющееся) число равно

числу элементов го вида. Таким образом, число сочетаний с повторениямиравно

числу этих множеств, у которых сумма

Число сочетаний с повторениями равно

(6)

Пример 3. Повторим условие примера 1:

Сколько способов выхода из лифта пяти человек на трех этажах?

Формулировка задачи, безусловно, не делает различия между тем, кто именно вышел на том или ином этаже, важно лишь количество выходящих и номер этажа.

В этой формулировке ответ дается формулой (6)

(напишите все варианты!)

Классическое определение вероятности.

Эксперимент называется классическим, если его проведение приводит к событиям

, удовлетворяющим условиям:

1. Они попарно несовместны, т.е (невозможное событие);

2. Образуют полную группу, т. е ;

3. Равновозможны, т.е. ни одно из этих событий не является предпочтительным по степени возможности его появления

Если эксперимент является классическим, то вероятностью события A называется отношение , где n - общее число случаев (исходов) эксперимента, а m - число случаев, благоприятствующих событию A, т.е. случаев, при которых событие A происходит.

Классическое определение реализуется, например, на так называемой Урновой схеме: В урне находится М белых и N черных шаров. Какова вероятность сделать выборку, состоящую из m белых и n черных шаров (событие А)?

В этом случае , .

Пример: Какова вероятность угадать ровно 3 номера в лотерее «5 из 36»?

. Здесь число случаев, благоприятствующих событию A

(3 номера верные, 2 неверные) равно произведению числа способов выбрать 3 номера из 5 верных на число способов выборки 2-х неверных номеров из (36-5=31) неверных.

 

Пример 1 [1]. Каждый из девяти человек независимо и случайно выбирают одну из трех линий обслуживания. Найти вероятность того, что они распределены между линиями поровну.

Обобщим задачу. Найдем вероятность распределения клиентов по линиям таким образом, что на – ой линии находятся клиентов.

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

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

Таким образом, . (1)

В рассматриваем примере = , что в 6 раз меньше ответа в [1].

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

,

что после сокращения на 9 и приводит к .

Ошибка, по-видимому, в том, что полученный результат следует разделить на число «перенумераций» линий 3!=6, поскольку в формулировке задачи линии не различаются.

Пример 2. Найти вероятность того, что четыре клиента выберут первую линию, четыре третью, а один вторую.

По формуле (1)

Если сформулировать эту же задачу, лишив линии номеров, т.е. так: какова вероятность того, что восемь из девяти клиентов разделятся между двумя линиями поровну, то числитель в (1) будет равен сумме

,

где число перестановок с повторениями равно числу слагаемых. Число «2» - число одинаковых чисел «4», число «1» - одна единица в .

Пример 3. [1]. Билеты на стадион разделены на 7 категорий – по секторам. Найти вероятность того, что 4 конкретных покупателя приобретут билеты разных категорий.

По формуле (1) .

В [1] приводится другой ответ . Уберем из условия задачи слово «конкретных». Тогда этот ответ и получим:

.

Пример 4. [1]. Экзамены принимают два экзаменатора, каждый из которых должен проэкзаменовать по 12 студентов. Найти вероятность того, что два конкретных студента попадут к одному экзаменатору.

Достаточно рассмотреть одного из экзаменаторов, поскольку ко второму без дополнительных вариантов попадают остальные. Общее число вариантов равно числу сочетаний N= , число случаев попадания двух конкретных студентов равно произведению , где второй множитель равен числу вариантов «припасовки» к двум «именованным» студентам 10-ти из 22-х «безымянных». Таким образом, вероятность попадания двух конкретных студентов к конкретному экзаменатору

Полученный результат надо умножить на 2, поскольку экзаменаторов двое: Не так уж неправы те, кто решает так: «то ли попадут, то ли нет, поэтому ».

 

 




Дата добавления: 2015-05-05; просмотров: 23 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Испытания машин| Формула полной вероятности и формула Байеса

lektsii.net - Лекции.Нет - 2014-2024 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав