|
Сколько одночленов окажется в многочлене после раскрытия скобок и приведения подобных членов: $$ (1 + t^{k} + t^{2k} .... + t^{Nk}) \times (1+ t^{s} + t^{2s} .... + t^{Ms}) $$ $%НОД(s, k) = 1$%
задан 19 Июн '15 2:46 
sapere aude |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
19 Июн '15 2:46
показан
2003 раза
обновлен
19 Июл '15 21:48
Связанные исследования
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Для частного случая с небольшими числами (скажем $%k=3$%, $%N= 10$%, $%s = 5$%, $%M=6$%) можно сделать таблицу размером ($%N+1 \times M+1$%) со степенями одночленов при раскрытии скобок (без приведения подобных членов). В $%i$%-ой строке первая скобка умножается на $%i$%-ый одночлен во второй. Для указанных параметров в таблице будет $%77$% чисел, $%24$% из которых пересекаются, а потому одночленов будет $%77-24=53$%. Добавил картинку в исходное сообщение.
по идее, тут можно как-то привлечь линейную алгебру, но хотелось бы отыскать максимально элементарное комбинаторное решение.
Как увидел лемму из ссылки ниже сразу подумал про эту задачи, если посмотреть для k=3 и s=5, то сходится с графическим решением math.hashcode.ru/questions/70389/