Комбинаторика — Microsegment.ru

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

Формула для расчета числа размещений с повторениями:

\overline{A_n^k} = k^n

где:

A — всего возможных комбинаций,
k — всего элементов,
n — число элементов в выборке.

Число размещений и сочетаний без повторений

Формула для расчета числа размещений без повторений (в одной комбинации может встречаться любое количество одинаковых значений, например, последовательность 1, 1, 2):

A_n^k = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1) = \frac {n!}{(n-k)!} = C_n^k k!

в которой присутствует формула для расчета числа сочетаний без повторений (в одной комбинации могут встречаться только разные значения, например, последовательность 1, 3, 5):

C_n^k = \frac {n!}{k!(n-k)!} = C_n^{n-k}

где:

A — размещений без повторений,
C — сочетаний без повторений,
k — всего элементов,
n — число элементов в выборке,
k < n.

Частный случай:

A_k^k = k \cdot (k-1) \cdot ... \cdot (1) = k!

где:

k == n

Вероятность наступления события

Формула Лапласа (гипергеометрическое распределение случайной величины):

P_n(k) = \frac {C_M^k \cdot C_N^{n-k}}{C_{N+M}^n}

где:

N — первое множество элементов,
M — второе множество элементов,
n — количество мест размещения,
k — количество искомых элементов множества M в размещении.

Решение на Python:

import math
from fractions import Fraction # Дроби
from scipy import stats # библиотека статистики на SciPy
import statistics # статистика в стандартной библиотеке

# Использования функции Лапласа

# Расчет числа сочетаний без повторений
# с использованием библиотеки Math
def laplas_cnk(n, k):
    C = math.factorial(n)/(math.factorial(k)*(math.factorial(n - k)))
    return C

# Вероятность наступления события
# с использованием формулы Лапласа
def laplas(N, M, n, k):
    p = (laplas_cnk(M, k)*laplas_cnk(N, n - k))/laplas_cnk(N + M, n)
    return p

# Лаплас на Scipy.Stats для расчета вероятности 
# определенного диапазона непрерывной вероятности
def ranges_propability(X, P, arange):
    
    M = sum(X*P)/len(X)
    Mx2 = sum(X**2*P)/len(X)
    sigma = (Mx2 - M**2)**.5
    
    # Формула Лапласа
    p = stats.norm.cdf((arange[1] - M)/sigma) - stats.norm.cdf((arange[0] - M)/sigma)
    
    print("Случайная величина принимает значение от {:} до {:} с вероятностью".format(arange[0], arange[1]), round(p, 3))
    return p

# Лаплас на Scipy
#scipy.laplas()

# Вывод на печать
# k < n

k, n = 5, 7
print("Число размещений", k, "элементов по", n, "без повторений:", laplas_cnk(n, k))

N, M, n, k = 20, 30, 1, 0
print("Вероятность появления", n, "из", N, "элементов", "и", k, "из", M, "других элементов =", laplas(N, M, n, k))

Число размещений 5 элементов по 7 без повторений: 21.0
Вероятность появления 1 из 20 элементов и 0 из 30 других элементов = 0.6

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

Вероятность при бесконечно большом количестве последовательностей

Формула для расчета:

\lim_{n \to oo}(\frac{k}{n}) \to \frac{1}{2}

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

Python анализ Математика Теория вероятностей