Помогите разобраться с вычислением суммы

[ShnurDash]

Здравствуйте. Стоит задача - получить удобную формулу для числа изомеров насыщенных одноатомных спиртов. Формула Пойа (в дебри дискретной математики не вдавался, привожу итоговый результат) задаётся следующим образом: $n_{isomers} = 1 + \frac{C^{3}(x)+3C(x)C(x^{2})+2C(x^{3})}{6} \cdot x = C(x)$, где $C(x)$ - производящая функция последовательности ($C(0)=1$). Вроде бы всё понятно, постепенно плодим полином, получаем в коэффициентах число изомеров "спирта" n-ой степени, но задача стоит в том, чтобы упростить алгоритм и не заставлять людей возводить длинные полиномы в куб и перемножать их между собой. Думал - всё, приехали. Но недавно нашёл альтернативную запись формулы Пойа: $g_{n+1} = \frac{1}{6}[\sum\limits_{i+j+k=n}^{}g_{i}g_{j}g_{k}+3\sum\limits_{i+2j}^{}g_{i}g_{j}+2\sum\limits_{3i=n}^{}g_{i}]$, где $g_{i}, g_{j}, g_{k}$ - известные члены последовательности, $n (0, 1, 2...)$, $g_{0}=1$, $i, j, k \in \mathbb{Z}$. Меня очень смутили выражения в условии суммирования. Пожалуйста, натолкните на правильную мысль, Заранее спасибо.

[iifat]

Вам бы, эээ, вопрос сформулировать, глядишь, и натолкнули б.
В альтернативном варианте в средней сумме явно $i+2j=n$, уж не знаю, у вас описка, или в книге.
Хоть попробуйте сформулировать, чем же вас так смутила безобидная запись.

[ShnurDash]

iifat в сообщении #1531246 писал(а):

Вам бы, эээ, вопрос сформулировать, глядишь, и натолкнули б.
В альтернативном варианте в средней сумме явно $i+2j=n$, уж не знаю, у вас описка, или в книге.
Хоть попробуйте сформулировать, чем же вас так смутила безобидная запись.

Я не понимаю, как мне подставлять в сумму члены ряда. Не могу понять, что именно значит выражение $i+j+k=n$ и им подобные. А насчёт $i+2j=n$, скорее всего там условие $\leqslant$.

[Dan B-Yallay]

ShnurDash в сообщении #1531247 писал(а):

Не могу понять, что именно значит выражение $i+j+k=n$ и им подобные.

Это означает, что первое суммирование по ВСЕМ возможным триплетам ${i,\ j ,\ k}$, которые в сумме дают $n$,

второе суммирование по таким парам ${i, \ j}$, что $i+2j = n$

и третье - по таким $i$, что $i=n/3$.

В последнем случае знак суммы ни к чему, это какая-то казуистика.

-- Пт сен 10, 2021 11:30:48 --

Например, если $n=3$ то в первом суммировании надо рассмотреть такие комбинации:
3,0,0
2,1,0
1,1,1
1,2,0
0,3,0
0,1,2
0,0,3
1,0,2
2,0,1
0,2,1

Возможно я чего-то пропустил, надо проверять.

[ShnurDash]

Dan B-Yallay в сообщении #1531248 писал(а):

ShnurDash в сообщении #1531247 писал(а):

Не могу понять, что именно значит выражение $i+j+k=n$ и им подобные.

Это означает, что первое суммирование по ВСЕМ возможным триплетам ${i,\ j ,\ k}$, которые в сумме дают $n$,

второе суммирование по таким парам ${i, \ j}$, что $i+2j = n$

и третье - по таким $i$, что $i=n/3$.

В последнем случае знак суммы ни к чему, это какая-то казуистика.

-- Пт сен 10, 2021 11:30:48 --

Например, если $n=3$ то в первом суммировании надо рассмотреть такие комбинации:
3,0,0
2,1,0
1,1,1
1,2,0
0,3,0
0,1,2
0,0,3
1,0,2
2,0,1
0,2,1

Возможно я чего-то пропустил, надо проверять.

Спасибо за пояснение. Разрешите тогда задать дополнительный вопрос: возможен ли ещё какой-то способ упрощения варианта с производящей функцией? Или этот переход к суммам единственный?

[Dan B-Yallay]

Насчет других способов с наскоку не скажу. Может кто-то другой подскажет, более в теме.

