Снова о числах Стирлинга

[Dave]

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$.

[iifat]

(Оффтоп)

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

[deep blue]

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.
Можно переписать тождество через биномиальные коэффициенты (чтобы сделать обе части целочисленными) и далее доказывать комбинаторно, но задумка наверное в другом.

[Dave]

deep blue в сообщении #828253 писал(а):

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

А 1 использовать никто и не требовал. На самом деле эта часть проще первой и комбинаторное доказательство указанным Вами способом практически очевидно.

deep blue в сообщении #828253 писал(а):

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

Эту задачу я там не заметил. А какой номер упражнения, если не секрет?

(Оффтоп)

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

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

[maxal]

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

[deep blue]

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$.
Легко следует из экспоненциальной производящей функции для чисел Стирлинга

Тоже подумал о той производящей функции когда увидел факториалы в знаменателях при числах Стирлинга. Но не довел это до решения.

[iifat]

Да тоже, в общем, несложно. Как оказалось Хотим посчитать $\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)$ раз.

[Dave]

iifat, именно это решение я и имел ввиду (думаю, что и deep blue тоже), когда говорил, что комбинаторное доказательство практически очевидно.
Решение через производящие здесь тоже сразу напрашивается и показывает мультипликативность производящей функции. Точно так же, как и обычная свёртка Вандермонда показывает равенство

$$(1+x)^a \, (1+x)^b=(1+x)^{a+b}.$$

Но задача поиска именно комбинаторного доказательства (не только в данной теме, а вообще), помимо чисто олимпиадного или учебного интереса, актуальна не только сама по себе. Я не случайно упомянул слово алгоритм в постановке задачи и привёл "компьютерную" интерпретацию правой части (1). Если мы возьмём упомянутую задачу 2с из Стенли, то её комбинаторное решение можно применить, например, в криптографии для преобразования ключа или сообщения, в котором частота единиц отличается от $\frac 1 2$, в строку с частотой ровно $\frac 1 2$ (ну и плюс небольшой заголовок, который, ввиду малого размера, погоды не делает).