Сколько одночленов окажется в многочлене после раскрытия скобок и приведения подобных членов: $$ (1 + t^{k} + t^{2k} .... + t^{Nk}) \times (1+ t^{s} + t^{2s} .... + t^{Ms}) $$

$%НОД(s, k) = 1$%

alt text

задан 19 Июн '15 2:46

изменен 3 Июл '15 23:11

1

Для частного случая с небольшими числами (скажем $%k=3$%, $%N= 10$%, $%s = 5$%, $%M=6$%) можно сделать таблицу размером ($%N+1 \times M+1$%) со степенями одночленов при раскрытии скобок (без приведения подобных членов). В $%i$%-ой строке первая скобка умножается на $%i$%-ый одночлен во второй. Для указанных параметров в таблице будет $%77$% чисел, $%24$% из которых пересекаются, а потому одночленов будет $%77-24=53$%. Добавил картинку в исходное сообщение.

(22 Июн '15 2:46) sapere aude

по идее, тут можно как-то привлечь линейную алгебру, но хотелось бы отыскать максимально элементарное комбинаторное решение.

(22 Июн '15 19:43) sapere aude

Как увидел лемму из ссылки ниже сразу подумал про эту задачи, если посмотреть для k=3 и s=5, то сходится с графическим решением math.hashcode.ru/questions/70389/

(19 Июл '15 21:48) sapere aude
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,711
×968
×654
×322

задан
19 Июн '15 2:46

показан
526 раз

обновлен
19 Июл '15 21:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru