Число размещений из n элементов по m

Теория вероятности .

События, которые происходят реально или в нашем воображении, можно разделить на 3 группы. Это достоверные события, которые обязательно произойдут, невозможные события и случайные события. Теория вероятностей изучает случайные события, т.е. события, которые могут произойти или не произойти.

Что изучает эта наука? Многим в голову наверняка пришли мысли вроде «вероятность дождя велика», «вероятность выигрыша в лотерею мала», «орёл и решка выпадают с вероятностью 50 на 50» и т.п. Но тогда сразу возникает вопрос, при чём здесь наука? Пожалуйста, прямо сейчас возьмите в руки монету и скажите, какой гранью она выпадет после броска? …Совсем не похоже на теорию – скорее какое-то гадание….

И действительно, обывательское понимание вероятности больше смахивает на некое предсказание, часто с изрядной долей мистицизма и суеверий. Теория же вероятностей изучает вероятностные закономерности массовыходнородных случайных событий. То есть, у неё нет цели что-либо угадать, например, результат броска той же монеты в единичном эксперименте. Однако если одну и ту же монету в одинаковых условиях подбрасывать сотни и тысячи раз, то будет прослеживаться чёткая закономерность, описываемая вполне жёсткими законами.

Объектом изучения теории вероятностей являются события и их вероятности.

Другой пример. Вокруг каждого из нас летают молекулы воздуха. Некоторые из них обладают высокой, некоторые средней, а некоторые – низкой скоростью. Не имеет смысла угадывать скорость отдельно взятых молекул; но их массовый учёт находит самое широкое применение в теоретических и прикладных физических исследованиях. Обратите внимание, что самолёты «умеют» летать, газовые и паровые котлы обычно не взрываются, а чайники при кипении не скачут по кухне. За многими и многими, казалось бы, обыденными фактами и событиями кроются серьёзные вероятностно-статистические расчёты.

Или пример попроще. Если вы приобретёте лотерейный билет, то вряд ли что-то выиграете и совсем невероятно, что сорвёте крупный куш. Но организатор лотереи даже при случайном розыгрыше тиража (извлечение пронумерованных шариков и т.п. либо если участники сами угадывают номера) гарантированно и с высокой точностью знает, сколько билетов выиграют/проиграют, и, понятно, остаётся в прибыли. Лотереи часто называют обманом, однако парадокс состоит в том, что эта гарантия строго обоснована теорией; рАвно, как и житейская фраза «всё равно ничего не выиграю». Думаю, теперь все поняли правильный способ заработка на лотереях =) Впрочем, мы ещё вернёмся к «секретам» выигрыша в рулетку и различные лотереи.

Да, кстати подумайте ещё над одной насущной задачей: многие из нас за жизнь сдают десятки экзаменов, и практически всегда имеет место следующая ситуация: часть вопросов студент знает (либо заготовлены шпоры), а часть вопросов – не знает (либо плавает как мастер спорта). Наступает день «X»: утро, коридор с 10-15 однокурсниками и дверь, за которой на столе лежит полный комплект билетов. В каком случае вероятнее сдать экзамен – если идти «в первых рядах», «в серединке» или если зайти в аудиторию в числе последних? …Изучаем теорию вероятностей!

Зачем нужна теория вероятности

Исторически потребность исследования этих проблем возникла в XVII веке в связи с развитием и профессионализацией азартных игр и появлением казино. Это было реальное явление, которое требовало своего изучения и исследования.

Игра в карты, кости, рулетку создавала ситуации, когда могло произойти любое из конечного числа равновозможных событий. Возникла необходимость дать числовые оценки возможности наступления того или иного события.

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

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

Комбинаторика – раздел математики, в котором изучаются задачи на составление различных комбинаций из конечного числа элементов и подсчёт всех возможных таких комбинаций. Объекты, конструируемые по этим правилам из элементов данного множества М, называются комбинаторными конфигурациями. Комбинаторными конфигурациями могут быть упорядоченные или неупорядоченные подмножества множества М, совокупности повторяющихся элементов и т.п.

Правило суммы. Пусть в множестве есть элементов, в множестве есть элементов и эти множества не пересекаются. Тогда существует способов выбрать один элемент, имеющийся либо в , либо в .

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

Правило произведения. Пусть множества и состоят из и элементов соответственно. Тогда имеется способов выбрать пару , где и .

Задача 1. В компьютере каждый символ (буква, цифра, специальный знак) кодируется последовательностью из восьми 0 и 1, например:

01000110 — код буквы «F»;

00110010 — код цифры «2» и т.д.

Сколько различных символов можно закодировать таким образом?

Другими словами, сколько существует различных двоичных кодов длины 8?

Выстраивая комбинацию из восьми нулей и единиц, мы можем выбрать первую цифру двумя способами, после чего вторую цифру — тоже двумя способами и т.д. Всего получаем 2 • 2 • ... •2 = 2⁸ = 256 комбинаций. Именно столько символов содержит так называемая таблица ASCII, давно ставшая стандартом для представления символов в памяти компьютера (сейчас ей на смену пришли более длинные 16-разрядные коды, позволяющие кодировать уже 2¹⁶ = 65536 различных символов).

Выписывать все 256 комбинаций мы здесь не будем, напишем только начало и конец этой последовательности:

00000000; 00000001; 00000010;

11111110; 11111111.

