Дискретная математика. Элементы теории, задачи и упражнения. Часть 1. Булгакова И.Н. - 45 стр.

применять метод – объединение нескольких одинаковых элементов в
блоки.
      Далее рассмотрим задачи на разбиения, где требуется разделить
элементы на две или более групп в соответствии с некоторыми условиями,
и требуется найти число всевозможных различных способов раздела. При
этом необходимо учитывать, существенен ли порядок элементов в группах,
различаем ли мы элементы, входящие в группы, и сами группы и т. д. При
решении этих задач обычно элементы располагают в ряд и применяют так
называемый метод введения перегородок.

      Пример 16. Имеются предметы k сортов : n1 предметов одного сорта,
n2 предметов другого сорта, … , nk предметов k-го сорта, где все предметы
одного сорта всё же различны друг от друга. Найти число перестановок
этих предметов, в которых все предметы одного и того же сорта стоят ря-
дом.
      Решение. Из данных k сортов (блоков) можно сделать Pk = k! пере-
становок. Но ещё можно переставлять предметы внутри блоков n1!, n2!, … ,
nk! способами. Далее по правилу произведения имеем n1!n2!…nk!k! пере-
становок.

      Пример 17. Сколькими способами можно переставить буквы слова
«перемет» так, чтобы три буквы «е» не шли подряд?
      Решение. Объединим все буквы «е» в блок «еее». Число перестано-
вок, в которых все три буквы «е» идут подряд, равно числу перестановок
из 5-ти объектов : «еее», «п», «м», «р», «т», т. е. P5 = 5! Всего же переста-
новок с повторениями из букв данного слова можно составить
P(3,1,1,1,1) = 840. Значит, искомое число перестановок, где три буквы «е»
не идут рядом равно N = 840 – 120 = 720 (способов).

     Пример 18. Сколькими способами можно расставить m нулей и k
единиц так, чтобы никакие две единицы не стояли рядом?
     Решение. Выпишем сначала m нулей. Для единиц получается (m + 1)
место (одно впереди, (m – 1) в промежутках между нулями и одно сзади).
На любые из этих (m + 1) мест можно поставить одну из k единиц. Это
можно осуществить    Cmk � 1 способами, причём k � m + 1.

     Пример 19. На полке стоят 12 книг. Сколькими способами можно
выбрать из них 5 книг так, чтобы никакие две из них не стояли рядом?
     Решение. Зашифруем каждый выбор книг последовательностью из
нулей и единиц следующим образом: каждой оставленной книге сопоста-
вим 0, а каждой взятой – 1. В результате получим последовательность из 5
единиц и 7 нулей, причём в последовательности не будет двух подряд

                                     45