Комментарии 27
У вас ключевая сумма не отображается, видно только n_i
И ещё непонятно что означают квадратные скобки при n_i. А так - полезная заметка.
Так ведь 1/11 из элементарных соображений?
P.S. Нет, соврал :(
В третьей формуле должно быть res(1/z^(m-n+1)), а у вас m-n-1.
очень интересные расчеты. вспомнил то, что изучал 6 лет назад
Хоть раз ТФКП пригодилась за эти 6 лет?
В вашем колхозе цветы тоже считаются вредным излишеством?
При чем тут цветы? Цветами в вузах студентов не мучают. За то, что не сдал экзамен по цветам не отчисляют и никому судьбу не ломают. А за ТФКП отчисляют только в путь. По крайней мере у меня это был единственный предмет за все время учебы, по которому меня отправили на пересдачу. У нас а на экзамене по ТФКП преподаватели сильно жестили. Наверное это очень важный свирепствуют, раз препы на нем так зверствует. По видимому они уверены, что знание ТФКП критически важно. Вот мне и интересно - кому ни будь оно пригодилось?
Кому-нибудь пригодилось, мне например
Я не изучал ТФКП в институте, но оно пригодилось потом в ЦОС, в задачах синтеза и анализа звука, а также в решении геометрических задач на плоскости, ориентированных на геймдев (даже статью порывался писать на эту тему писать, но руки так и не дошли. Зато другая есть, решаемая также через комплексные числа).
Билетиков на самом деле 10^6 - 1, но единица ничего здесь не решает, у нее нет власти.
Получается, в z-области задача факторизуется, а в области индексов - нет. Классика)
Если рассмотреть многочлен р(z) = ( 1+z+z^2 +z^3+...+z^9 ) ^3 , то не трудно понять - коэффициент при z^n есть число способов представить число n в виде суммы трех чисел . Тогда сумма квадратов этих коэффициентов есть число счастливых билетов , которую можно представить в виде коэффициента при нулевой степени многочлена
р(z)×p( 1/z ) = ( 1/z^27)×( (1-z^10 )/( 1- z ) )^6
Отсюда можно получить , используя формулу о вычетах , ( поделив данное выражение на z ) ваше выражение для М в виде интеграла по контуру .
А можно не получать - просто посчитав коэффициент при минус первой степени ( если по вашему ) , либо коэффициент при нулевой - по моему . Используя разложения функций именно так , как вы написали - без ТФКП .
Впрочем , использование интегрального представления дельта - функции - почему нет . Оригинально.
В принципе ТФКП можно приплести :
Итак , имеем интеграл по контуру от функции р(z)×p( 1/z ) / z . Если взять контур в виде единичной окружности с центром в начале координат , то есть сделать замену : z = exp( 2×X×i) , где х = [ 0..Pi ] , то элементарными преобразованиями , с учетом того , что у нас сопряженные числа , получим :
М = ( 1/Pi ) × int ( ( sin ( 10×X ) / sin ( X ))^6 , x= 0..Pi )
То есть получим выражение М через обычный интеграл .
Повторил ваши выкладки, замысловатая первообразная получается, но да, работает.
Ну а поскольку 
, то решение можно получить свёрткой дискретной последовательности 
самой с собой 6 раз и искомое число будет в середине итоговой последовательности. Тут и БПФ можно приплести заодно.
То есть имеется ввиду обычное приближенное вычисление интеграла :
М = ( 1/N )* Sum ( f( a + k*Pi/N ) , k = 0..N-1 )
Почему приближенное? Вполне точное, опираясь на теорему о свёртке.
У нас имеется функция : f( X) = ( sin ( 10×X ) / sin ( X ))^6
Как доказать , что
( 1/Pi ) × int ( f(X) , x= 0..Pi ) = ( 1/N )* Sum ( f( a + k*Pi/N ) , k = 0..N-1 ) , да еще и при любом N > 27
используя теорему о свертке - я не понимаю . Так как в общем виде - это заведомо ложное равенство , точнее - это просто приближенное вычисление интеграла от функции f ( X ) . Более того : оно приближенное даже в частном ( данном ) случае ( когда функция - тригонометрический многочлен ) , если N < 28 .
Вы же помните, что интеграл в этой задаче притянут за уши? А если их оттянуть обратно, то получится вычисление биномиальных коэффициентов через свёртку. Ну а свёртка конечной последовательности с целыми коэффициентами гарантированно даст конечную последовательность с целыми коэффициентами, только длинее. Это единственное, что я обобщаю в данном случае.
Я понимаю , что если мы знаем происхождение данного интеграла , то используя этот факт , мы можем его легко посчитать . Например как коэффициент в разложении функции и это вычисляется без всяких Фурье-преобразований , сверток и " вручную " .
Я о другом : Имеется интеграл от некой функции f ( x ) . Мы хотим его посчитать приближенными методами . Берем самый примитивный и самый грубый метод - метод прямоугольников : у нас пределы интегрирования от 0 до Pi . Делим его на N частей и берем соответственно N точек : а + Pi*к/N , k = 0..N - 1 , получаем приближенную формулу вычисления интеграла :
Int ( f ( x ) , x = 0..Pi ) = ( Pi/ N ) Sum ( f ( а + Piк/N ) , k = 0 ...N - 1 ) .
Так вот : дело в том , что ( например ) в нашем случае при N > 27 эта формула точная при любых N и любых а !!!
Существует доказательство данного утверждения , учитывая тот факт , что наша функция - тригонометрический многочлен . Но как это доказать , так же легко и непринужденно , как вычисление счастливых билетиков , приплетая сюда ТФКП - я не знаю .
Если вы в курсе , то было бы любопытно на это посмотреть .
Спасибо, всегда любил ТФКП. Самый приятный раздел университетской математики вместе с диффурами.
Вообще, в програзме, если хочется более-менее точно считать сложность алгоритмов, ТФКП вылезает. Оказывается, для более-менее сложных вещей, через вычеты получается достаточно надёжно. На Курсере даже был курс Седжвика.
Отсюда легко видеть... (с)
Зачем считать довольно непростой интеграл , пусть и с помощью компьютера , если мы знаем откуда он появился : это определенный коэффициент в разложении соответствующей функции . Разлагая ее , получаем сразу ответ : М = Sum ( ((-1)^k )*bin ( 6, k ) * bin ( 32-10k , 5 ) , k =0..2 ) = bin ( 32 , 5 ) + bin ( 6 ,1) bin ( 22 ,5 ) + bin ( 6 , 2 ) * bin ( 12 , 5 )
Здесь , у меня , естественно : bin - биноминальный коэффициент .
Если все-таки соберетесь считать на компьютере , то рекомендую считать " в лоб " - по приближенной формуле : обнаружите любопытный факт - получите абсолютно точный ответ при N > 27....
Задача про счастливые билетики и ТФКП