bulgakov

09. Выборки: порядок и повторения — четыре вида

Выборка — это набор из rr элементов, взятых из данного множества. Вид выборки определяют два вопроса: «важен ли порядок?» и «можно ли брать один элемент несколько раз?». Ответы дают четыре вида выборок, и у каждого вида своя формула.

Что пригодится из прошлого: правила суммы и произведения — по ним мы будем считать; двоичные коды — там подмножество описывалось короткой записью из нулей и единиц. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Одни и те же буквы — четыре разные задачи

Пусть есть три буквы: A={a,b,c}A=\{a,b,c\}. Нужно выбрать две. Слово «выбрать» может означать совсем разное. Четыре короткие истории:

1. Староста и заместитель. Из трёх человек выбираем старосту и его заместителя. Пара «aa — староста, bb — заместитель» отличается от пары «bb — староста, aa — заместитель», а один человек не может занять обе должности. Варианты: ab, ac, ba, bc, ca, cb — 6 вариантов.

2. Двухбуквенный код. На каждой из двух позиций стоит любая из трёх букв, буквы могут повторяться. Варианты: aa, ab, ac, ba, bb, bc, ca, cb, cc — 9 вариантов.

3. Два дежурных. Из трёх человек выбираем двух дежурных. «aa и bb» — то же самое, что «bb и aa»; одного человека дважды выбрать нельзя. Варианты: ab, ac, bc — 3 варианта.

4. Две порции мороженого. Есть три сорта. Берём две порции; порядок не важен, один и тот же сорт взять дважды можно. Варианты: aa, ab, ac, bb, bc, cc — 6 вариантов.

Соберём всё вместе:

  • порядок важен, повторений нет — размещение без повторений: староста и заместитель, 6 вариантов;
  • порядок важен, повторения разрешены — размещение с повторениями: двухбуквенный код, 9 вариантов;
  • порядок не важен, повторений нет — сочетание без повторений: два дежурных, 3 варианта;
  • порядок не важен, повторения разрешены — сочетание с повторениями: две порции мороженого, 6 вариантов.

Определения

Пусть A={a1,a2,…,an}A=\{a_1,a_2,\dots,a_n\} — множество из nn элементов, а rr — целое неотрицательное число (r∈Z≥0r\in\mathbb Z_{\ge0}): сколько элементов мы выбираем.

rr-выборка из AA — это последовательность x1,x2,…,xrx_1,x_2,\dots,x_r элементов множества AA, не обязательно различных. Последовательность значит, что сначала мы записываем первый выбранный элемент, потом второй и так далее. Дальше всё зависит от того, обращаем мы внимание на этот порядок или нет. Если порядок не важен, выборка превращается в таблицу кратностей: сколько раз встретился каждый элемент (а в каком порядке — уже не помним).

Кратность. Через d(a)d(a) обозначим число появлений элемента a∈Aa\in A в выборке — кратность элемента aa. Например, в выборке b,a,bb,a,b из множества {a,b,c}\{a,b,c\} кратности такие: d(a)=1d(a)=1, d(b)=2d(b)=2, d(c)=0d(c)=0. Сумма кратностей всех элементов равна rr.

Повторения.

  • rr-выборка без повторений: 0≤d(a)≤10\le d(a)\le1 для всех a∈Aa\in A. Каждый элемент встречается не более одного раза.
  • rr-выборка с повторениями: 0≤d(a)≤r0\le d(a)\le r. Каждый элемент может встретиться несколько раз.

Слова «с повторениями» означают «повторения разрешены», а не «обязательно есть». Выборка без повторений — частный случай выборки с повторениями.

Порядок.

  • Упорядоченная rr-выборка: существенна последовательность выбора. Две упорядоченные выборки равны, если у них одинаковая длина и на соответствующих местах стоят одинаковые элементы. Упорядоченную rr-выборку называют размещением из nn элементов по rr.
  • Неупорядоченная rr-выборка: последовательность выбора несущественна, важно только, сколько раз встречается каждый элемент (его кратность). Две неупорядоченные выборки равны, если каждый элемент встречается в них одинаковое число раз. Неупорядоченную rr-выборку называют сочетанием из nn элементов по rr.

Проверка: выборки b,a,bb,a,b и b,b,ab,b,a — разные упорядоченные (на втором месте стоят разные буквы), но одна и та же неупорядоченная (в обеих d(a)=1d(a)=1, d(b)=2d(b)=2).

Схема видов

выборки
├─ упорядоченные (размещения)
│    ├─ без повторений
│    └─ с повторениями
└─ неупорядоченные (сочетания)
     ├─ без повторений
     └─ с повторениями

Верхний уровень — порядок, нижний — повторения. Четыре нижние строки — это четыре вида из списка выше.

Все четыре вида на одной картинке

Запишем все двухбуквенные слова из a,b,ca,b,c в таблицу: строка — первая буква, столбец — вторая.

               вторая буква
                 a    b    c
первая    a     aa   ab   ac
буква     b     ba   bb   bc
          c     ca   cb   cc
  • Вся таблица, 9 клеток — размещения с повторениями.
  • Таблица без диагонали (клетки aa,bb,ccaa,bb,cc убраны), 6 клеток — размещения без повторений.
  • Клетки на диагонали и над ней (aa,ab,ac,bb,bc,ccaa,ab,ac,bb,bc,cc), 6 клеток — сочетания с повторениями: клетки abab и baba — зеркальные, они описывают один и тот же набор, поэтому берём по одной из каждой пары.
  • Клетки строго над диагональю (ab,ac,bcab,ac,bc), 3 клетки — сочетания без повторений.

Видно, как виды связаны между собой:

