Дискретная математика. Ерош И.Л - 78 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

78
количество перестановок, не обладающих ни одним из восьми свойcтв,
будет равно
12
123 8
888 8
8 9! 8! 7! 6! ... 1! 148 329.NСССС34 5 4 5 3
В общем случае при n верблюдах получаем
12 1 2 1 2
12 12
12
11
31
111
!1!2!
3! ... 1 1! .
nn
n
n
nnnn
Nn n C n C n
CCDD
34 4 5 4 4
4454 35
(4.14)
Упражнения.
1. Пусть имеется последовательность некоторых чисел a
1
, a
2
, a
3
, …,
a
n
. В каком количестве перестановок не встречается ни одной подряд
стоявшей пары?
2. В каком количестве перестановок чисел предыдущего примера
встречается ровно 5 пар чисел, которые находились рядом в исходной
расстановке?
4.3. Комбинаторные задачи на раскладки и разбиения
Этот класс задач часто используется для оптимизации стратегий в
различных играх.
4.3.1. Раскладки с указанием числа предметов
При анализе стратегий различных игр часто требуется подсчитывать
количество комбинаций при раскладке определенных предметов (карт,
костей, спичек и т. п.). Наиболее распространенная карточная игра –
преферанс. В классическом варианте этой игры 32 карты раздаются на
руки трем игрокам по 10 карт каждому и 2 карты кладутся в «при
куп». Определим количество вариантов расклада при игре в преферанс:
3
32!
.
(10 !) 2!
N 1
Для обоснования полученной формулы выложим все карты подряд
и переставим их 32! способами. При каждой перестановке первые 10
карт будем отдавать первому игроку, следующие 10 карт – второму,
следующие 10 карт – третьему и последние 2 карты будем класть в
«прикуп». После этого заметим, что перестановка 10 карт в руках каж
дого игрока не меняет варианта расклада, как и положения двух карт
в «прикупе». Поэтому 32! разделим три раза на 10! и один раз на 2!.
При игре в древнюю китайскую игру НИМ раскладывается n спи
чек на 3 кучки. Подсчитаем число вариантов расклада при игре в НИМ.

Страницы