Здесь порядок необходим, поскольку иначе мы рискуем потерять какие-то из комбинаций или выписать некоторые из них повторно

Еще один пример иллюстрирует применение двух комбинаторных правил — умножения и сложения — вместе.

Задача 2. Сколькими способами можно посадить шестерых школьников на скамейку так, чтобы Коля и Оля оказались рядом?

Будем считать, что на скамейке 6 пустых мест. Посадить на одно из них Колю можно шестью различными способами, после чего посадить рядом с ним Олю можно… одним или двумя различными способами. Это зависит от того, куда мы посадили Колю — на крайнее место или нет. Самое время применить правило сложения. Разобьем все искомые комбинации на два класса:

1-й класс: Коля сидит на краю, Оля рядом с ним;

2-й класс: Коля сидит где-то в середине, Оля рядом с ним.

Заметим, что эти классы действительно не пересекаются и исчерпывают все комбинации — ведь, в конце концов, Коля сидит либо на краю, либо

где-то в середине. Посчитаем число комбинаций в 1-ом классе: место с краю для Коли можно выбрать двумя способами, после чего Олю можно посадить рядом с ним только одним способом, после чего оставшиеся 4 места можно занять 4-3-2-1 способами. Значит, в этом классе будет

2-1-4-3-2-1 = 48 комбинаций.

Посчитаем число исходов во 2-ом классе: место в середине скамейки для Коли можно выбрать четырьмя способами, после чего Олю можно посадить рядом с ним двумя способами, после чего оставшиеся 4 места можно занять 4-3-2-1 способами. Значит, в этом классе будет

4-2-4-3-2-1 = 192 комбинации.

Итого по правилу сложения 48 + 192 = 240 способов

правило вычитания: при подсчете комбинаций, обладающих заданным свойством, иногда проще найти количество комбинаций, которые этим свойством НЕ обладают, и вычесть его из общего количества комбинаций.

Задача 3. Найдите количество трехзначных чисел, в записи которых есть хотя бы один 0.

Воспользуемся правилом вычитания. Сначала найдем количество всех трехзначных чисел - это можно сделать и без всякой комбинаторики - их будет 999-99=900. Теперь найдем, сколько из них не содержат ни одного 0: на первое место можно поставить любую из девяти цифр, на второе - любую из девяти цифр и на третье - любую из девяти цифр (каждый раз исключаем 0). Всего по правилу умножения будет вариантов. А теперь найдем ответ по правилу вычитания:

900-729= 171 столько трехзначных чисел содержат хотя бы один 0.

В комбинаторике принято каждому виду комбинаций давать специальное название.

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

Сейчас мы познакомимся с тремя такими видами — перестановками, размещениями и сочетаниями.

Перестановки из n элементов

Определение 1 . Перестановкой из n элементов называется любой упорядоченный набор этих элементов.

Обозначение:

Пример. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3}: это (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2). Число перестановок вычисляется по формуле:

P_n=n!. - число различных перестановок из n элементов

Замечание: n!=1*2*3*...*n (читается: "эн факториал"), кроме того полагают, что 0!=1.

Определение 2. n!- это произведение n последовательных чисел.

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

Решение

:эта задача о числе перестановок семи разных книг. Имеется P₇=7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

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

В перестановках с повторениями, как и в «обычных» перестановках, участвует сразу всё множество объектов, но есть одно но: в данном множестве один или большее количество элементов (объектов) повторяются. Число перестановок с повторениями вычисляется по формуле:

Р_n= - число перестановок с повторениями

Задача 2. Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами:

К, О, Л, О, К, О, Л, Ь, Ч, И, К?

Решение: Всё предельно просто – всего: 11 карточек, среди которых буква:

К – повторяется 3 раза;
О – повторяется 3 раза;
Л – повторяется 2 раза;
Ь – повторяется 1 раз;
Ч – повторяется 1 раз;
И – повторяется 1 раз.

Проверка: 3 + 3 + 2 + 1 + 1 + 1 = 11, что и требовалось проверить.

По формуле количества перестановок с повторениями:
различных буквосочетаний можно получить. Больше полумиллиона!

На практике вполне допустимо не записывать общую формулу и, кроме того, опускать единичные факториалы:

Но предварительные комментарии о повторяющихся буквах обязательны!

Ответ: 554400

Число размещений из n элементов по m

Определение 3 . Размещением из n элементов по m называется любой упорядоченный набор из m различных элементов, выбранных из n элементов множества.

Обозначение: А_n^m

Пример . Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком .

Число размещений вычисляется по формуле:

- число размещений из n элементов по m элементов

Вывод формулы:

Задача 3. Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные?
Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:

Размещения с повторениями

Из множества, состоящего из элементов, выбирается элементов, при этом важен порядок элементов в каждой выборке. и любой объект исходного множества мы можем выбирать сколько угодно раз.

Число размещений с повторениями вычисляется по формуле:

= - число размещений с повторениями

Когда так бывает? Типовым примером является кодовый замок с несколькими дисками, но по причине развития технологий актуальнее рассмотреть его цифрового потомка:

Задача 4. Сколько существует четырёхзначных пин-кодов?

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

если банкомат «съедает» карточку после третьей неудачной попытки ввода пин-кода, то шансы подобрать его наугад весьма призрачны.

Дата добавления: 2021-01-20; просмотров: 144; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 Следующая ⇒

Мы поможем в написании ваших работ!