bulgakov

33. Слова, содержащие все буквы алфавита

Чтобы посчитать слова длины rr, содержащие все nn букв алфавита, проще посчитать противоположное: слова, в которых каких-то букв не хватает. «Не хватает буквы aia_i» — это свойство pip_i, и принцип включений и исключений даёт ответ D(n,r)=∑k=0n(−1)k(nk)(n−k)rD(n,r)=\sum_{k=0}^{n}(-1)^k\dbinom nk(n-k)^r.

Что пригодится из прошлого: включения и исключения через свойства — формула E(0)=w(0)−w(1)+w(2)−…E(0)=w(0)-w(1)+w(2)-\dots; размещения с повторениями — слов длины rr в алфавите из mm букв ровно mrm^r; сочетания. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Задача

Задача. Найти количество слов длины rr в алфавите A={a1,a2,…,an}A=\{a_1,a_2,\dots,a_n\}, которые содержат все буквы алфавита. Обозначим число таких слов D(n,r)D(n,r).

Самый маленький случай: две буквы, три позиции

Алфавит {a,b}\{a,b\}, слова длины 33. Всего слов 23=82^3=8. Нужные нам слова содержат и aa, и bb; «плохие» слова — те, где одной из букв нет: aaaaaa (нет bb) и bbbbbb (нет aa). Нужные слова: aab, aba, abb, baa, bab, bba. Их 8−2=68-2=6.

Тот же результат даёт формула: 23−2⋅13+03=62^3-2\cdot1^3+0^3=6. Разберём, откуда она берётся.

Решение по формуле включений и исключений

Пусть SS — множество всех слов длины rr в алфавите AA. Тогда ∣S∣=nr|S|=n^r.

Свойство pip_i (1≤i≤n1\le i\le n): слово не содержит буквы aia_i. Нужные нам слова — те, у которых ни одно из свойств p1,…,pnp_1,\dots,p_n не выполнено (ни одной буквы не пропущено). Значит, D(n,r)=E(0)D(n,r)=E(0).

Найдём числа w(k)w(k). Фиксируем kk букв, которых в слове нет: ai1,…,aika_{i_1},\dots,a_{i_k}. Слово составлено из оставшихся n−kn-k букв, повторять можно: таких слов (n−k)r(n-k)^r. А выбрать, какие kk букв отсутствуют, можно (nk)\dbinom nk способами. Поэтому

w(0)=nr,w(1)=(n1)(n−1)r,w(2)=(n2)(n−2)r, …,w(k)=(nk)(n−k)r, …,w(n)=(nn)(n−n)r.\begin{gathered} w(0)=n^r,\qquad w(1)=\binom n1(n-1)^r,\\ w(2)=\binom n2(n-2)^r,\ \dots,\\ w(k)=\binom nk(n-k)^r,\ \dots,\\ w(n)=\binom nn(n-n)^r. \end{gathered}

По принципу включений и исключений D(n,r)=E(0)=w(0)−w(1)+w(2)−⋯+(−1)nw(n)D(n,r)=E(0)=w(0)-w(1)+w(2)-\dots+(-1)^nw(n), то есть

D(n,r)=∑k=0n(−1)k(nk)(n−k)r.\boxed{D(n,r)=\sum_{k=0}^{n}(-1)^k\binom nk(n-k)^r}.

Как читать. Начинаем со всех слов nrn^r. Вычитаем слова без одной буквы (для каждой из nn букв — (n−1)r(n-1)^r). Но слова без двух букв мы вычли дважды: возвращаем (n2)(n−2)r\dbinom n2(n-2)^r, и так далее.

Разбор примера: n=3n=3, r=4r=4

Сколько существует слов длины 44 в алфавите {a,b,c}\{a,b,c\}, содержащих все три буквы?

kk (3k)\dbinom{3}{k} (3−k)4(3-k)^4 Слагаемое
0 1 81 +81
1 3 16 −48
2 3 1 +3
3 1 0 0
сумма 36

Ответ: 81−48+3−0=3681-48+3-0=36.

