Оценка сверху количества перестановок

[Jilian]

Коридор имеет размеры 3*N. Для любого заданного N, необходимо оценить максимальное количество различных вариантов, которыми можно уложить паркет в этом коридоре плитками размером [1*2] или [2*2] (сами варианты укладки паркета определять не надо).

[Руст]

N нечётно решений нет, если N -чётно то число решений равно 2* число решений для (N-2) следовательно 2^(N/2).

[maxal]

Jilian писал(а):

Коридор имеет размеры 3*N. Для любого заданного N, необходимо оценить максимальное количество различных вариантов, которыми можно уложить паркет в этом коридоре плитками размером [1*2] или [2*2] (сами варианты укладки паркета определять не надо).

Решение для полосы 2 x n:

Пусть $f(n)$ - число вариантов укладки полосы размером 2 x n клеток. Тогда $f(n+1) = f(n) + 2 f(n-1)$. Откуда следует, что $f(n)=\frac{2^{n+1}+(-1)^n}{3}$.

[Руст]

Как укладывается 3*1?

[maxal]

Предыдущее решение было для полосы размером 2xn. Исправляюсь.

Пусть $f(n)$ - число вариантов укладки полосы размером 3 x n клеток. Пусть $g(n)$ - число вариантов укладки этой же полосы с одной вырезанной угловой клеткой. Тогда:
$f(n+1) = 2g(n) + 3f(n-1)$
$g(n+1) = f(n) + 2g(n-1)$
Откуда следует, что
$f(n+2) = 7f(n) - 6f(n-2)$
и с учетом $f(0)=1, f(2)=5$ получаем $f(2n)=\frac{4\cdot 6^n + 1}{5}$.

Ну а для неченых n, действительно f(n)=0.

[AHOHbIMHO]

Jilian писал(а):

Коридор имеет размеры 3*N. Для любого заданного N, необходимо оценить максимальное количество различных вариантов, которыми можно уложить паркет в этом коридоре плитками размером [1*2] или [2*2] (сами варианты укладки паркета определять не надо).

После замечания maxal (см. следующий пост) получаем следующее решение

При N=2, имеем 5 вариантов укладки (можно нарисвовать и посмотреть), при четных N имеем $5^{N/2}$, т.к. каждая часть размером 3 на 2 ( общее количество которых равно N/2) укладывается независимо от друга. При нечетных N имеем 0 вариантов укладки.

[maxal]

AHOHbIMHO писал(а):

При N=2, имеем 3 варианта укладки (можно нарисвовать и посмотреть)

Для N=2 существует 5 вариантов укладки. Не забывайте, что паркетину 1x2 можно вертеть.

[AHOHbIMHO]

maxal писал(а):

AHOHbIMHO писал(а):

При N=2, имеем 3 варианта укладки (можно нарисвовать и посмотреть)

Для N=2 существует 5 вариантов укладки. Не забывайте, что паркетину 1x2 можно вертеть.

Да 5. Я про это помнил, запутался с заменой паркета 2 на 2 двумя 2 на 1

[AHOHbIMHO]

AHOHbIMHO писал(а):

Jilian писал(а):

Коридор имеет размеры 3*N. Для любого заданного N, необходимо оценить максимальное количество различных вариантов, которыми можно уложить паркет в этом коридоре плитками размером [1*2] или [2*2] (сами варианты укладки паркета определять не надо).

После замечания maxal (см. следующий пост) получаем следующее решение

При N=2, имеем 5 вариантов укладки (можно нарисвовать и посмотреть), при четных N имеем $5^{N/2}$, т.к. каждая часть размером 3 на 2 ( общее количество которых равно N/2) укладывается независимо от друга. При нечетных N имеем 0 вариантов укладки.

Не, это не правильное решение. Я ошибся в том, что части независимо друг от другоа укладываются. При N=4 в этом можно убдетиться.

[maxal]

Решение приведено выше.

[AHOHbIMHO]

maxal писал(а):

Пусть $g(n)$ - число вариантов укладки этой же полосы с одной вырезанной угловой клеткой.

Не понял, может быть имелось полоса с вырезанным углом размера 2 на 1? Иначе число вариантов равно нулю.

[AHOHbIMHO]

AHOHbIMHO писал(а):

maxal писал(а):

Пусть $g(n)$ - число вариантов укладки этой же полосы с одной вырезанной угловой клеткой.

Не понял, может быть имелось полоса с вырезанным углом размера 2 на 1? Иначе число вариантов равно нулю.

А, начал понимать. Просто это не совсем корректно выражалость, т.к. неправиьно говорить "этой же полосы ", а полосы в случае нечетного n.

[Jilian]

весьма благодарна за посты, но реккурентные соотношения я уже вывела, прогу сдала. Попросили просто числом оценить число таких укладок для N
K(i,0,0,0)=K(i-1,1,1,1).
K(i,1,0,0)=K(i-1,0,1,1)
K(i,0,1,0)=K(i-1,1,0,1)
K(i,0,0,1)=K(i-1,1,1,0)
K(i,1,0,1)=K(i-1,0,1,0)
K(i,1,1,0)=K(i-1,1,1,1) +K(i-1,1,0,1) +K(i-1,0,0,1)
K(i,0,1,1)=K(i-1,1,1,1) +K(i-1,1,0,0) +K(i-1,1,0,1)
K(i,1,1,1)=K(i-1,0,0,1)+K(i,1,0,0) +K(i-1,0,0,0)+K(i-1,0,0,0)+K(i-1,0,0,0)

[maxal]

AHOHbIMHO писал(а):

AHOHbIMHO писал(а):

maxal писал(а):

Пусть $g(n)$ - число вариантов укладки этой же полосы с одной вырезанной угловой клеткой.

Не понял, может быть имелось полоса с вырезанным углом размера 2 на 1? Иначе число вариантов равно нулю.

А, начал понимать. Просто это не совсем корректно выражалость, т.к. неправиьно говорить "этой же полосы ", а полосы в случае нечетного n.

Все корректно. Я нигде не писал, что n должно быть четным или нечетным. Для f(n+2) получилась линейная зависимость от f(n) и f(n-2), и только после этого уже можно рассматривать отдельно четные и нечетные n. Просто для нечетных n начальные условия f(1) и f(3) являются нулевыми, что порождает ряд нулей. А вот для четных они ненулевые и дают указанное решения.

[AHOHbIMHO]

maxal писал(а):

AHOHbIMHO писал(а):

AHOHbIMHO писал(а):

maxal писал(а):

Пусть $g(n)$ - число вариантов укладки этой же полосы с одной вырезанной угловой клеткой.

Не понял, может быть имелось полоса с вырезанным углом размера 2 на 1? Иначе число вариантов равно нулю.

А, начал понимать. Просто это не совсем корректно выражалость, т.к. неправиьно говорить "этой же полосы ", а полосы в случае нечетного n.

Все корректно. Я нигде не писал, что n должно быть четным или нечетным. Для f(n+2) получилась линейная зависимость от f(n) и f(n-2), и только после этого уже можно рассматривать отдельно четные и нечетные n. Просто для нечетных n начальные условия f(1) и f(3) являются нулевыми, что порождает ряд нулей. А вот для четных они ненулевые и дают указанное решения.

Ладно, я не буду спорить. Главное я понял Ваше решение. Нарисовал, проверил - все сошлось.