Кстати, я только сейчас обратил внимание, что у вас $i, j, k \in \mathbb Z$, так что надо рассмативать комбинации и с отрицательными.

[ShnurDash]

Dan B-Yallay в сообщении #1531251 писал(а):

Насчет других способов с наскоку не скажу. Может кто-то другой подскажет, более в теме.

Кстати, я только сейчас обратил внимание, что у вас $i, j, k \in \mathbb Z$, так что надо рассмативать комбинации и с отрицательными.

Забыл дописать, что они неотрицательные. Теперь результат суммирований сходится с методом производящей. Спасибо. Попробую выделить какой-то общий алгоритм оценки. Ваши идеи приветствуются.

[Mikhail_K]

Dan B-Yallay в сообщении #1531248 писал(а):

и третье - по таким $i$, что $i=n/3$.

В последнем случае знак суммы ни к чему, это какая-то казуистика.

Видимо, имеется в виду, что в этой сумме может быть как одно слагаемое (если $n$ делится на три), так и нуль слагаемых (если не делится); в последнем случае сумма равна нулю.

[kotenok gav]

ShnurDash в сообщении #1531239 писал(а):

$g_{n+1} = \frac{1}{6}[\sum\limits_{i+j+k=n}^{}g_{i}g_{j}g_{k}+3\sum\limits_{i+2j}^{}g_{i}g_{j}+2\sum\limits_{3i=n}^{}g_{i}]$

Так а что, собственно, надо с этой формулой сделать? Упростить? Найти производящую функцию?

[ShnurDash]

kotenok gav в сообщении #1531273 писал(а):

ShnurDash в сообщении #1531239 писал(а):

$g_{n+1} = \frac{1}{6}[\sum\limits_{i+j+k=n}^{}g_{i}g_{j}g_{k}+3\sum\limits_{i+2j}^{}g_{i}g_{j}+2\sum\limits_{3i=n}^{}g_{i}]$

Так а что, собственно, надо с этой формулой сделать? Упростить? Найти производящую функцию?

Как раз таки переход от производящей функции к дейстию над числами. А вот эту сумму желательно упростить, дабы считать было легче, стоит задача сделать наглядный алгортм. Если есть другой метод перехода от производящей к действию над самими членами последовательности, то $C(x)=1+x+x^2+2x^3+4x^4...$ (коэффициент - число изомеров "спирта" $n$-ой степени, единица - нулевой член), функциональное уравнение приведено выше. Нужно найти более простой переход к действиям над числами, либо упростить имеещееся выражение с суммамм

[kotenok gav]

ShnurDash в сообщении #1531274 писал(а):

Как раз таки переход от производящей функции к дейстию над числами.

От производящей функции чего именно?

[iifat]

kotenok gav в сообщении #1531276 писал(а):

От производящей функции чего именно?

Ну, производящие функции производят последовательности чисел Боле ничего они производить не умеют.
И нет, боюсь, проще не получится.
Вопрос разве что — на кой это делать людям? Человечество давно уж придумало как минимум два способа ничего не считать: составить агромадные таблицы либо использовать компьютер. Или вам, ShnurDash, потребны десятимиллиардные члены последовательности?

[ShnurDash]

iifat в сообщении #1531280 писал(а):

kotenok gav в сообщении #1531276 писал(а):

От производящей функции чего именно?

Ну, производящие функции производят последовательности чисел Боле ничего они производить не умеют.
И нет, боюсь, проще не получится.
Вопрос разве что — на кой это делать людям? Человечество давно уж придумало как минимум два способа ничего не считать: составить агромадные таблицы либо использовать компьютер. Или вам, ShnurDash, потребны десятимиллиардные члены последовательности?

Нужно сделать алгоритм более наглядным, условие следующее "предложите наглядный алгортм оценки числа изомеров спиртов, который можно использовать на уроках в школе". Предполагается, что оценка производится у больших значений n. Для химии это $n\geqslant 10$

[Sender]

Если хочется наглядности, может, стоит посмотреть в сторону поиска рекуррентных соотношений?

[ShnurDash]

Sender в сообщении #1531294 писал(а):

Если хочется наглядности, может, стоит посмотреть в сторону поиска рекуррентных соотношений?

Та формула с суммами и есть рекуррентная. Но проблема в том, что для больших значений N нужно перебирать много вариантов, не так много как при прямом вращении молекул, но всё же. Этого дефекта лишена функциональная формула, но она требует громоздких действий с многочленами. Есть ли вариант упрощение этой формулы?