Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        Кодирование перестановок.
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 3 ]
Модераторы: Roman Osipov, RKI, attention, paradise
  

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



Новичок

См. формулы на http://www.research.att.com/projects/OEIS?Anum=A001906

Всего сообщений: Нет | Присоединился: Never | Отправлено: 25 апр. 2005 23:21 | IP
sms


Удален

dm
Если ответ уже указан, то можно, наверное, и без индукции его проверить. Доказать, что совпадает для первого n, а затем проверить, что суммы удовлетворяют простенькому соотношению для чисел Фибоначчи. Конечно, пригодятся рекуррентные соотношения, как Вы справедливо указали.
Вопрос-как вывести сам ответ, не зная его. Производящая функция, которую я знаю, приводит к подобным суммам, но не в точности этим. Нужно ещё подумать, как свести.

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 27 апр. 2005 21:29 | IP

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 3 ]

Форум работает на скрипте © Ikonboard.com