Условия существования явной формулы общего члена целоч.посл.

[maximkarimov]

Дана целочисленная последовательность, которая имеет комбинаторную природу (например, A000358). Можно ли ответить на вопрос - существует ли для ее общего члена такая формула, которая содержит только элементарные функции или такой формулы не существует?

[kotenok gav]

Как правило, такая последовательность будет реккурентной. О решении гипергеометрических рекуррентных уравнений/доказательстве несуществования решения можно почитать в A=B.

-- 25 июл 2020, 06:42 --

И давайте все же ссылки: A000358

[maximkarimov]

"... можно почитать в А=B" - это где?)
По поводу давать ссылки - принято.

[kotenok gav]

Гугл вам в помощь.

[maximkarimov]

Погуглил, спасибо!) Из того, что удалось понять сделал вывод, что ответить на мой вопрос нельзя, иными словами - может быть существует такая формула, а может нет. Вполне возможно, что мой вывод ошибочен - поэтому прошу Вас, уважаемый kotenok_gav, не наводить туману, а сделать утверждение (существует/не существует) в отношении последовательности, которую я привел в качестве примера (A000358) и доказать его.
P.S. Или пояснить условия при которых можно утверждать несуществование - в книжке, на которую Вы любезно дали мне ссылку, я этого не нашел (может быть пропустил?).

[kotenok gav]

Chapter 8, Algorithm Hyper.

[novichok2018]

maximkarimov - метода определить, что решение рекуррентного уравнения выражается через элементарные функции, кроме простейших случаев (линейное с постоянными коэффициентами или сводящееся к такому), по-видимому, не существует. Существуют методы современного суммирования в гипергеометрических функциях, когда это возможно. kotenok gav дал Вам ссылку на знаменитую книгу по теме, есть и другие по гипергеометрическому суммированию. Вам нужно не ехидничать про туманы, а сказать ему спасибо.
Он и другие ничего Вам не должны здесь показывать и доказывать, последовательность Ваша и задача Вам нужна, изучайте теорию и вперёд, тем более при таком отношении к подсказкам и помощи.

[maximkarimov]

Изучаю. kotenok_gav - спасибо.

[novichok2018]

Если это последовательность по ссылке - то там есть для неё и простые явные формулы в виде суммы, и ещё более простые приближённые.

[maximkarimov]

novichok2018 - по видимому Вы не поняли мой вопрос. Я спрашивал не о существовании алгоритма или формулы вычисления n-го члена вообще, а о конкретном ее виде или типе - "содержит только элементарные функции". Для A000358 суммирование идет по индексам-делителям n (по сути - выполняется факторизация n) плюс для слагаемого функция Эйлера используется - не заметили?
И естественно речь идет о точной формуле - приближение в элементарных функциях существует всегда, ведь всегда возможно хотя бы одно "очень плохое", но при этом элементарное ("более простое") приближение, не так ли?

[kotenok gav]

maximkarimov в сообщении #1475814 писал(а):

kotenok_gav - спасибо.

Может, вы все же прекратите искажать мой ник?

Если не ошибаюсь, то для A000358 можно построить реккурентное уравнение (но по ссылке его нет, что странно). Правда, не совсем уверен, что у него будут полиномиальные коэффициенты.

[maximkarimov]

kotenok gav - сорри!

[kotenok gav]

Хотя, я сначала не заметил там слова "necklace", подумал, что просто бинарные последовательности... Тогда может и не будет уравнения, надо думать.

[maximkarimov]

Если решение рекуррентного соотношения не может быть представлено в виде конечной комбинации гипер-геометрических функций, то решения в элементарных функциях заведомо не существует. Обратное, в общем случае, неверно.
kotenok gav - Вы это хотели сказать ссылкой на A=B?

[kotenok gav]

maximkarimov в сообщении #1476067 писал(а):

, то решения в элементарных функциях заведомо не существует.

Не факт.

maximkarimov в сообщении #1476067 писал(а):

Вы это хотели сказать ссылкой на A=B?

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