2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: задача по комбинаторике
Сообщение09.10.2010, 22:01 
Производящие функции.

 
 
 
 Re: задача по комбинаторике
Сообщение09.10.2010, 22:27 
спасибо, а можно чуть чуть подробней?

 
 
 
 Re: задача по комбинаторике
Сообщение09.10.2010, 23:05 
Аватара пользователя
В "Конкретной Математике" Грэхема и др. было что-то похожее.

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

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

 
 
 
 Re: задача по комбинаторике
Сообщение10.10.2010, 10:24 
Спасибо :)

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

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

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

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

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

 
 
 
 Re: задача по комбинаторике
Сообщение25.10.2010, 06:29 
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.
$$

 
 
 
 Re: задача по комбинаторике
Сообщение26.10.2010, 15:13 
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}$

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

 
 
 
 Re: задача по комбинаторике
Сообщение26.10.2010, 18:21 
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$ в формуле - это совершенно разные вещи, поэтому обозначать их одинаково нельзя. Вам сначала следует разобраться с тем, что такое производящая функция, а потом решать такие достаточно продвинутые задачи. Во-вторых, теоретически можно преобразовать мою производящую функцию в формулу, но выглядеть она будет настолько страшно, что лучше не смотреть.

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

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

 
 
 
 Re: задача по комбинаторике
Сообщение27.10.2010, 06:24 
Вы, конечно, извините, но тут задачи за вас решать нельзя. Все, что я могу сделать - намекнуть вот этой картинкой:
Изображение

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

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

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group