bulgakov

10. Размещения: nʳ и n(n−1)…(n−r+1)

Размещение — это упорядоченная выборка: мы заполняем rr мест по очереди. Если элементы можно повторять, на каждое место есть nn вариантов, и размещений nrn^r. Если нельзя — на каждое следующее место вариантов на один меньше: n(n−1)(n−2)⋯(n−r+1)n(n-1)(n-2)\cdots(n-r+1).

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

Размещение — это слово

Пусть A={a1,a2,…,an}A=\{a_1,a_2,\dots,a_n\} — алфавит из nn букв. Упорядоченная rr-выборка из AA — это слово длины rr: на первом месте стоит какая-то буква, на втором какая-то буква и так далее. Поэтому считать размещения — значит считать слова. Различны ли буквы в слове — как раз вопрос «с повторениями или без».

Размещения с повторениями: nrn^r

Начнём с алфавита {a,b,c}\{a,b,c\} и слов длины 22. Выберем первую букву (три способа), затем вторую (снова три способа — повторять можно):

старт
├── a ── aa  ab  ac
├── b ── ba  bb  bc
└── c ── ca  cb  cc

Три ветки по три слова: 3⋅3=93\cdot3=9.

Теорема (а). Число размещений с повторениями из nn элементов по rr равно

[n]~r=nr.\boxed{\widetilde{[n]}_r=n^r}.

Почему. Рассмотрим слова длины rr в алфавите из nn букв. Число таких слов совпадает с числом размещений с повторениями. На первом месте может стоять любая из nn букв. На втором месте тоже любая из nn букв: повторять можно, ограничений нет. То же для каждого следующего места. Рисуем ячейки и под каждой записываем число вариантов:

  1-е       2-е           r-е
┌──────┐  ┌──────┐      ┌──────┐
│      │  │      │  …   │      │
└──────┘  └──────┘      └──────┘
   n         n             n

По правилу произведения получаем n⋅n⋯nn\cdot n\cdots n (rr множителей), то есть nrn^r.

Для двоичного алфавита {0,1}\{0,1\} получается 2r2^r кодов — это в точности вывод из первой главы.

Размещения без повторений: n(n−1)⋯(n−r+1)n(n-1)\cdots(n-r+1)

Возьмём пять букв a,b,c,d,ea,b,c,d,e и составим слова из трёх разных букв. Следим за тем, какие буквы ещё свободны:

Схема
свободные буквы → способов
шаг 1:  a b c d e → 5
        выбрали c
шаг 2:  a b d e   → 4
        выбрали e
шаг 3:  a b d     → 3
        выбрали a
слово:  c e a

На первом шаге — любая из 55 букв. На втором — любая, кроме уже выбранной: 44. На третьем — любая, кроме двух выбранных: 33. Итого 5⋅4⋅3=605\cdot4\cdot3=60 слов.

Теорема (б). Число размещений без повторений из nn элементов по rr равно

[n]r=n(n−1)(n−2)⋯(n−r+1).\boxed{[n]_r=n(n-1)(n-2)\cdots(n-r+1)}.

Почему. Слова длины rr из nn букв, в которых буквы не повторяются, считаем по местам. Первое место: любая из nn букв — nn способов. Второе: любая, кроме первой, — n−1n-1 способ. Третье: любая, кроме первых двух, — n−2n-2. Каждый раз число свободных букв на одну меньше. К rr-му месту уже занято r−1r-1 букв, поэтому свободных остаётся n−(r−1)=n−r+1n-(r-1)=n-r+1.

Важно: какие буквы свободны, зависит от прежних выборов, но сколько их — нет. Поэтому правило произведения применимо (как с цифрами в главе про правила суммы и произведения).

Как читать произведение

В записи n(n−1)⋯(n−r+1)n(n-1)\cdots(n-r+1) ровно rr множителей: первый — nn, каждый следующий на единицу меньше, последний — n−r+1n-r+1. Последний множитель — не n−rn-r, это частая ошибка. Проверим на малых rr:

  • r=1r=1: один множитель nn — выбрать одну букву можно nn способами;
  • r=2r=2: n(n−1)n(n-1);
  • r=3r=3: n(n−1)(n−2)n(n-1)(n-2), последний множитель n−3+1=n−2n-3+1=n-2.

Сравнение двух видов

