1.1.2. Бесповторные выборки
Представим себе, что имеется n каких-то предметов, из которых нужно составить выборку объема r. Выбор будем проводить по схеме:
– для выбора первого элемента имеется n способов,
– для выбора второго элемента осталось n - 1 способов,
– для выбора третьего элемента осталось n - 2 способа,
… … … … … … … … …
– для выбора k-го элемента осталось n – r + 1 способов.
Общее число способов, согласно комбинаторному принципу, равно произведению k сомножителей: n(n-1)(n-2)…(n-k+1). Такие комбинации встречаются часто и получили специальное название.
Размещениями из n элементов по k называются группы каких-то k предметов, взятых из этих n и отличающихся друг от друга либо составом, либо порядком их расположения в выборке. Таким образом, различными считаются размещения, в которых имеются или различные элементы, или, если все элементы одинаковы (одинаков состав), то различны порядки их расположения. Размещения из n элементов по k обычно обозначаются символом
A
= n(n-1)(n-2)
… (n-k+1).
Пример 1.2.
В студенческой группе 25 студентов. Требуется выбрать актив группы, состоящий из трех человек. Сколько различных комбинаций при этом возможно?
Решение
В этом случае выборки будут отличаться друг от друга либо составом, либо порядком расположения. Действительно, при изменении порядка следования выбранная “тройка” займет уже другие посты. Следовательно, общее число способов дают размещения из 25 по 3 :
А
= 252423
= 13 800.
Выясним, что получится при вычислении
А
.
Пользуясь общей формулой для числа
размещений, имеем А
= n(n-1)(n-2)…321.
Размещения из n элементов по n
называются перестановками из
n элементов и обозначаются:
=
123…n
=n!.
Символом
n! (n – факториал) обозначается
произведение всех целых положительных
чисел от 1 до n. Очевидно, что при n 2
справедливо следующее свойство: n! =
(n-1)! n . Чтобы это равенство имело смысл
при всех положительных целых значениях
n, по определению положим 0! = 1.
Пример 1.3.
С помощью перестановок можно решать
такие задачи: три человека могут сесть
за парту в аудитории 3! =
= 6 способами; десять человек встать в
очередь или разместиться за столом
может 10! различными способами (это число
больше 3 млн).
Выясним теперь вопрос о том, сколько
существует выборок объема r из n
элементов, которые отличаются между
собой хотя бы одним элементом. Группы
из n элементов по r, отличающиеся
только составом, называются сочетаниями
из n по r. Число таких различных
групп обозначается символом C
.
Получим формулу для подсчета всех
возможных сочетаний C
.
Обратим внимание на то, что если наряду
с каждым сочетанием рассматривать и
все перестановки из r составляющих
его элементов, то получим всевозможные
размещения. Таким образом, выполняется
равенство
,
отсюда
C
=
.
Преобразуем С
к более удобной для запоминания форме,
для этого умножим числитель и знаменатель
дроби на (n – r)!.
С
=
.
Из полученной формулы вытекает полезное
равенство: С
=С
.
Пример 1.4.
От студенческой группы в 25 человек нужно послать трех представителей на студенческую конференцию. Сколько возникнет различных способов это сделать?
Решение
При выборе студентов важен только состав выборки, а порядок их расположения – нет. Следовательно, общее число способов будет равно
При решении задач комбинаторики можно придерживаться следующей схемы рассуждений:
Выяснить, какие группы образуют выборки – повторные или бесповторные.
В случае бесповторных выборок рассмотреть, чем они отличаются – только составом, порядком или тем и другим.
Классификация выборок представлена на рис. 1.1.
Рис. 1.1.