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

                           2.4 Задачи с ограничениями

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

      Пример 16. Имеются предметы k сортов : n1 предметов одного сорта,
n2 предметов другого сорта, … , nk предметов k-ого сорта, где все предметы
одного сорта всё же различны друг от друга. Найти число перестановок
этих предметов, в которых все предметы одного и того же сорта стоят ря-
дом.
      Решение. Из данных k сортов (блоков) можно сделать Pk=k!
перестановок. Но ещё можно переставлять предметы внутри блоков n 1!,
n2!, … , nk! способами. Далее по правилу произведения имеем n 1 !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 единиц. Это можно
                k
осуществить Cm +1 способами, причём k ≤ m+1.

     Пример 19. На полке стоят 12 книг. Сколькими способами можно
выбрать из них 5 книг так, чтобы никакие две из них не стояли рядом?