Проверка другим способом. Слово длины 44 с тремя разными буквами состоит из одной буквы, встретившейся дважды, и двух остальных по одному разу. Выбрать повторяющуюся букву можно 33 способами, а слов с составом, например, a,a,b,ca,a,b,c — 4!2! 1! 1!=12\dfrac{4!}{2!\,1!\,1!}=12 (напомним перестановки с повторяющимися элементами). Всего 3⋅12=363\cdot12=36. Совпало.

Два замечательных частных случая

Случай r=nr=n. Слово длины nn, содержащее все nn букв, использует каждую ровно один раз — это перестановка. Значит, D(n,n)=n!D(n,n)=n!, и мы получили любопытное равенство

n!=∑k=0n(−1)k(nk)(n−k)n.n!=\sum_{k=0}^{n}(-1)^k\binom nk(n-k)^n.

Например, для n=3n=3: 27−3⋅8+3⋅1−0=6=3!27-3\cdot8+3\cdot1-0=6=3!.

Случай r<nr<n. В слове длины r<nr<n не поместятся все nn букв, поэтому D(n,r)=0D(n,r)=0, то есть

∑k=0n(−1)k(nk)(n−k)r=0(r<n).\sum_{k=0}^{n}(-1)^k\binom nk(n-k)^r=0\qquad(r<n).

Для n=4n=4:

rr 1 2 3 4 5 6
D(4,r)D(4,r) 0 0 0 24 240 1560

Числа 0,0,0,24,240,15600,0,0,24,240,1560: нули при r=1,2,3r=1,2,3, затем 4!=244!=24 при r=n=4r=n=4 и дальше рост.

Другое прочтение. D(n,r)D(n,r) — это число способов раздать rr различных предметов nn получателям так, чтобы каждый получил хотя бы один: предмет jj — это позиция jj слова, а буква на ней — получатель.

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

  • Вычитать только слова без одной буквы. Нужно продолжить: ++ слова без двух букв, −- без трёх и так далее.
  • Считать слова без kk букв как (n−k)r(n-k)^r без коэффициента (nk)\dbinom nk. Выбрать, какие kk букв пропущены, можно (nk)\dbinom nk способами.
  • Удивиться слагаемому k=nk=n. Оно равно (nn)⋅0r=0\dbinom nn\cdot0^r=0 при r≥1r\ge1: слов вообще без всех букв нет. Его можно не писать.
  • Применять формулу при r<nr<n ожидая положительного ответа. Результат всегда 00.

Проверь себя

1. Сколько слов длины 44 в алфавите {a,b}\{a,b\} содержат обе буквы?

Решение

D(2,4)=24−2⋅14+0=14D(2,4)=2^4-2\cdot1^4+0=14 (все слова, кроме aaaaaaaa и bbbbbbbb).

2. Сколько слов длины 55 в алфавите {a,b,c}\{a,b,c\} содержат все три буквы?

Решение

D(3,5)=35−3⋅25+3⋅15−0=243−96+3=150D(3,5)=3^5-3\cdot2^5+3\cdot1^5-0=243-96+3=150.

3. Сколькими способами можно раздать 55 различных подарков трём детям, чтобы каждому досталось хотя бы по одному?

Решение

Это то же число: подарок — позиция слова, ребёнок — буква. D(3,5)=150D(3,5)=150.

4. Проверьте по формуле, что D(4,4)=4!D(4,4)=4!.

Решение

D(4,4)=44−4⋅34+6⋅24−4⋅14+1⋅04=256−324+96−4+0=24=4!D(4,4)=4^4-4\cdot3^4+6\cdot2^4-4\cdot1^4+1\cdot0^4=256-324+96-4+0=24=4!.

Итог

  • Слова, содержащие все буквы, — это слова без «пропущенных» букв: свойство pip_i — «нет буквы aia_i».
  • w(k)=(nk)(n−k)rw(k)=\dbinom nk(n-k)^r, поэтому D(n,r)=∑k=0n(−1)k(nk)(n−k)rD(n,r)=\sum_{k=0}^n(-1)^k\dbinom nk(n-k)^r.
  • Если r=nr=n, получаем n!n!; если r<nr<n, получаем 00.
  • D(n,r)D(n,r) — число способов раздать rr различных предметов nn получателям так, чтобы каждый получил хотя бы один.
ПрактикаЗагружаем тест…