Составители:
Рубрика:
18
1.13. Задача о караване
Рассмотрим еще одну задачу, в которой решение может быть полу-
чено с помощью главной теоремы комбинаторики. 9 верблюдов идут
гуськом. Сколько существует комбинаций перестановки верблюдов, при
которых ни один верблюд не идет за тем, за кем шел ранее.
Выделим запрещенные пары: (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7),
(7, 8), (8, 9). Для решения применим главную теорему комбинаторики.
Для этого определим, что есть объект и что есть свойства. Под объек-
тами будем понимать различные расстановки верблюдов. Всего их бу-
дет N = 9!. Под свойствами будем понимать наличие определенной пары
в перестановке. Таким образом число свойств равно 8. Тогда количе-
ство перестановок, не обладающих ни одним из 8 свойств:
N(
8
) = 9! –
1
8
C
8! +
2
8
C
7! –
3
8
C
6! +… +
4
8
C
1! = 142729 = D
9
+D
8
В общем случае при n верблюдах имеем
D
n
+ D
n – 1
.
Упражнение
Рассмотрим последовательность чисел a
1
, a
2
, …, a
10
. В каком чис-
ле перестановок этих чисел не встретится ни одной пары соседних чи-
сел, т. е. пар (a
1
, a
2
), (a
2
, a
3
), …, (a
9
, a
10
)?
1.14. Комбинаторика разбиений
При анализе стратегий различных игр требуется подсчитывать ко-
личество комбинаций при раскладе определенных предметов. Наибо-
лее распространенная карточная игра – преферанс. В классическом
варианте этой игры карты раскладываются на 3 кучки (по числу играю-
щих) и 2 карты кладутся в “прикуп“. Играют 32 картами, т. е. каждый
игрок получает по 10 карт.
Определим количество вариантов расклада при игре в преферанс:
()
3
32!
.
10! 2!
N
=
Для обоснования полученной формулы расставим все карты подряд
и переставим их 32! способами. При каждой перестановке будем выде-
лять первые 10 карт первому игроку, вторую десятку – второму, третью
Страницы
- « первая
- ‹ предыдущая
- …
- 16
- 17
- 18
- 19
- 20
- …
- следующая ›
- последняя »
