2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Снова о числах Стирлинга
Сообщение16.02.2014, 08:41 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
1. Как известно, у чисел Стирлинга первого рода (без знака) есть два разных определения. Первое из них определяет число $\left[n \atop k\right]$ как количество перестановок порядка $n$, содержащих ровно $k$ циклов. Второе определяет его же как коэффициент при $x^k$ многочлена $x(x+1)\dots(x+n-1)$, т.е. $$\left[n \atop k\right]=\sum_{1 \leqslant y_1<y_2< \dots <y_{n-k}<n} {y_1 y_2 \dots y_{n-k}} \, . \eqno(1)$$Дайте комбинаторное доказательство того, что эти определения эквивалентны. Точнее, постройте алгоритм, позволяющий каждой перестановке порядка $n$ с $k$ циклами сопоставить $n-k$ пар натуральных чисел $(x_1,y_1),(x_2,y_2),\dots,(x_{n-k},y_{n-k})$, таких, что $y_1<y_2< \dots <y_{n-k}<n$ и $\forall i \colon x_i \leqslant y_i$, а также произвести обратное преобразование.

2. Докажите тождество $$\sum_{i+j=n} \, {\frac {a!} {i!} \left[i \atop a\right] \frac {b!} {j!} \left[j \atop b\right]}=\frac {(a+b)!} {n!} \left[n \atop {a+b}\right],$$ для любых натуральных $a,b,n$.

 Профиль  
                  
 
 Re: Снова о числах Стирлинга
Сообщение18.02.2014, 13:33 
Заслуженный участник


16/02/13
4105
Владивосток

(Оффтоп)

1) Так я и думал: очень простая задача. Так я и думал все эти два дня (хм. А казалось, не меньше недели прошло). И был прав! :wink:
Крутим циклы, чтобы максимальный элемент шёл последним, располагаем их по возрастанию оного максимального элемента. После этого, в порядке $n,n-1,n-2\dots$ каждое число вычёркиваем, для последних элементов цикла тем и ограничиваемся, для прочих запоминаем пару "позиция в списке — число". Циклы по набору таких пар строятся в обратном порядке.

 Профиль  
                  
 
 Re: Снова о числах Стирлинга
Сообщение18.02.2014, 23:47 


23/11/09
173
1. Запишем перестановку, в виде строки циклов, а циклы в строке упорядочим по возрастанию их максимального элемента, который установим на первое место. Такая запись, очевидно, взаимно однозначна. Затем, сопоставим этой строке перестановку чисел в порядке их следования в строке. Например, для перестановки $(1347526)$ получим строку $(1)(5)(76234)$ и для нее перестановку $(1576234)$. Теперь взаимно однозначно сопоставим перестановке набор из $n$ чисел, в котором $i$-ое число набора равно числу инверсий элемента $i$ в перестановке (количеству элементов больших $i$ и расположенных левее). Для нашего примера это $(0,3,3,3,0,1,0)$.
i-ое число в таком наборе может быть от нуля до $n-i$. Если в исходной перестановке $k$ циклов, то в преобразованной перестановке будет $k$ смен максимального элемента во время чтения ее слева направо и в наборе инверсий будет ровно $k$ нулей по индексам равным соответствующим максимумам при чтении слева направо. За пары $(x,y)$ можно брать пары индекс-значение в наборе инверсий для ненулевых элементов. При этом индекс отсчитывается от нуля и справа. В нашем примере это: $(1,1), (3,3), (3,4), (3,5)$.
Обратный алгоритм, строящий перестановку по набору инверсий тоже простой и изящный. Будем последовательно пополнять набор (первоначально пустой, а в конце представляющий перестановку) числами i от n до 1 по следующему правилу: число поставим в строке на $a_i$ место от левого элемента. Где $a_i$ это число инверсий $i$-ого элемента. Сложность алгоритма вроде $n\log(n)$

Кстати, у Стэнли в перечислительной комбинаторике есть такое же упражнение на построение биекции, где дается указание к его решению. И там много важных комбинаторных интерпретаций перестановок (одного из самых богатых объектов перечислительной комбинаторики) и соответственно чисел Стирлинга, что обеспечивает неожиданные доказательства разных тождеств.

2. Нет идей как использовать здесь 1.
Можно переписать тождество через биномиальные коэффициенты (чтобы сделать обе части целочисленными) и далее доказывать комбинаторно, но задумка наверное в другом.

 Профиль  
                  
 
 Re: Снова о числах Стирлинга
Сообщение19.02.2014, 08:31 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
deep blue в сообщении #828253 писал(а):
2. Нет идей как использовать здесь 1.
Можно переписать тождество через биномиальные коэффициенты (чтобы сделать обе части целочисленными) и далее доказывать комбинаторно, но задумка наверное в другом.
А 1 использовать никто и не требовал. На самом деле эта часть проще первой и комбинаторное доказательство указанным Вами способом практически очевидно.
deep blue в сообщении #828253 писал(а):
Кстати, у Стэнли в перечислительной комбинаторике есть такое же упражнение на построение биекции, где дается указание к его решению. И там много важных комбинаторных интерпретаций перестановок (одного из самых богатых объектов перечислительной комбинаторики) и соответственно чисел Стирлинга, что обеспечивает неожиданные доказательства разных тождеств.
Эту задачу я там не заметил. А какой номер упражнения, если не секрет?

