1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 голосов)

Основные комбинаторные соотношения в теории вероятностей

 

В теории вероятностей, при подсчете числа исходов испытаний(попыток)  применяют следующие соотношения

Число перестановок по m элементов  из n различных элементов, в которых каждый элемент используется только один раз.

A_n^m=\frac{n!}{(n-m)!

В частности, число перестановок из n различных  элементов равно

Число перестановок  по m элементов по n различных элементов, в которых  каждый элемент может использоватся любое допустимое (от 0 до m) число раз

U(n,n)=n^m

Таким способом мы например высчитывали какой же запас автомобильных номеров может существовать при той или иной нумерации.

Число перестановок из n элементов, среди которых n1 первого вида, n2 второго вида,...nm m-ого вида, или число способов рзмещения n различных элементов по m различным ячейкам при условии, что в i-ой ячейке помещается ni(i=1,...,m) элементов

P(n;m_1,...m_k)=C_n^{m_1,....,m_k}

где

m_1+m_2+...+m_k=n

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

D(n,k)=C_n^k(n-k)![\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}]=C_n^kD_{n-k}

Значение D_{n-k} - есть субфакториал и  рассчитывается по реккуретной формуле

D_n=nD_{n-1}+(-1)^n

при D_0=1

Число сочетаний по m элементов из n различных элементов, в которых каждый элемент используется только один раз

C(n,m)=C_n^m

Число сочетаний по m элементов из n различных элементов, в которых каждый элемент может повторятся любое допустимое  (от 0 до m) число раз

f(n,m)=C_{n+m-1}^m=C_{n+m-1}^{n-1}

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

C_n^kC_{m-1}^{k-1}=C_n^{n-k}C_{m-1}^{k-1}\\\\(m\ge{k},1\le{k}\le{n}

а число всевозможных размещений

\sum_{k=1}^nC_n^{n-k}C_{m-1}^{k-1}=C_{n+m-1}^{n-1}=f(n,m)

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

A_n^kS(m,k), (m\ge{k},1\le{k}\le{n})

а число всевозможных размещений

\sum_{k=1}^nA_n^kS(m,k)=N^m=U(n,m)

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

S(m,k), (m\ge{k},1\le{k}\le{n})

а число всевозможных размещений

V(n,m)=\sum_{k=1}^nS(m,k)

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

p_m(k),(m\ge{k},1\le{k}\le{n})

а число всевозможных размещений

F(n,m)=\sum_{k=1}^np_m(k)

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

Ячейки, n Элементы,m
различные одинаковые
различные U(n,m) f(n,m)
одинаковые V(n,m) F(n,m)