В задаче необходимо найти количество способов разрезания клетчатого кольца из n клеток на домино(1x2) и тримино(1x3). Что такое клетчатое кольцо?

задан 20 Апр '17 10:33

изменен 20 Апр '17 11:33

falcao's gravatar image


256k23650

Обычно это описано, как полоска клетчатой бумаги склеенная кольцом

(20 Апр '17 11:22) Isaev

@Reyg: это то же, что и клетчатая полоска бумаги, только склеенная: за последней клеткой идёт первая. Фактически, это боковая поверхность цилиндра.

Я так понимаю, в условии считается, что клетки как бы пронумерованы, то есть способы, отличающиеся поворотом, считаются разными.

(20 Апр '17 11:25) falcao

@falcao: а n клеток, это его ширина?

(20 Апр '17 11:35) Isaev

@Isaev: была полоска 1xn, потом её склеили. Я думаю, что длиной надо считать n, как оно и было, а ширина равна 1.

(20 Апр '17 12:06) falcao
10|600 символов нужно символов осталось
0

Обозначим через f(n) вспомогательную функцию: число способов замостить обычную полоску из n клеток при помощи домино и тримино. Тогда начальные значения таковы: f(0)=1, f(1)=0, f(2)=1. Далее при n>=2 у нас первой лежит плитка домино или плитка тримино, откуда получается рекуррентная формула f(n)=f(n-2)+f(n-3). Характеристическое уравнение этого соотношения имеет один вещественный корень, приблизительно равный 1,3247, и два мнимых. В явном виде корни выражаются плохо, поэтому здесь можно или ограничиться рекуррентной формулой, или получить производящую функцию. Домножая рекуррентное соотношение на t^n и суммируя по n>=3, имеем F(t)-1-t^2=t^2(F(t)-1)+t^3F(t), откуда F(t)=1/(1-t^2-t^3).

Теперь пусть g(n) -- число способов замощения кольцевой полоски. Здесь также g(0)=1 (условно), g(1)=0, g(2)=2 (плитка домино может занимать две разных позиции). При n>=3 возможны такие варианты: в начале лежит плитка домино; плитка тримино; плитка домино занимает последнюю и первую позиции; плитка тримино занимает две последние позиции и первую; плитка тримино занимает последнюю позицию и две первых. Отсюда g(n)=2f(n-2)+3f(n-3). Это даёт такие значения последовательности при 0<=n<=20:

1, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, ... .

Производящая функция здесь прямо выражается через предыдущую, и получается G(t)=1+2t^2+2t^2(F(t)-1)+3t^3F(t)=(1+t^2+2t^3)/(1-t-t^3).

ссылка

отвечен 20 Апр '17 12:05

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,333

задан
20 Апр '17 10:33

показан
469 раз

обновлен
20 Апр '17 12:06

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru