Количество размещений "кактуса" по n (комбинаторная задача)

[Mihaylo]

Нужно решить следующую теоретически полезную задачу (для исследования эффективности алгоритма сортировки).

Имеется ориентированный граф в форме дерева, которое я называю "кактусом". См. рисунок:

Это дерево поиска (не бинарное), то есть в каждой вершине графа находится некоторое число, дуга указывает на бинарное отношение между числами. Дуга исходит из вершины с бОльшим числом и входит в вершину с меньшим числом.
Дерево типа "Кактус" характеризуется высотой ствола $m$ и количеством листьев $k_i$ на каждой вершине ствола.

Нужно определить количество размещений чисел "кактуса" по $n$, где $n \geqslant m+\sum\limits_{}^{}k_i$. При этом числа кактуса должны размещаться по возрастанию в соответствии с графом.

Решил задачу для частного случая - для дерева, которое я называю "бамбуком". Это когда $k_i=0$, для всех $i$.
Формула имеет вид:
$AB(m,n)=\frac{n!}{m!\cdot(n-m)!}$

Пример размещения "кактуса":


---
Если требуются какие-то пояснения и уточнения, пишите. Мне с моей стороны не видно, насколько четко я изложил задачу.

[VAL]

Mihaylo в сообщении #1036053 писал(а):

Если требуются какие-то пояснения и уточнения, пишите. Мне с моей стороны не видно, насколько четко я изложил задачу.

Сформулировали довольно путано и расплывчато.
Зато четко и последовательно нарушили целый ряд правил форума.
Советую сделать наоборот.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Mihaylo
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[sqribner48]

Mihaylo
Графы, подобные графу, который Вы изобразили, в литературе называются гусеницами (caterpillar). Граф, называемый Вами бамбуком -- это простая цепь. А кактусами в литературе по теории графов принято называть графы другого вида.
Вообще непонятна постановка вопроса.
Мне кажется, что заданному Вами неравенству $n \geqslant m+\sum\limits_{}^{}k_i$ удовлетворяет бесконечное количество чисел $n$. Так, для графа, изображенного на Вашем рисунке, минимальное значение $n=4+(0+2+1+3)= 10$. Тогда вершины графа можно пронумеровать следующим образом: 1-му узлу присвоить номер 10, 2-ому узлу - 9 (смежным с ним узлам -- номера 8 и 7), третьему узлу присвоить номер 6 (а смежному с ним узлу - номер 5), четвертый узел будет иметь номер 4, а смежные с ним узлы -номера 3, 2, 1 соответственно. Такая нумерация вершин удовлетворяет Вашему условию. Другие подобные нумерации с большими значениями $n$ можно получить добавляя числа 1, или 2, или 3... и т.п. ко всем вышеуказанным номерам вершин.
Если я не прав, то объясните в чем именно.
Мне также непонятно правило, согласно которому Вы расставляете номера вершин в цепочке клеток. Например, почему число 51 далеко "уехало" от числа 64, числа 50 и размещено за числом 9. Прошу разъяснить.

[Mihaylo]

Хорошо. Будем применять термины "гусеница" и "простая цепь".

Второй момент, который хотелось бы отметить. Я обнаружил, что пытаюсь определить не просто количество размещений, а количество перестановок с ограничением. Перестанавливать требуется $(m+\sum\limits_{}^{}k_i)$ чисел и $(n-m-\sum\limits_{}^{}k_i)$ пустых клеток, т.е. всего $n$ элементов в $n$ ячейках.

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

[iancaple]

Вроде понятно. Может ли быть компактная формула, мне неизвестно, но рекуррентность рулит.
Немного изменим обозначение числа размещений в простой цепи, так, чтобы оно годилось и для гусениц:$AB_n(k_1,...,k_m)$,
для простой цепи $AB_n(0,0...0)=C^m_n=\dfrac{n!}{m!(n-m)!}$, где в качестве аргументов $m$ штук нулей.
Отделим 1-ю вершину и все ее листья. Число в 1-й вершине пусть будет $s\leq n$, число вариантов выбора чисел в листьях-это число размещений $s-1$ элементов по $k_1$, то есть $A^{k_1}_{s-1}=\dfrac{(s-1)!}{(s-k_1-1)!}$. Тут удобнее ввести $k=s-k_1-1$. Тогда число размещений в остальной гусенице будет просто $AB_k(k_2,...k_m)$. Получаем

$$AB_n(k_1,...,k_m)=\sum_{k=1}^{n-k_1-1}\dfrac{(k+k_1)!}{k!}\cdot AB_k(k_2,...k_m)$$

