2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Помогите разобраться с вычислением суммы
Сообщение10.09.2021, 18:17 


21/10/19
14
Здравствуйте. Стоит задача - получить удобную формулу для числа изомеров насыщенных одноатомных спиртов. Формула Пойа (в дебри дискретной математики не вдавался, привожу итоговый результат) задаётся следующим образом: $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}$. Меня очень смутили выражения в условии суммирования. Пожалуйста, натолкните на правильную мысль, Заранее спасибо.

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение10.09.2021, 20:01 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение10.09.2021, 20:09 


21/10/19
14
iifat в сообщении #1531246 писал(а):
Вам бы, эээ, вопрос сформулировать, глядишь, и натолкнули б.
В альтернативном варианте в средней сумме явно $i+2j=n$, уж не знаю, у вас описка, или в книге.
Хоть попробуйте сформулировать, чем же вас так смутила безобидная запись.


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

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение10.09.2021, 20:26 
Заслуженный участник
Аватара пользователя


11/12/05
9953
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

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

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение10.09.2021, 20:42 


21/10/19
14
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

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


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

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение10.09.2021, 20:55 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение10.09.2021, 21:01 


21/10/19
14
Dan B-Yallay в сообщении #1531251 писал(а):
Насчет других способов с наскоку не скажу. Может кто-то другой подскажет, более в теме.

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

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

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение11.09.2021, 05:12 
Заслуженный участник
Аватара пользователя


26/01/14
4601
Dan B-Yallay в сообщении #1531248 писал(а):
и третье - по таким $i$, что $i=n/3$.

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

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение11.09.2021, 09:39 


21/05/16
4292
Аделаида
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}]$

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

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение11.09.2021, 09:53 


21/10/19
14
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$-ой степени, единица - нулевой член), функциональное уравнение приведено выше. Нужно найти более простой переход к действиям над числами, либо упростить имеещееся выражение с суммамм

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение11.09.2021, 10:03 


21/05/16
4292
Аделаида
ShnurDash в сообщении #1531274 писал(а):
Как раз таки переход от производящей функции к дейстию над числами.

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

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение11.09.2021, 11:02 
Заслуженный участник


16/02/13
4105
Владивосток
kotenok gav в сообщении #1531276 писал(а):
От производящей функции чего именно?
Ну, производящие функции производят последовательности чисел :wink: Боле ничего они производить не умеют.
И нет, боюсь, проще не получится.
Вопрос разве что — на кой это делать людям? Человечество давно уж придумало как минимум два способа ничего не считать: составить агромадные таблицы либо использовать компьютер. Или вам, ShnurDash, потребны десятимиллиардные члены последовательности?

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение11.09.2021, 11:13 


21/10/19
14
iifat в сообщении #1531280 писал(а):
kotenok gav в сообщении #1531276 писал(а):
От производящей функции чего именно?
Ну, производящие функции производят последовательности чисел :wink: Боле ничего они производить не умеют.
И нет, боюсь, проще не получится.
Вопрос разве что — на кой это делать людям? Человечество давно уж придумало как минимум два способа ничего не считать: составить агромадные таблицы либо использовать компьютер. Или вам, ShnurDash, потребны десятимиллиардные члены последовательности?


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

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение11.09.2021, 14:51 


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

 Профиль  
                  
 
 Re: Помогите разобраться с вычислением суммы
Сообщение11.09.2021, 16:59 


21/10/19
14
Sender в сообщении #1531294 писал(а):
Если хочется наглядности, может, стоит посмотреть в сторону поиска рекуррентных соотношений?


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group