dimaniac
Удален
|
    
Я вот подумал это вроде как сочетания с повторениями. А формула там если не ошибаюсь другая С(n+k-1,k-1). Насчет +4 мне эта формула нужна чтобы определить время выполнения одной задачки по программированию. По условию 4 там не может быть. Кроме того это не принципиально т.к. ответ изменится всего лишь на n.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 23 апр. 2005 7:06 | IP
|
|
Guest
Новичок
|
Если число слагаемых нефиксировано, то надо просуммировать C(n+k-1,n-k) по k от 1 до n.
Эта сумма равна числу Фибоначчи F(2n).
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 23 апр. 2005 8:36 | IP
|
|
Guest
Новичок
|
Цитата: dimaniac написал 23 апр. 2005 7:06
Я вот подумал это вроде как сочетания с повторениями. А формула там если не ошибаюсь другая С(n+k-1,k-1).
Эта формула дает число различных композиций (т.е. разбиений, в которых важен порядок) числа n на k слагаемых. В то время как указанная мной формула вычисляет сумму произведений элементов этих композиций.
Цитата: dimaniac написал 23 апр. 2005 7:06
По условию 4 там не может быть. Кроме того это не принципиально т.к. ответ изменится всего лишь на n.
Тогда ответом будет F(2n)-n.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 23 апр. 2005 8:42 | IP
|
|
dimaniac
Удален
|
А в какой книге есть эти формулы?
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 23 апр. 2005 9:32 | IP
|
|
Guest
Новичок
|
Цитата: dimaniac написал 23 апр. 2005 9:32
А в какой книге есть эти формулы?
Боюсь, что ни в какой. Потому как если осилить хотя бы половину того же Стенли, то такие задачки будут щёлкаться как орехи.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 24 апр. 2005 12:12 | IP
|
|
sms
Удален
|
На самом деле существует общий метод суммирования рядов или конечных сумм из биноминальных коэффициентов=гипергеометрических рядов. Безотносительно к комбинаторике. Это можно делать руками или когда не получается на компе готовыми программами. Про это есть гениальная книга с коротким названием A=B.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 24 апр. 2005 16:47 | IP
|
|
sms
Удален
|
Можно действительно пояснить Ваш вывод, что это число Фибоначчи? Я знаю производящую функцию для них, но с ходу эту конкретную сумму не свёл.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 25 апр. 2005 21:50 | IP
|
|
dm
Удален
|
sms
Думаю, можно одновременно проверить индукционный переход в равенствах:
sum_(k=1)^n C_(n+k-1)^(n-k) = f_(2n)
sum_(k=1)^(n+1) C_(n+k-1)^(n-k+1) = f_(2n+1)
(при этом воспользуемся рекуррентным соотношением для биноминальных коэффициентов).
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 25 апр. 2005 22:35 | IP
|
|
Guest
Новичок
|
См. формулы на внешняя ссылка удалена
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 25 апр. 2005 23:21 | IP
|
|
sms
Удален
|
dm
Если ответ уже указан, то можно, наверное, и без индукции его проверить. Доказать, что совпадает для первого n, а затем проверить, что суммы удовлетворяют простенькому соотношению для чисел Фибоначчи. Конечно, пригодятся рекуррентные соотношения, как Вы справедливо указали.
Вопрос-как вывести сам ответ, не зная его. Производящая функция, которую я знаю, приводит к подобным суммам, но не в точности этим. Нужно ещё подумать, как свести.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 27 апр. 2005 21:29 | IP
|
|
Форум
Кодирование перестановок.