-свели к меньшим n и на единицу меньшем числе аргументов ("длине гусеницы").Меня совершенно не смущает, что , например, значение $k=1$ почти никогда не возможно, просто слагаемое для этого $k$ будет равно нулю, как и многие первые. Когда останется гусеница единичной длины,число размещений в ней

$$AB_n(k_m)=\sum_{k=1}^{n-k_m-1}\dfrac{(k+k_m)!}{k!}=k_m!C^{k_m+1}_n$$

Таким образом, при фиксированной последовательности количеств листьев $k_1,...,k_m$ строка значений для нижнего звена гусеницы вычисляется, и последовательно вычисляются строки значений для все более дополненной гусеницы.
Для простой цепи эта рекуррентная формула эквивалентна $C^m_n=\sum_{k=1}^{n-1}C^{m-1}_k$, верная из комбинаторных соображений, и нам так же не мешают нижние индексы, меньшие верхних, соответствующие слагаемые просто равны 0

[Mihaylo]

Обновил картинку-пример для лучшего понимания:


-- 14.07.2015, 06:38 --

iancaple в сообщении #1036754 писал(а):

Число в 1-й вершине пусть будет $s\leq n$

Погодите. Числа в вершинах никак не влияют на количество размещений (перестановок). Алгоритм сортировки, который я исследую, может сортировать числа, вектора, матрицы или еще какие-нибудь объекты. Числа я приводил только для наглядного примера.
Здесь важны дуги между вершинами. Дуга показывает, что исследуемый алгоритм сортировки сравнил два объекта и установил между ними отношение. При этом нас не интересует, что за объекты были сравнены.

-- 14.07.2015, 07:02 --

iancaple писал(а):

для простой цепи $AB_n(0,0...0)=C^m_n=\dfrac{n!}{m!(n-m)!}$, где в качестве аргументов $m$ штук нулей.

Хотелось бы здесь заметить, что формула для подсчета перестановок простой цепи похожа на формулу для сочетаний. Дело в том, что мы осуществляем перестановки цепи длины $m$ по $n$, а известная формула дает сочетания из $n$ по $m$, то есть наоборот. Есть ли в этом совпадении какой-то математический смысл?

Еще раз оговорюсь: я вроде как сообразил, все-таки видимо искомой величиной является не количество размещений $AB$, а количество перестановок $PB$. Количество таких перестановок равно произведению количества перестановок гусеницы по $m+\sum\limits_{}^{}k_i$ и количества перестановок пустых клеток между элементами гусеницы. В силу независимости множеств и комбинаторного правила умножения.

$PB(n,m,k_1,...,k_i) = PB(m+\sum\limits_{}^{}k_i,m,k_1,...,k_i) \cdot P_0$

Для начала сообразить бы как рассчитать $P_0$ - количество перестановок пустых клеток вокруг элементов гусеницы... Вокруг элементов гусеницы имеется $(m+\sum\limits_{}^{}k_i+1)$ ячеек.

[Mihaylo]

Mihaylo писал(а):

Для начала сообразить бы как рассчитать $P_0$ - количество перестановок пустых клеток вокруг элементов гусеницы... Вокруг элементов гусеницы имеется $(m+\sum\limits_{}^{}k_i+1)$ ячеек.

Сообразил. Значит искомое число $P_0$ - это число сочетаний с повторениями. Формула для расчета сочетаний пустых клеток:

$P_0 = \frac{n!}{(m+\sum\limits_{}^{}k_i)!\cdot(n-m-\sum\limits_{}^{}k_i)!}$


Искомое значение:

$PB(n,m,k_1,...,k_i) = PC(m,k_1,...,k_i) \cdot \frac{n!}{(m+\sum\limits_{}^{}k_i)!\cdot(n-m-\sum\limits_{}^{}k_i)!}$

В итоге задача сводится к поиску перестановок чисел гусеницы с ограничением $PC(m,k_1,...,k_i)$.

Немного упрощается пример перестановки (при перестановке не должно быть пустых клеток):


При рассмотрении частного случая - простая цепь, $k_i = 0$ для всех $i$ - получается, что
$PC(m,0,...,0)=1$, что вполне естественно и интуитивно понятно.

Итак, требуется найти число перестановок гусеницы $PC(m,k_1,...,k_i)$ в общем случае.

[iancaple]

Mihaylo в сообщении #1037622 писал(а):

Итак, требуется найти число перестановок гусеницы $PC(m,k_1,...,k_i)$ в общем случае.

