число способов замостить пол плитками...

[Alin22]

Нужно определить количество способов заполнить пол размерами 4х10 плитками размером 1х2. Если пол размером 2хN, то количество способов равно N-ому из чисел Фибоначчи, а как поступить в этом случае, когда размеры 4х10?
Заранее спасибо

[arseniiv]

Производящие функции.

[Alin22]

спасибо, а можно чуть чуть подробней?

[caxap]

В "Конкретной Математике" Грэхема и др. было что-то похожее.

[Zealint]

Если вас также интересует "программистское" решение, то есть вот здесь: http://e-maxx.ru/algo/profile_dynamics

Данную задачу проще всего решить (имхо) методом матрицы переноса, где ответом будет число в специальной матрице, возведённой в 10-ю степень. Элементы матрицы - 0 и 1, указывающие на возможность переходов между всеми возможными "профилями", получаемыме в процессе замощения. В вашем случае таких профилей не больше $2^4$. Но полное описание метода заслуживает отдельной статьи...

[Alin22]

Спасибо :)

[Alin22]

мне нужно вывести формулу для нахождения А[n](для поля 4хN) с помощью производящих функций, если кто-нибудь сможет помочь, буду очень благодарна.

[Zealint]

Ну, помочь тут вряд ли быстро получится. Дело в том, что вам для начала нужно определить все возможные "фронты", которые могут получаться при последовательном замощении поля. Потом определить из каких фронтов в какие можно попасть. Получится система рекуррентных соотношений, сворачивающаяся в производящую функцию типа такой:

$$ G(x)=\frac{1-x^2}{1-x-5x^2-x^3+x^4} $$

Она вроде правильная. Я даже не знаю как тут на форуме описать решение, это займёт уйму времени.

[Alin22]

Мне бы хотя бы направление, с чего начать.. потом дальше сама постараюсь разобраться.
А из этого выражения для производящей функции можно получить значение для А[n], то есть, чтобы зная номер N, сразу получить результат?

[Zealint]

Alin22 в сообщении #365827 писал(а):

Мне бы хотя бы направление, с чего начать.. потом дальше сама постараюсь разобраться.
А из этого выражения для производящей функции можно получить значение для А[n], то есть, чтобы зная номер N, сразу получить результат?

Начать нужно с книги "Конкретная Математика" со страницы 353, а потом повторить вывод для полоски шириной 4. Да, из этой производящей функции можно получить ответ для любого $n$, если разложить её в ряд:

$$ \frac{1-x^2}{1-x-5x^2-x^3+x^4}=1+x+5x^2+11x^3+36x^4+95x^5+O(x^6). $$

Например, если $n=5$, то имеем 95 способов замощения. К сожалению, раскладывать эту функцию в ряд руками дело неблагодарное. Тут нужна система компьютерной алгебры. Сами ответы проще получать из рекуррентного соотношения, вид которого показывает знаменатель:

$$ A[n]=A[n-1]+5A[n-2]+A[n-3]-A[n-4], \quad n\geq4. $$

[Alin22]

http://ifolder.ru/19955132
Подскажите, пожалуйста, в чем ошибка..
И еще.
Производящую функцию для чисел Фибоначчи , т.е. 1/(1-x-x^2) можно выразить так:
F(x)=( ($(1+\sqrt{5})^{x+1}$-$(1-\sqrt{5})^{x+1})/$\sqrt{5}$*$2^{x+1}$

Как выразить таким образом функцию, которую получили Вы?
Спасибо.

[Zealint]

Alin22 в сообщении #366418 писал(а):

http://ifolder.ru/19955132
Подскажите, пожалуйста, в чем ошибка..
И еще.
Производящую функцию для чисел Фибоначчи , т.е. 1/(1-x-x^2) можно выразить так:
F(x)=( ($(1+\sqrt{5})^{x+1}$-$(1-\sqrt{5})^{x+1})/$\sqrt{5}$*$2^{x+1}$

Как выразить таким образом функцию, которую получили Вы?
Спасибо.

Кажется, вы совсем не поняли смысл... У вас осталось некоторое непонимание того, что и почему происходит именно так, как происходит. Попытайтесь разобрать хорошенько примеры для полосок шириной 2 и 3.

По поводу формулы. Во-первых, вы путаете $x$ в производящей функции и $x$ в формуле - это совершенно разные вещи, поэтому обозначать их одинаково нельзя. Вам сначала следует разобраться с тем, что такое производящая функция, а потом решать такие достаточно продвинутые задачи. Во-вторых, теоретически можно преобразовать мою производящую функцию в формулу, но выглядеть она будет настолько страшно, что лучше не смотреть.

[Alin22]

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

[Alin22]

Преподаватель так и сказал, что формула получится очень сложная, видимо как вы сказали эта "страшная формула" она и есть.
Уже самой надоело, которую неделю бьюсь над этой задачей, но сделать нужно...

[Zealint]

Вы, конечно, извините, но тут задачи за вас решать нельзя. Все, что я могу сделать - намекнуть вот этой картинкой:


Подробности этого вывода вам придется понять самостоятельно.

Что касается формулы, то чтобы её отыскать, есть два способа. Первый сложный (будет сумма произведений биномиальных коэффициентов), а второй - отыскать корни знаменателя и действовать по принципу, описанному здесь. Но ответ вас не порадует, так как корни очень кривые и упрощать все это без системы компьютерной алгебры под рукой будет не очень просто.