2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Об ожерельях и производящей функции для числа инверсий
Сообщение01.08.2012, 21:02 


08/05/08
954
MSK
Задача об ожерельях хорошо известна, когда "The number of fixed necklaces of length $n$ composed of $a$ types of beads $N(n,a)$ может быть вычеслено.
http://mathworld.wolfram.com/Necklace.html

Рассмотрим предел произведения $\lim_{n\to \infty}\prod_{p=1}^n N(p,a)$
Нетрудно показать, что с точностью до несущественного множителя предел совпадает с производящей функцией для числа инверсий

Возникает вопрос, как можно объяснить данный результат "на пальцах", каково влияние свойств симметрической группы?

 Профиль  
                  
 
 Re: Об ожерельях и производящей функции для числа инверсий
Сообщение02.08.2012, 20:45 
Заслуженный участник


08/01/12
915
e7e5 в сообщении #602032 писал(а):
Нетрудно показать, что с точностью до несущественного множителя предел совпадает с производящей функцией для числа инверсий

Я ничего не понял; предел произведений чисел совпадает с функцией? Производящая функция какой именно последовательности (функции от какого натурального параметра)?

 Профиль  
                  
 
 Re: Об ожерельях и производящей функции для числа инверсий
Сообщение02.08.2012, 21:51 


08/05/08
954
MSK
apriv в сообщении #602466 писал(а):
e7e5 в сообщении #602032 писал(а):
Нетрудно показать, что с точностью до несущественного множителя предел совпадает с производящей функцией для числа инверсий

Я ничего не понял; предел произведений чисел совпадает с функцией? Производящая функция какой именно последовательности (функции от какого натурального параметра)?

$\frac {a^n} {n!}$ $\prod_{p=1}^n \frac {1-a^p} {1-a}$

 Профиль  
                  
 
 Re: Об ожерельях и производящей функции для числа инверсий
Сообщение02.08.2012, 22:11 
Заслуженный участник


08/01/12
915
Вы пока что не ответили ни на один из моих вопросов. Кроме того, указанная Вами производящая функция не очень-то похожа на произведение формул для числа ожерелий.

 Профиль  
                  
 
 Re: Об ожерельях и производящей функции для числа инверсий
Сообщение03.08.2012, 07:07 


08/05/08
954
MSK
apriv в сообщении #602506 писал(а):
Кроме того, указанная Вами производящая функция не очень-то похожа на произведение формул для числа ожерелий.

рассматриваемый предел для задачи об Ожерельях ( не забудем, что рассматриваем $n \to \infty$ можно представить в виде ( аппроксимировать):
$\frac {a^n} {n!}$ $\prod_{p=1}^n \frac {1-a^p} {1-a}$

Если отбросить множитель $\frac {a^n} {n!}$, то $\prod_{p=1}^n \frac {1-a^p} {1-a}$
по виду напоминает производящую функцию для числа инверсий, например Теорема 1 в работе:
www.cs.uwaterloo.ca/journals/JIS/VOL4/M ... rsions.pdf

 Профиль  
                  
 
 Re: Об ожерельях и производящей функции для числа инверсий
Сообщение03.08.2012, 08:35 
Заслуженный участник


08/01/12
915
e7e5 в сообщении #602600 писал(а):
рассматриваемый предел для задачи об Ожерельях ( не забудем, что рассматриваем $n \to \infty$ можно представить в виде ( аппроксимировать):

Представить его в таком виде нельзя, а аппроксимировать, может, и можно, только нужно уточнить, что это вообще значит — аппроксимировать производящую функцию. Пока что ее коэффициенты от этой «аппроксимации» уезжают куда-то далеко.

 Профиль  
                  
 
 Re: Об ожерельях и производящей функции для числа инверсий
Сообщение03.08.2012, 09:12 


08/05/08
954
MSK
apriv в сообщении #602608 писал(а):
Представить его в таком виде нельзя, а аппроксимировать, может, и можно, только нужно уточнить, что это вообще значит — аппроксимировать производящую функцию.


Всего лишь утверждается, что при $n \to \infty$ выполняется асимптотическое равенство
$\prod_{p=1}^n N(p,a) \approx \frac {a^n} {n!}$ $\prod_{p=1}^n \frac {1-a^p} {1-a}$
Здесь еще мы не говорим о производящей функции.

 Профиль  
                  
 
 Re: Об ожерельях и производящей функции для числа инверсий
Сообщение29.07.2014, 11:17 


12/07/14
8
e7e5 в сообщении #602600 писал(а):
Если отбросить множитель $\frac {a^n} {n!}$

А как получился этот самый множитель?

 Профиль  
                  
 
 Re: Об ожерельях и производящей функции для числа инверсий
Сообщение13.08.2014, 20:16 


08/05/08
954
MSK
aspair в сообщении #891248 писал(а):
e7e5 в сообщении #602600 писал(а):
Если отбросить множитель $\frac {a^n} {n!}$

А как получился этот самый множитель?

Множитель появляется при оценке произведения, используя теорему Пойа.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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