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

UptoLike

Составители: 

45
применять метод объединение нескольких одинаковых элементов в
блоки.
Далее рассмотрим задачи на разбиения, где требуется разделить
элементы на две или более групп в соответствии с некоторыми условиями,
и требуется найти число всевозможных различных способов раздела. При
этом необходимо учитывать, существенен ли порядок элементов в группах,
различаем ли мы элементы, входящие в группы, и сами группы и т. д. При
решении этих задач обычно элементы располагают в ряд и применяют так
называемый метод введения перегородок.
Пример 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 единиц. Это
можно осуществить
1
k
m
C
+
способами, причём k
£
m + 1.
Пример 19. На полке стоят 12 книг. Сколькими способами можно
выбрать из них 5 книг так, чтобы никакие две из них не стояли рядом?
Решение. Зашифруем каждый выбор книг последовательностью из
нулей и единиц следующим образом: каждой оставленной книге сопоста-
вим 0, а каждой взятой 1. В результате получим последовательность из 5
единиц и 7 нулей, причём в последовательности не будет двух подряд