Версия для печати

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

Рассмотрим совокупность \(n\) различных элементов

\[a_1, a_2, ..., a_n.\]

Произвольную упорядоченную выборку (возможно, с повторениями) из этих элементов

\[a_{{\alpha}_1}, a_{{\alpha}_2}, ..., a_{{\alpha}_m} (1 \le {\alpha}_k \le n; k=1, ..., m)\]

будем называть соединением.

 Например, при бросании монеты 10 раз выпадение герба (Г) и выпадение решки (Р) могут дать соединение

ГГГГРРГРРР.

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

Определим число \(A_n^m\) размещений из \(n\) элементов \(a_1, a_2, ..., a_n\) по \(m\).

Пусть \(a_{{\alpha}_1}, a_{{\alpha}_2}, ..., a_{{\alpha}_m}\) - всевозможные размещения, содержащие \(m\) элементов. Будем эти размещения строить последовательно. Сначала определим \(a_{{\alpha}_1}\) - первый элемент размещения. очевидно, из данной совокупности \(n\) элементов его можно выбрать \(n\) различными способами. После выбора первого элемента \(a_{{\alpha}_1}\), для второго элемента \(a_{{\alpha}_2}\) остается \(n-1\) способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. поэтому имеем

\[A_n^m=n(n-1)(n-2) \cdots [n-(m-1)]. \tag{1}\]

Вводя обозначение факториала

\[n!=1 \cdot 2 \cdot 3 \cdots n,\]

формулу (1) можно записать в следующем виде:

\[A_n^m= \frac{n!}{(n-m)!}. \tag{2}\]

Соединения из \(n\) элементов, каждое из которых содержит все \(n\) элементов и которые отличаются лишь порядком элементов, называются перестановками.

Очевидно, число перестановок из \(n\) элементов равно

\[A_n^n=n(n-1)(n-2) \cdots [n-(n-1)]=n!. \tag{3}\]

Условно считают, \(0!=1.\)

Обозначим через \(C_n^m\) из \(n\) элементов по \(m\).

Рассмотрим все допустимые сочетания наших элементов

\(a_{{\alpha}_1}, a_{{\alpha}_2}, ..., a_{{\alpha}_m};\)

Делая в каждом из них \(m!\) возможных перестановок их элементов, очевидно, получим все размещения из \(n\) элементов по \(m\). таким образом, имеем формулу

\[C_n^m \cdot m!=A_n^m;\]

отсюда

\[C_n^m=\frac {A_n^m}{m!}= \frac{n(n-1)(n-2) \cdots [n-(n-1)]}{m!}. \tag{4}\]

Формулу (4) можно представить также в виде

\[C_n^m = \frac {n!}{m! (n-m)!}. \tag{5}\]

Символ \(C_n^m\) обладает очевидным свойством

\[C_n^m=C_n^{n-m}. \tag{6}\]

Пример

Партия из 10 деталей содержит одну нестандартную. Какова вероятность, что при случайной выборке 5 деталей из этой партии все они будут стандартными (событие A)?

Здесь число всех случайных выборок \(n=C_{10}^5\), а число выборок, благоприятствующих событию \(A\) есть \(m=C_9^5.\) Таким образом, искомая вероятность равна

\[P(A)=\frac{C_9^5}{C_{10}^5}=\frac{9!}{5!4!} \cdot \frac{5!5!}{10!}=\frac12.\]

Похожие материалы (по тегу)

Авторизуйтесь, чтобы получить возможность оставлять комментарии