Для алфавита из пяти букв (n=5n=5):

rr 0 1 2 3 4 5 6
[5]r[5]_r 1 5 20 60 120 120 0
5r5^r 1 5 25 125 625 3125 15625

Что видно в таблице:

  • при r=0r=0 размещение единственное — пустое слово;
  • [5]5=120=5![5]_5=120=5!: когда мест столько же, сколько букв, получается число перестановок — об этом следующая глава;
  • при r=6>5r=6>5 без повторений слов нет: в произведении 5⋅4⋅3⋅2⋅1⋅05\cdot4\cdot3\cdot2\cdot1\cdot0 появляется нулевой множитель, ведь свободных букв не осталось;
  • при r≥2r\ge2 слов с повторениями строго больше, чем без повторений (при r=0r=0 и r=1r=1 числа совпадают, это видно в таблице). Разница при r=2r=2 — слова вроде aa,bb,…aa,bb,\dots: их ровно nn, и n2−n=n(n−1)n^2-n=n(n-1) (это диагональ таблицы из главы про виды выборок).

Примеры

1. Код из четырёх цифр. Повторять можно: 104=10 00010^4=10\,000 кодов. Если все цифры различны: 10⋅9⋅8⋅7=504010\cdot9\cdot8\cdot7=5040.

2. Призовая тройка. Восемь бегунов; золото, серебро и бронза — три разные награды, поэтому порядок важен, а один человек не может получить две награды. [8]3=8⋅7⋅6=336[8]_3=8\cdot7\cdot6=336 способов.

3. Флаг из трёх горизонтальных полос. Есть пять красок. Если цвета полос могут совпадать, флагов 53=1255^3=125. Если все три полосы разного цвета, 5⋅4⋅3=605\cdot4\cdot3=60.

4. Слова из разных букв. Сколько существует слов из четырёх различных букв русского алфавита (в нём 3333 буквы), не обязательно осмысленных? 33⋅32⋅31⋅30=982 08033\cdot32\cdot31\cdot30=982\,080.

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

  • nrn^r вместо rnr^n. Основание — число вариантов для одного места, показатель — число мест. Двухбуквенных слов из трёх букв 32=93^2=9, а трёхбуквенных слов из двух букв 23=82^3=8.
  • Последний множитель n−rn-r вместо n−r+1n-r+1. В [n]r[n]_r ровно rr множителей.
  • Забыть, что при r>nr>n без повторений слов нет.
  • Считать «без повторений» эквивалентным «порядок не важен». Это два разных вопроса: у размещений порядок важен всегда; повторения разрешены или нет — отдельное условие.

Проверь себя

1. Сколько существует двоичных слов длины 66?

Решение

Алфавит {0,1}\{0,1\}: n=2n=2, r=6r=6, повторения разрешены. 26=642^6=64.

2. Сколько существует трёхбуквенных слов с различными буквами в латинском алфавите (2626 букв)?

Решение

Повторений нет: 26⋅25⋅24=1560026\cdot25\cdot24=15600.

3. В турнире участвуют десять команд. Сколькими способами можно распределить первое, второе и третье места?

Решение

Места различны, одна команда не может занять два места: [10]3=10⋅9⋅8=720[10]_3=10\cdot9\cdot8=720.

4. Вычислите [7]3[7]_3, [7]7[7]_7 и [7]8[7]_8.

Решение

[7]3=7⋅6⋅5=210[7]_3=7\cdot6\cdot5=210. [7]7=7⋅6⋅5⋅4⋅3⋅2⋅1=5040[7]_7=7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1=5040. У [7]8[7]_8 восемь множителей, последний равен 7−8+1=07-8+1=0, поэтому [7]8=0[7]_8=0: из семи букв нельзя составить слово из восьми разных.

Итог

  • Размещение — слово длины rr в алфавите из nn букв.
  • С повторениями: на каждое место nn вариантов, всего [n]~r=nr\widetilde{[n]}_r=n^r.
  • Без повторений: n,  n−1,  n−2,…n,\;n-1,\;n-2,\dots, всего [n]r=n(n−1)⋯(n−r+1)[n]_r=n(n-1)\cdots(n-r+1) — ровно rr множителей.
  • При r>nr>n размещений без повторений нет; при r=nr=n получается n!n!.
ПрактикаЗагружаем тест…