Распределение порядка во всех перестановках

[Scholium]

В процессе реализации алгоритма сортировки естественным слиянием возникла следующая несложная комбинаторная задача. Может, кто подскажет ее решение.

Дано множество всех перестановок натуральных чисел от 1 до n. Сколько в них будет упорядоченных (по возрастанию или убыванию) подпоследовательностей длины $Q_n(k)$ для $1 \leqslant k \leqslant n$? Случай $k = 1$ будем рассматривать только для тех перестановок, которые дают «зависшую» подпоследовательность длины 1 в конце перестановки. Порядок подпоследовательностей рассматривается относительно начала перестановки. Подпоследовательности рассматриваются до тех пор, пока сохраняется их локальный порядок и не пересекаются между собой. Также интересует средняя длина таких упорядоченных подпоследовательностей.

Очевидно, что $Q_n(n) = 2$. Но для остальных k формулы, очевидно, будут сложнее.

[AKM]

Только подсказки по набору формул.

Не надо вставлять [mаth]...[/mаth]. Тэги вставятся автоматически при интрерпретации сообщения. Необходимо (и достаточно) окружить формулу знаками доллара: $ Q_n(n-m) $ --- $ Q_n(n-m) $.
$ 2< k \le n$ --- $ 2< k \le n$ (команды \le, \ge).

[Scholium]

AKM в сообщении #251280 писал(а):

Только подсказки по набору формул.

Не надо вставлять [mаth]...[/mаth]. Тэги вставятся автоматически при интрерпретации сообщения. Необходимо (и достаточно) окружить формулу знаками доллара: $ Q_n(n-m) $ --- $ Q_n(n-m) $.
$ 2< k \le n$ --- $ 2< k \le n$ (команды \le, \ge).

Понял, спасибо .

[gris]

Мне больше нравится $\geqslant$ и $\leqslant$ .
Вопрос к Scholium: подпоследовательности одной перестановки могут пересекаться? Подпоследовательность - это члены последовательности, идущие подряд по номерам или возможны разрывы?

Например, для перестановки $12345$ сколько подпоследовательностей длины 3?
$123\quad 234 \quad 345$ или только одна из них?
$134$ не считается?

[Scholium]

gris в сообщении #251284 писал(а):

Мне больше нравится $\geqslant$ и $\leqslant$ .
Вопрос к Scholium: подпоследовательности одной перестановки могут пересекаться? Подпоследовательность - это члены последовательности, идущие подряд по номерам или возможны разрывы?

Например, для перестановки $12345$ сколько подпоследовательностей длины 3?
$123\quad 234 \quad 345$ или только одна из них?
$134$ не считается?

Спасибо насчет знаков неравенств!

В последовательности 12345 нет подпоследовательностей длины 3, так как здесь есть только одна подпоследовательность длины 5! Соответственно никаких пересечений не предусматривается. Задача появилась в алгоритме сортировки, в котором последовательно с начала произвольной перестановки выбирались упорядоченные (в любом порядке) подпоследовательности, пока они не заканчивались. У меня опубликован демонстрационный алгоритм этой сортировки (ее нелинейный вариант), если интересно могу дать ссылку. Кстати эксперименты со случайными последовательностями натуральных чисел показали, что средняя длина упорядоченных подпоследовательностей лежит в пределах от 2.41 до 2.42. Но хотелось бы найти это число теоретически.

[Maslov]

А в последовательности 14325 есть возрастающая подпоследовательность длины 3? 135 с разрывами считается?

[Хорхе]

Пусть $\mathcal N$ - семейство наборов номеров, по которым мы берем подпоследовательность.

Удобно писать в первом случае

$$ S_N = \sum_{N\in \mathcal N} I_{N\text{-подпоследовательность монотонна}}. $$

и во втором случае

$$ L_N = \frac{1}{|\mathcal N|}\sum_{N\in \mathcal N} |N|I_{N\text{-подпоследовательность монотонна}}. $$

Тогда, например, в первом случае

$$ E[S_N] = \sum_{N\in \mathcal N} \frac{1+1_{|N|\ge 2}}{|N|!}, $$

во втором:

$$ E[L_N] = \frac{1}{|\mathcal N|}\sum_{N\in \mathcal N} \frac{1+1_{|N|\ge 2}}{(|N|-1)!} $$

[nn910]

Тогда осталось непонимание про последовательность в форме W: 52314 это 4 подпоследовательности длины 2 или две,и если 2 то какие? Это же влияет на статистику

[Scholium]

Maslov в сообщении #251286 писал(а):

А в последовательности 14325 есть возрастающая подпоследовательность длины 3? 135 с разрывами считается?

В этой последовательности будет три упорядоченных подпоследовательности:
14, 32 и 5, соответственно две подпоследовательности длины 2 и одна 1.

nn910 в сообщении #251289 писал(а):

Тогда осталось непонимание про последовательность в форме W: 52314 это 4 подпоследовательности длины 2 или две,и если 2 то какие? Это же влияет на статистику

