2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Кострикин Сборник задач по алгебре 5.3
Сообщение01.05.2019, 22:02 


23/04/18
143
Пусть $S_n$ множество всех перестановок длины $n$, $\sigma\in S_n$, тогда $|\left\lbrace i|\sigma(i)=i\right\rbrace|=N(\sigma)$ - это количество циклов длины 1 в перестановке $\sigma$. Требуется доказать, что если $\sum\limits_{\sigma\in S_n}^{}N(\sigma)^s=\gamma(s)n!$ и $1\leqslant s\leqslant n$, то $\gamma(s+1)=\sum\limits_{k=0}^{s-1}\binom{s}{k}\gamma(s-k)+1$.
Иначе последнее равенство можно сформулировать так: $\sum\limits_{\sigma\in S_n}^{}N(\sigma)^{s+1}=\sum\limits_{\sigma\in S_n}^{}(N(\sigma)+1)^s$.
Доказательство по индукции у меня, к сожалению, никак не получается провести, так как действует ограничение $1\leqslant s\leqslant n$ и если s не вписывается в данное ограничение, то последнее равенство вообще перестаёт быть верным. Я также пробовал подойти к решению более прямо и подсчитать сколько есть перестановок $\sigma\in S_n$ для которых $N(\sigma)=p$ для любого p, вполне конкретную формулу вывести, конечно, получилось, вот только она ничего не даёт.
В конце данного сборника представлено решение, но написано оно в одну строчку и понять его у меня не получилось.
Нужны идеи.

 Профиль  
                  
 
 Re: Кострикин Сборник задач по алгебре 5.3
Сообщение02.05.2019, 11:43 
Аватара пользователя


24/03/19
147
Полезно рассмотреть сумму $\sum\limits_{\sigma\in S_n, \sigma(i)=i}{N(\sigma)^s}.$ Её удобно свести к случаю с $n-1$ элементами; дело в том, что элемент $i$ остается на месте, поэтому дело фактически сводится к перестановкам $n-1$ элементов. Делая это для каждого элемента $i,$ можно получить требуемое соотношение между $\gamma(s).$

После этого останется доказать, что $\sum\limits_{\sigma\in S_n}{N(\sigma) = n!},$ или, что равносильно, $\gamma(1)=1.$ В этом плане есть продвижения?

 Профиль  
                  
 
 Re: Кострикин Сборник задач по алгебре 5.3
Сообщение02.05.2019, 12:08 
Заслуженный участник


18/01/15
3221
Общая идея: когда в задаче есть натуральный параметр, сначала надо ее пытаться решать при малых значениях параметра. Конкретно для данной задачи: выяснить, чему равно $\gamma(1)$, $\gamma(2)$, $\gamma(3)$ (и написать подробное доказательство для этих случаев). А там, возможно, общую идею увидите (или во всяком случае помогающим будет легче объяснить Вам, в чем эта общая идея состоит). В частности, присоединяюсь к вопросу
SiberianSemion в сообщении #1390663 писал(а):
доказать, что $\sum\limits_{\sigma\in S_n}{N(\sigma) = n!},$ или, что равносильно, $\gamma(1)=1.$ В этом плане есть продвижения?

 Профиль  
                  
 
 Re: Кострикин Сборник задач по алгебре 5.3
Сообщение02.05.2019, 17:26 


23/04/18
143
SiberianSemion,vpb, спасибо, идею поймал. Этот план действительно рабочий.

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

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



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

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


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

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