Элементы дискретной математики - 35 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

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

Рубрика: 

35
Сколькими способами можно замостить прямоугольную доску размером 2 х 7 костями
домино, если все кости считать одинаковыми и учитывать только положение кости:
горизонтальное или вертикальное?
Решение.
Обозначим через Ф(k) количество способов замостить костями домино прямоугольную
доску размером 2 х k. Угловая клетка может быть закрыта одним из двух способов:
либо костью, которая лежит вертикально
, тогда оставшуюся k–1 кость можно
положить Ф(k–1) способами, либо костью, которая лежит горизонтально, тогда еще
одну кость можем положить только горизонтально, а оставшиеся k–2 кости можно
уложить Ф(k–2) способами. Используя правило суммы, приходим к соотношению
Ф(к)=Ф(к–1)+Ф(к–2). Учитывая, что Ф(0)=Ф(1)=1, можем для любого значения k найти
ответ: Ф(2)=2,
Ф(3)=3, Ф(4)=5, Ф(5)=8, Ф(6)=13, Ф(7)=21. Имеем 21 способ замостить
костями домино прямоугольную доску размером 2 х 7.
При решении многих комбинаторных (и не только) задач часто встречается способ,
когда задачу с заданными значениями параметров сводят к аналогичной задаче, но уже с
меньшими значениями параметров. Таким образом, можно довести задачу до простой.
Данный метод
решения задач носит название метода рекуррентных соотношений. (От
латинского слова recurrere – возвращаться).
Пример.
Используя метод рекуррентных соотношений, можно по-новому вывести формулу
для вычисления числа перестановок из k предметов.
Обозначим за Р(k) количество перестановок из элементов k типов. В перестановке
на первом месте может быть любой из k предметов, а оставшиеся k–1 предмет можно в
каждом из этих случаев переставить Р(k–1) способами. По правилу произведения получаем
формулу
Р(k)=k·Р(k-1). Далее замечаем, что Р(1)=1, и получаем, что Р(k)=k!
Числа Фибоначчи
Формула, которую мы получили при решении задачи о домино, впервые была
опубликована в книге “Liber Abaci”, появившейся в 1202 году, где итальянский математик
Фибоначчи среди многих других задач привел следующую:
Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца),
причем новорожденные крольчата через два месяца после рождения уже приносят приплод
.
Сколько кроликов появится через год, если в начале года была одна пара кроликов?

Страницы