Справочные материалы

«Комбинаторика»

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

Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок

P_n = n!,

где n! = 1 * 2 * 3... n.

Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.

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

A^m_n = n (n - 1)(n - 2)... (n - m + 1).

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

С ^m_n = n! / (m! (n - m)!).

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

A^m_n = P_mC ^m_n.

З а м е ч а н и е. Выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам. Например, если среди n элементов есть n₁ элементов одного вида, n₂ элементов другого вида и т.д., то число перестановок с повторениями

P_n (n₁, n₂,...) = n! / (n₁! n₂!...),

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

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

Литература:

Журбенко Л.Н., Никонова Г.А., Никонова Н.В., Нуриева С.Н., Дегтярева О.М. Математика в примерах и задачах: Учеб. пособие. — М.: ИНФРА М, 2009. — 373 с. — (Высшее образование).