Схема
зеркальные пары (один набор):
  ab ↔ ba    ac ↔ ca    bc ↔ cb
на диагонали (сами себе пара):
  aa         bb         cc

размещения без повторений:
  3 пары · 2 клетки = 6
размещения с повторениями:
  6 клеток + 3 диагональные = 9
сочетания без повторений:
  3 пары = 3
сочетания с повторениями:
  3 пары + 3 диагональные = 6

Обозначения

Для числа выборок каждого вида в курсе принята своя запись:

  1. [n]r[n]_r — число размещений без повторений из nn элементов по rr.
  2. [n]~r\widetilde{[n]}_r — число размещений с повторениями из nn элементов по rr.
  3. (nr)\dbinom nr (или CnrC_n^r) — число сочетаний без повторений из nn элементов по rr.
  4. (nr)~\widetilde{\dbinom nr} (или C~nr\widetilde C_n^r) — число сочетаний с повторениями из nn элементов по rr.

Волнистая черта сверху означает «повторения разрешены». В других учебниках встречаются иные обозначения (например, AnrA_n^r для размещений без повторений); смысл тот же.

По нашему списку для n=3n=3, r=2r=2 получаем

[3]2=6,[3]~2=9,(32)=3,(32)~=6.[3]_2=6,\qquad \widetilde{[3]}_2=9,\qquad \binom32=3,\qquad \widetilde{\binom32}=6.

Откуда берутся формулы для произвольных nn и rr, мы выясним в следующих главах: размещения, перестановки, сочетания, сочетания с повторениями.

Как определить вид выборки по условию

Задайте себе два вопроса.

Вопрос 1. Изменится ли результат, если поменять выбранные элементы местами? Если изменится — порядок важен (размещение). Если нет — порядок не важен (сочетание).

Вопрос 2. Можно ли взять один и тот же элемент более одного раза? Если можно — с повторениями, если нет — без повторений.

Пример. «Из 20 учеников выбрать старосту и заместителя»: староста и заместитель — разные должности, значит, порядок важен; один ученик не может занять обе должности, значит, повторений нет. Это размещение без повторений.

Особые случаи

  • При r=0r=0 выборка пустая: она одна, и никаких выборов делать не нужно.
  • Размещения и сочетания без повторений существуют только при r≤nr\le n: нельзя выбрать пять разных элементов из трёх. Выборок с повторениями при любом rr бывает много: набор из трёх элементов позволяет составить и слово из пяти букв.
  • Множество {a1,…,an}\{a_1,\dots,a_n\} нумерует элементы, но порядок в самом множестве не важен. Это не мешает размещениям: порядок возникает в выборке, а не в множестве.

Частые ошибки

  • «Выбрать» всегда значит «неупорядоченно». Нет: выбор старосты и заместителя упорядочен.
  • Считать, что с повторениями — значит «обязательно с повторами». Выборка a,ba,b тоже допустима в схеме «с повторениями».
  • Путать выборку и подмножество. Подмножество — это сочетание без повторений (порядок не важен, повторов нет), которое описывается кодом из нулей и единиц. Выборка в общем случае может содержать повторы.
  • Забывать, что a,ba,b и b,ab,a — разные размещения. Порядок меняет результат.

Проверь себя

1. Определите вид выборки (порядок важен? повторения разрешены?).

  • (а) Из 20 учеников выбрать двух дежурных.
  • (б) Из 20 учеников выбрать старосту и его заместителя.
  • (в) Составить трёхбуквенное слово (не обязательно осмысленное) из букв алфавита.
  • (г) Купить пять пирожных четырёх видов (порядок покупки не важен, одинаковые пирожные разрешены).
  • (д) Набрать четырёхзначный код домофона.
Решение
  • (а) Дежурные неразличимы по должности, порядок не важен; одного ученика дважды выбрать нельзя. Сочетание без повторений.
  • (б) Должности разные — порядок важен; повторений нет. Размещение без повторений.
  • (в) Порядок букв важен («кот» и «ток» разные слова), буквы повторять можно. Размещение с повторениями.
  • (г) Порядок покупки не важен; одинаковые пирожные разрешены. Сочетание с повторениями.
  • (д) Порядок цифр важен; цифры повторять можно. Размещение с повторениями.

2. Выпишите все сочетания с повторениями из элементов x,yx,y по 33 и все размещения без повторений из x,yx,y по 33. Сколько их?

Решение

Сочетания с повторениями (важно только, сколько раз встречается каждая буква): xxx, xxy, xyy, yyy — их 4. Размещений без повторений из двух элементов по три нет: из двух разных букв нельзя составить слово длины 33, не повторяя буквы. Это пример случая r>nr>n: их 00.

3. Выборки a,b,aa,b,a, a,a,ba,a,b и b,a,ab,a,a из множества {a,b}\{a,b\}: какие из них равны как упорядоченные, а какие — как неупорядоченные?

Решение

Как упорядоченные — все три разные: на соответствующих местах стоят разные буквы. Как неупорядоченные — все три равны: в каждой d(a)=2d(a)=2 и d(b)=1d(b)=1.

Итог

  • Выборка из nn элементов по rr — последовательность из rr элементов множества; вид определяют два вопроса: порядок и повторения.
  • Размещение — упорядоченная выборка, сочетание — неупорядоченная; каждая бывает без повторений и с повторениями.
  • Для n=3n=3, r=2r=2 четыре вида дают 66, 99, 33, 66 вариантов.
  • Обозначения: [n]r[n]_r, [n]~r\widetilde{[n]}_r, (nr)\binom nr, (nr)~\widetilde{\binom nr}; волна — «повторения разрешены».
ПрактикаЗагружаем тест…