Составители:
Рубрика:
16
обезличенные, то
4
6
C
= 15. В общем случае при n львах и k тиграх
имеем:
1
k
n
C
+
б) Задача о книжной полке. Из m книг, стоящих на полке, нужно
выбрать k таких, которые не стояли рядом на книжной полке. Отберем
сразу k книг, останется n–k. Их расставим с промежутками (n–k+1 про-
межуток). На эти места вставим k книг. Общее решение:
1
k
nk
C
−+
( 9 )
в) Рыцари короля Артура. 12 рыцарей сидят за круглым столом.
Нужно выбрать 5 из них, но таких, которые не сидели рядом за столом.
Множество всех решений разбиваем на два подмножества в зависимо-
сти от того, входит ли в команду избранных конкретный рыцарь или
нет? Ответ: 15 +21 = 36. Если за круглым столом сидит n рыцарей, а
нужно выбрать k, которые не сидели рядом, то задача решается анало-
гично и имеет смысл при n ≥ 2k.
Упражнение
Определите условия при которых задачи а), б) и в) имеют решения.
1.11. Задачи о смещениях (о беспорядках)
Имеется 5 разных предметов. Сколько можно составить различ-
ных комбинаций, в которых ни один предмет не стоит на своем мес-
те? Решим задачу с помощью теоремы о включениях и исключени-
ях: N( 5 ) = 5!–
1
5
C
⋅ 4! +
2
5
C
⋅ 3!–
3
5
C
⋅ 2! +
4
5
C
⋅ 1!–
5
5
C
⋅ 0! = 44. При
решении этой задачи мы использовали главную теорему комбинатори-
ки, которая требует определить, что понимается под объектами и что
под свойствами этих объектов. Общее число объектов равнялось 5!,
так как под объектом мы будем понимать различные расстановки пяти
предметов. Под первым свойством понимаем наличие первого предме-
та на своем месте, под вторым – наличие второго предмета на своем
месте и т. д. Всего оказалось 5 свойств.
1.12. Частный случай теоремы о включениях и исключениях
В некоторых случаях количество объектов, обладающих определен-
ным набором свойств, зависит только от числа этих свойств. Тогда фор-
мула для подсчета числа объектов, не обладающих ни одним из выде-
ленных свойств, упрощается.
Страницы
- « первая
- ‹ предыдущая
- …
- 14
- 15
- 16
- 17
- 18
- …
- следующая ›
- последняя »
