09. Выборки: порядок и повторения — четыре вида
Выборка — это набор из элементов, взятых из данного множества. Вид выборки определяют два вопроса: «важен ли порядок?» и «можно ли брать один элемент несколько раз?». Ответы дают четыре вида выборок, и у каждого вида своя формула.
Что пригодится из прошлого: правила суммы и произведения — по ним мы будем считать; двоичные коды — там подмножество описывалось короткой записью из нулей и единиц. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Одни и те же буквы — четыре разные задачи
Пусть есть три буквы: . Нужно выбрать две. Слово «выбрать» может означать совсем разное. Четыре короткие истории:
1. Староста и заместитель. Из трёх человек выбираем старосту и его заместителя. Пара « — староста, — заместитель» отличается от пары « — староста, — заместитель», а один человек не может занять обе должности. Варианты: ab, ac, ba, bc, ca, cb — 6 вариантов.
2. Двухбуквенный код. На каждой из двух позиций стоит любая из трёх букв, буквы могут повторяться. Варианты: aa, ab, ac, ba, bb, bc, ca, cb, cc — 9 вариантов.
3. Два дежурных. Из трёх человек выбираем двух дежурных. « и » — то же самое, что « и »; одного человека дважды выбрать нельзя. Варианты: ab, ac, bc — 3 варианта.
4. Две порции мороженого. Есть три сорта. Берём две порции; порядок не важен, один и тот же сорт взять дважды можно. Варианты: aa, ab, ac, bb, bc, cc — 6 вариантов.
Соберём всё вместе:
- порядок важен, повторений нет — размещение без повторений: староста и заместитель, 6 вариантов;
- порядок важен, повторения разрешены — размещение с повторениями: двухбуквенный код, 9 вариантов;
- порядок не важен, повторений нет — сочетание без повторений: два дежурных, 3 варианта;
- порядок не важен, повторения разрешены — сочетание с повторениями: две порции мороженого, 6 вариантов.
Определения
Пусть — множество из элементов, а — целое неотрицательное число (): сколько элементов мы выбираем.
-выборка из — это последовательность элементов множества , не обязательно различных. Последовательность значит, что сначала мы записываем первый выбранный элемент, потом второй и так далее. Дальше всё зависит от того, обращаем мы внимание на этот порядок или нет. Если порядок не важен, выборка превращается в таблицу кратностей: сколько раз встретился каждый элемент (а в каком порядке — уже не помним).
Кратность. Через обозначим число появлений элемента в выборке — кратность элемента . Например, в выборке из множества кратности такие: , , . Сумма кратностей всех элементов равна .
Повторения.
- -выборка без повторений: для всех . Каждый элемент встречается не более одного раза.
- -выборка с повторениями: . Каждый элемент может встретиться несколько раз.
Слова «с повторениями» означают «повторения разрешены», а не «обязательно есть». Выборка без повторений — частный случай выборки с повторениями.
Порядок.
- Упорядоченная -выборка: существенна последовательность выбора. Две упорядоченные выборки равны, если у них одинаковая длина и на соответствующих местах стоят одинаковые элементы. Упорядоченную -выборку называют размещением из элементов по .
- Неупорядоченная -выборка: последовательность выбора несущественна, важно только, сколько раз встречается каждый элемент (его кратность). Две неупорядоченные выборки равны, если каждый элемент встречается в них одинаковое число раз. Неупорядоченную -выборку называют сочетанием из элементов по .
Проверка: выборки и — разные упорядоченные (на втором месте стоят разные буквы), но одна и та же неупорядоченная (в обеих , ).
Схема видов
выборки
├─ упорядоченные (размещения)
│ ├─ без повторений
│ └─ с повторениями
└─ неупорядоченные (сочетания)
├─ без повторений
└─ с повторениями
Верхний уровень — порядок, нижний — повторения. Четыре нижние строки — это четыре вида из списка выше.
Все четыре вида на одной картинке
Запишем все двухбуквенные слова из в таблицу: строка — первая буква, столбец — вторая.
вторая буква
a b c
первая a aa ab ac
буква b ba bb bc
c ca cb cc
- Вся таблица, 9 клеток — размещения с повторениями.
- Таблица без диагонали (клетки убраны), 6 клеток — размещения без повторений.
- Клетки на диагонали и над ней (), 6 клеток — сочетания с повторениями: клетки и — зеркальные, они описывают один и тот же набор, поэтому берём по одной из каждой пары.
- Клетки строго над диагональю (), 3 клетки — сочетания без повторений.
Видно, как виды связаны между собой:
зеркальные пары (один набор):
ab ↔ ba ac ↔ ca bc ↔ cb
на диагонали (сами себе пара):
aa bb cc
размещения без повторений:
3 пары · 2 клетки = 6
размещения с повторениями:
6 клеток + 3 диагональные = 9
сочетания без повторений:
3 пары = 3
сочетания с повторениями:
3 пары + 3 диагональные = 6
Обозначения
Для числа выборок каждого вида в курсе принята своя запись:
- — число размещений без повторений из элементов по .
- — число размещений с повторениями из элементов по .
- (или ) — число сочетаний без повторений из элементов по .
- (или ) — число сочетаний с повторениями из элементов по .
Волнистая черта сверху означает «повторения разрешены». В других учебниках встречаются иные обозначения (например, для размещений без повторений); смысл тот же.
По нашему списку для , получаем
Откуда берутся формулы для произвольных и , мы выясним в следующих главах: размещения, перестановки, сочетания, сочетания с повторениями.
Как определить вид выборки по условию
Задайте себе два вопроса.
Вопрос 1. Изменится ли результат, если поменять выбранные элементы местами? Если изменится — порядок важен (размещение). Если нет — порядок не важен (сочетание).
Вопрос 2. Можно ли взять один и тот же элемент более одного раза? Если можно — с повторениями, если нет — без повторений.
Пример. «Из 20 учеников выбрать старосту и заместителя»: староста и заместитель — разные должности, значит, порядок важен; один ученик не может занять обе должности, значит, повторений нет. Это размещение без повторений.
Особые случаи
- При выборка пустая: она одна, и никаких выборов делать не нужно.
- Размещения и сочетания без повторений существуют только при : нельзя выбрать пять разных элементов из трёх. Выборок с повторениями при любом бывает много: набор из трёх элементов позволяет составить и слово из пяти букв.
- Множество нумерует элементы, но порядок в самом множестве не важен. Это не мешает размещениям: порядок возникает в выборке, а не в множестве.
Частые ошибки
- «Выбрать» всегда значит «неупорядоченно». Нет: выбор старосты и заместителя упорядочен.
- Считать, что с повторениями — значит «обязательно с повторами». Выборка тоже допустима в схеме «с повторениями».
- Путать выборку и подмножество. Подмножество — это сочетание без повторений (порядок не важен, повторов нет), которое описывается кодом из нулей и единиц. Выборка в общем случае может содержать повторы.
- Забывать, что и — разные размещения. Порядок меняет результат.
Проверь себя
1. Определите вид выборки (порядок важен? повторения разрешены?).
- (а) Из 20 учеников выбрать двух дежурных.
- (б) Из 20 учеников выбрать старосту и его заместителя.
- (в) Составить трёхбуквенное слово (не обязательно осмысленное) из букв алфавита.
- (г) Купить пять пирожных четырёх видов (порядок покупки не важен, одинаковые пирожные разрешены).
- (д) Набрать четырёхзначный код домофона.
Решение
- (а) Дежурные неразличимы по должности, порядок не важен; одного ученика дважды выбрать нельзя. Сочетание без повторений.
- (б) Должности разные — порядок важен; повторений нет. Размещение без повторений.
- (в) Порядок букв важен («кот» и «ток» разные слова), буквы повторять можно. Размещение с повторениями.
- (г) Порядок покупки не важен; одинаковые пирожные разрешены. Сочетание с повторениями.
- (д) Порядок цифр важен; цифры повторять можно. Размещение с повторениями.
2. Выпишите все сочетания с повторениями из элементов по и все размещения без повторений из по . Сколько их?
Решение
Сочетания с повторениями (важно только, сколько раз встречается каждая буква): xxx, xxy, xyy, yyy — их 4. Размещений без повторений из двух элементов по три нет: из двух разных букв нельзя составить слово длины , не повторяя буквы. Это пример случая : их .
3. Выборки , и из множества : какие из них равны как упорядоченные, а какие — как неупорядоченные?
Решение
Как упорядоченные — все три разные: на соответствующих местах стоят разные буквы. Как неупорядоченные — все три равны: в каждой и .
Итог
- Выборка из элементов по — последовательность из элементов множества; вид определяют два вопроса: порядок и повторения.
- Размещение — упорядоченная выборка, сочетание — неупорядоченная; каждая бывает без повторений и с повторениями.
- Для , четыре вида дают , , , вариантов.
- Обозначения: , , , ; волна — «повторения разрешены».