(Оффтоп)

Стенли плох тем, что даёт в своей книге упражнения, называя их простыми, а вместо решения иногда вываливает ссылки на научную литературу, что никак нельзя считать нормальным подходом в учебном пособии. Взять, к примеру, задачу (копия). Стенли предлагает дать комбинаторное доказательство (у него это задача 2с в первой главе), а сам хитрит и даёт только некомбинаторное.
Предлагаю подумать над комбинаторным, задача очень интересная. Решение, если что, есть в интернете.

Вообще же, эта тема, по сути, посвящена свёртке Вандермонда. Второе тождество говорит о том, что для чуть преобразованных чисел Стирлинга $D(k,n)=\frac {n!} {k!} \!\! \left[k \atop n\right]$ верно то же тождество, что и для биномиальных коэффициентов $n \choose k$. Мне этот факт показался красивым.
Обе же части в совокупности можно использовать для обобщения обычной свёртки Вандермонда на действительные показатели степени без использования рядов. Обратите внимание, например, на это сообщение.

 Профиль  
                  
 
 Re: Снова о числах Стирлинга
Сообщение19.02.2014, 20:15 
Модератор
Аватара пользователя


11/01/06
5660
Dave в сообщении #827063 писал(а):
2. Докажите тождество $$\sum_{i+j=n} \, {\frac {a!} {i!} \left[i \atop a\right] \frac {b!} {j!} \left[j \atop b\right]}=\frac {(a+b)!} {n!} \left[n \atop {a+b}\right],$$ для любых натуральных $a,b,n$.

Легко следует из экспоненциальной производящей функции для чисел Стирлинга - см., например, формулу (12) в
http://mathworld.wolfram.com/StirlingNu ... tKind.html

 Профиль  
                  
 
 Re: Снова о числах Стирлинга
Сообщение21.02.2014, 14:00 


23/11/09
173
Dave в сообщении #828379 писал(а):
А какой номер упражнения, если не секрет?
Задача решается по ходу второго доказательства предложения 1.3.4.
Dave в сообщении #828379 писал(а):
Взять, к примеру, задачу. Стенли предлагает дать комбинаторное доказательство (у него это задача 2с в первой главе), а сам хитрит и даёт только некомбинаторное.
Предлагаю подумать над комбинаторным, задача очень интересная.
Да, хорошая задача надо будет как-нибудь обдумать.
maxal в сообщении #828593 писал(а):
Dave в сообщении #827063
писал(а):
2. Докажите тождество $$\sum_{i+j=n} \, {\frac {a!} {i!} \left[i \atop a\right] \frac {b!} {j!} \left[j \atop b\right]}=\frac {(a+b)!} {n!} \left[n \atop {a+b}\right],$$ для любых натуральных $a,b,n$.
Легко следует из экспоненциальной производящей функции для чисел Стирлинга
Тоже подумал о той производящей функции когда увидел факториалы в знаменателях при числах Стирлинга. Но не довел это до решения.

 Профиль  
                  
 
 Re: Снова о числах Стирлинга
Сообщение21.02.2014, 14:23 
Заслуженный участник


16/02/13
4105
Владивосток
Да тоже, в общем, несложно. Как оказалось :wink: Хотим посчитать $\left[n\atop a+b\right]$. Поступаем таким вот извращённым способом: отбираем $i$ элементов, строим перестановку на $a$ циклов, из остатка — соответственно, на $b$, совокупляем — получили $\left(n\atop i\right)\left[i\atop a\right]\left[j\atop b\right]$. Потом суммируем. Осталось не забыть, что каждая перестановка будет посчитана $\left(a+b\atop a\right)$ раз.

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


03/12/11
640
Україна
iifat, именно это решение я и имел ввиду (думаю, что и deep blue тоже), когда говорил, что комбинаторное доказательство практически очевидно.
Решение через производящие здесь тоже сразу напрашивается и показывает мультипликативность производящей функции. Точно так же, как и обычная свёртка Вандермонда показывает равенство $$(1+x)^a \, (1+x)^b=(1+x)^{a+b}.$$Но задача поиска именно комбинаторного доказательства (не только в данной теме, а вообще), помимо чисто олимпиадного или учебного интереса, актуальна не только сама по себе. Я не случайно упомянул слово алгоритм в постановке задачи и привёл "компьютерную" интерпретацию правой части (1). Если мы возьмём упомянутую задачу из Стенли, то её комбинаторное решение можно применить, например, в криптографии для преобразования ключа или сообщения, в котором частота единиц отличается от $\frac 1 2$, в строку с частотой ровно $\frac 1 2$ (ну и плюс небольшой заголовок, который, ввиду малого размера, погоды не делает).

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

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



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

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


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

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