Смотрите, мы имеем объединение упорядоченных подпоследовательностей: $52314 = 52 + 31 + 4$.

[Maslov]

Scholium в сообщении #251291 писал(а):

Maslov в сообщении #251286 писал(а):
А в последовательности 14325 есть возрастающая подпоследовательность длины 3? 135 с разрывами считается?

В этой последовательности будет три упорядоченных подпоследовательности:
14, 32 и 5, соответственно две подпоследовательности длины 2 и одна 1.

Извините, что-то мне логику никак не уловить. А 432 почему не считаем?

[Scholium]

Хорхе в сообщении #251287 писал(а):

Пусть $\mathcal N$ - семейство наборов номеров, по которым мы берем подпоследовательность.

Удобно писать в первом случае

$$ S_N = \sum_{N\in \mathcal N} I_{N\text{-подпоследовательность монотонна}}. $$

и во втором случае

$$ L_N = \frac{1}{|\mathcal N|}\sum_{N\in \mathcal N} |N|I_{N\text{-подпоследовательность монотонна}}. $$

Тогда, например, в первом случае

$$ E[S_N] = \sum_{N\in \mathcal N} \frac{1+1_{|N|\ge 2}}{|N|!}, $$

во втором:

$$ E[L_N] = \frac{1}{|\mathcal N|}\sum_{N\in \mathcal N} \frac{1+1_{|N|\ge 2}}{(|N|-1)!} $$

Ну, это больше похоже на определения, чем на вычисления, к тому же, не совсем понятны обозначения.

[Maslov]

Мы что, просто разбиваем каждую перестановку на "отрезки монотонности"?

[Scholium]

Maslov в сообщении #251293 писал(а):

Scholium в сообщении #251291 писал(а):

Maslov в сообщении #251286 писал(а):
А в последовательности 14325 есть возрастающая подпоследовательность длины 3? 135 с разрывами считается?

В этой последовательности будет три упорядоченных подпоследовательности:
14, 32 и 5, соответственно две подпоследовательности длины 2 и одна 1.

Извините, что-то мне логику никак не уловить. А 432 почему не считаем?

Во-первых, мы идем сначала (слева направо), во-вторых, подпоследовательность выбираем до тех пор, пока существует ее локальный порядок и, в-третьих, подпследовательности не должны пересекаться. Смотрите, после единицы четверка образует локальное возрастание, а тройка дает локальное убывание. Отсекаем возрастание 14 и начинаем процедуру заново к оставшейся подпоследовательности 325. Здесь порядок начинается с убывания – 32. Пятерка нарушает этот порядок, она остается после отсечения 32 от 325. Таким образом, получаем «равенство»: 14325 = 14 + 32 + 5.

-- Вт окт 13, 2009 15:02:19 --

Для лучшего восприятия можно посмотреть мою тему: «Нелинейная demo реализация сортировки естественным слиянием (Natural Merge Sort) на Visual FoxPro» на:
http://sql.ru/forum/actualthread.aspx?bid=24&tid=686605&pg=2 .

-- Вт окт 13, 2009 15:10:34 --

Maslov в сообщении #251296 писал(а):

Мы что, просто разбиваем каждую перестановку на "отрезки монотонности"?

Ну, да! Я же говорю, что задача не должна быть сложной. Только мы рассматриваем эти «отрезки монотонности» (для убывающей и неубывающей подпоследовательностей) на всем множестве, всех перестановок натуральных чисел от 1 до n. Общее количество таких перестановок равно n! . Нам надо подсчитать количество всех подпоследовательностей заданной длины k и среднюю длину такой подпоследовательности, которая экспериментально определена в пределах от 2,41 до 2,42.

[Хорхе]

Scholium в сообщении #251294 писал(а):

Ну, это больше похоже на определения, чем на вычисления, к тому же, не совсем понятны обозначения.

После ваших объяснений, как оно на самом деле должно формулироваться, уже не важно. Не так страшно, что вы не пишете внятную постановку задачи сразу же, как то, что вы не извиняетесь за то, что вы этого не сделали. Не украшает такое поведение.

[Scholium]

Хорхе в сообщении #251308 писал(а):

Scholium в сообщении #251294 писал(а):

Ну, это больше похоже на определения, чем на вычисления, к тому же, не совсем понятны обозначения.

После ваших объяснений, как оно на самом деле должно формулироваться, уже не важно. Не так страшно, что вы не пишете внятную постановку задачи сразу же, как то, что вы не извиняетесь за то, что вы этого не сделали. Не украшает такое поведение.

К сожалению, я не понимаю ваших эмоций. Два человека одно и тоже событие видят по разному. Для меня формулировка задачи в теме была и остается достаточно понятной, но в любом случае дополнительные объяснения неизбежны, хотя бы потому, что задача новая и формулировка еще не «утряслась». За что ж тут извиняться? Вы всегда формулируете новые утверждения без дальнейшей правки? Думаю, что не надо быть слишком требовательным к другим, ибо люди не идеальны и никогда не будут таковыми. Так что давайте, без взаимных упреков .