Ну это уже в школе на уроках дают, и получают решение. Вы уже достаточно потрудились, и не понимаете сложных текстов, поэтому просто приведу его.
Как и раньше, $n=\sum_{i=1}^m(k_i+1)$
В цитируемом опечатка, надо найти $PC(m,k_1,...,k_m)$
По правилу умножения числа вариантов

$$PC(m,k_1,...,k_m)=A^{k_1}_{n-1}\cdot A^{k_2}_{n-k_1-2}\cdot ...A^{k_m}{k_{m-1}+k_m+1}\cdot k_m! =$$ $$=\dfrac{(n-1)!}{(k_2+...+k_m+m-1)(k_2+...+k_m+m-2)...(k_{m-1}+k_m+2)(k_m+1)}$$

И все.
Что изменилось по сравнению с моим предыдущим решением: там я считал, что пустые клетки означают элементы, еще не затронутые алгоритмом сортировки, но также подлежащие сортировке, и значит, различимые. А "пустые"-фигурой речи. Разница в сомножителе, факториале числа пустых. Значит, сумма свернулась, не только для простой цепи. Можно проверить, подставляя разные исходные значения.
Два разных решения вдвое ценнее, чем одно, вот другое.
Вероятность, что число в верхней клетке ствола больше всех, $\dfrac 1n$
Вероятность, что число в следующей клетке ствола больше всех, кто ниже и правее, $\dfrac {1}{n-k_1-1}$
...
Вероятность, что нижнее число ствола больше своих листьев, $\dfrac{1}{k_m+1}$
Перемножим эти вероятности между собой и на $n!$, получим ту же формулу.

[Mihaylo]

Пытаюсь разобраться. Правильно ли обобщил формулы?

$$PC(m,k_1,...,k_m)=\prod\limits_{i=1}^{m} A^{k_i}_{n-\sum\limits_{j=1}^{i-1}(k_j+1)}+k_m+1\cdot k_m! =$$

$$=\dfrac{(n-1)!}{\prod\limits_{i=1}^{m}(\sum\limits_{j=i}^{m} k_j+m-i)}$$

Первая часть формулы: с независимыми размещениями вроде как понятно, в концовке формулы не ясно, кажется сбой при вводе формулы... Где в формуле отражается количество размещений чисел, лежащих в стволе? Единственный вариант размещения только у первого числа, у последующих чисел в стволе размещений возможно больше единицы.

[iancaple]

Да, сбой

iancaple в сообщении #1037632 писал(а):

$$PC(m,k_1,...,k_m)=A^{k_1}_{n-1}\cdot A^{k_2}_{n-k_1-2}\cdot ...A^{k_m}_{k_{m-1}+k_m+1}\cdot k_m! =$$ $$=\dfrac{(n-1)!}{\prod_{i=2}^m(\sum_{j=i}^mk_j+m-i+1)}=\dfrac{n!}{\prod_{i=1}^m(\sum_{j=i}^mk_j+m-i+1)}$$

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

[Mihaylo]

Спасибо, буду проверять на правильность.

iancaple писал(а):

Про числа в стволе: когда все числа выше выбраны, очередное число в стволе определяется однозначно, как наибольшее из невыбранных.

Ага, сейчас сообразил. Значит в более общем случае (когда граф ограничения произволен) нужно обходить граф сверху вниз, размещая в первую очередь несвободный ствол, затем свободные листочки. Как же быть с раздвоением дерева на несколько веток?

[iancaple]

Mihaylo в сообщении #1037966 писал(а):

Как же быть с раздвоением дерева на несколько веток?

Так же. Не могу выбрать обозначения, они зависят от того, что дальше делать с задачей. Ну пусть так. Для каждой вершины $x$ обозначим $|T_x|$ число вершин в поддереве с корнем $x$, включая саму $x$, для листа $|T_x|=1$, для корня исходного дерева $|T_0|=n$. Перестановка "правильная в $x$", если число в $x$ больше, чем в его потомках.Событие "правильность в целом" является произведением событий "правильность в $x$", а они все независимы. (Для дерева с корнем любые 2 поддерева либо независимы, либо одно содержит другое.) Аналогично 2-му способу получаем число "правильных" перестановок

$$\dfrac{n!}{\prod_x|T_x|}$$

[Mihaylo]

Замечательная получается формула! Я начал верить в то, что можно получить красивый результат исследования.

Испытываю проблему с оценкой независимости множеств и определением применимости правила умножения. Незнаком с вероятностным методом. Но ничего, может со временем дойдет.

Будет ли простая формула для "сросшегося" дерева - это когда оно "разветвляется" и ниже снова "срастается"?