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

UptoLike

2.4 Задачи с ограничениями
Рассмотрим в данном параграфе комбинаторные задачи сначала с ог-
раничениями на порядок элементов, когда на порядок элементов накла -
дываются некоторые дополнительные условия. В таких задачах удобно
применять метод объединение нескольких одинаковых элементов в
блоки .
Далее рассмотрим задачи на разбиения, где требуется разделить
элементы на две или более групп в соответствии с некоторыми условиями,
и требуется найти число всевозможных различных способов раздела . При
этом необходимо учитывать, существенен ли порядок элементов в груп-
пах, различаем ли мы элементы, входящие в группы, и сами группы и т . д .
При решении этих задач обычно элементы располагают в ряд и применяют
так называемый метод введения перегородок.
Пример 16. Имеются предметы k сортов : n
1
предметов одного сорта,
n
2
предметов другого сорта, , n
k
предметов k-ого сорта , где все предметы
одного сорта всё же различны друг от друга . Найти число перестановок
этих предметов, в которых все предметы одного и того же сорта стоят ря-
дом.
Решение. Из данных k сортов (блоков) можно сделать P
k
=k!
перестановок. Но ещё можно переставлять предметы внутри блоков n
1
!,
n
2
!, , n
k
! способами. Далее по правилу произведения имеем n
1
!n
2
! n
k
!k!
перестановок.
Пример 17. Сколькими способами можно переставить буквы слова
перемет” так, чтобы три буквы е” не шли подряд ?
Решение. Объединим все буквы “е” в блок еее” . Число перестано-
вок, в которых все три буквы е” идут подряд , равно числу перестановок
из 5-ти объектов : еее” , п” , м”, р” , т”, т. е. P
5
=5! Всего же перестано-
вок с повторениями из букв данного слова можно составить
P(3,1,1,1,1)=840. Значит , искомое число перестановок, где три буквы “е” не
идут рядом равно N = 840 -- 120 = 720 (способов).
Пример 18. Сколькими способами можно расставить m нулей и k
единиц так, чтобы никакие две единицы не стояли рядом?
Решение. Выпишем сначала m нулей. Для единиц получается (m+1)
место (одно впереди, (m-1) в промежутках между нулями и одно сзади). На
любые из этих (m+1) мест можно поставить одну из k единиц. Это можно
осуществить
k
m
C
1+
способами, причём k
m+1.
Пример 19. На полке стоят 12 книг. Сколькими способами можно
выбрать из них 5 книг так, чтобы никакие две из них не стояли рядом ?