4.3 Основные формулы комбинаторики

Перестановками называют множества, состоящие из одних и тех же п различных элементов и отличающиеся друг от друга только порядком их расположения. Число всех возможных перестановок из п элементов равно P_n=n!, где n!=1·2·3... ·п.

Замечание. По определению полагают 0!=1.

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

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

Если среди п элементов есть п₁ элементов одного вида, п₂ элементов другого вида и т.д., то число перестановок с повторениями определяется формулой

, где п₁ + п₂+...+п_k=n.

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

Число сочетаний с повторениями из n элементов по m элементов равно числу сочетаний без повторений из n+m–1 элементов по m элементов, т.е. .

При решении задач комбинаторики используют следующие правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов т способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m+ n способами.

Правило произведения. Если объект А можно выбрать из совокупности объектов т способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана т·п способами.

4.4. Теоремы умножения и сложения вероятностей

Опр: Пусть события А и В называются независимыми, если вероятность каждого из них не зависит от того произошло другое событие или нет.

Опр: События А и В называются зависимыми, если вероятность каждого из них зависит от того, произошло или нет другое событие.

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

Р (В\А) или Р_А(В)

Теорема умножения вероятностей.

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

Р(АВ)=Р(А)·Р(В\А) или Р(АВ)=Р(В) ·Р(А\В)

Вероятность произведения двух независимых событий А и В равна произведению их вероятности: Р(АВ)=Р(А) ·Р(В).

Если события А₁, А₂, …., А_n – зависимы, то Р(А₁·А₂·…А_n)=Р(А₁) ·Р(А₂\А₁) ·Р(А₃\А₁А₂) ·…·Р(А_n\А₁А₂А₃…А_n-1)

Если события А₁, А₂, …., А_n – независимы, то Р(А₁·А₂·…·А_n)=Р(А₁) ·Р(А₂) ·…·Р(А_n).

Вероятность появления хотя бы одного события из n событий определяется формулой Р(А₁+А₂+…А_n)=1–Р(··...·)

Теорема сложения вероятности.

Вероятность суммы двух совместных событий равна сумме вероятности этих событий, без вероятности их совместного наступления:

Р(А+В)=Р(А)+Р(В)–Р(АВ)

Если события несовместные вероятность суммы двух несовместных событий равна сумме вероятности этих событий Р(А+В)=Р(А)+Р(В)

Сумма вероятности событий А₁А₂А₃…А_n,образующих полную группу равна единице: Р(А₁)+Р(А₂)+…+Р(А_n)=1