Перестановка Стирлинга - Stirling permutation

В комбинаторная математика, а Перестановка Стирлинга порядка k это перестановка из мультимножество 1, 1, 2, 2, ..., k, k (с двумя копиями каждого значения от 1 до k) с дополнительным свойством, что для каждого значения я появляющиеся в перестановке, значения между двумя копиями я больше чем я. Например, 15 перестановок Стирлинга третьего порядка таковы:

1,1,2,2,3,3;   1,2,2,1,3,3;   2,2,1,1,3,3;
1,1,2,3,3,2;   1,2,2,3,3,1;   2,2,1,3,3,1;
1,1,3,3,2,2;   1,2,3,3,2,1;   2,2,3,3,1,1;
1,3,3,1,2,2;   1,3,3,2,2,1;   2,3,3,2,1,1;
3,3,1,1,2,2;   3,3,1,2,2,1;   3,3,2,2,1,1.

Число перестановок Стирлинга порядка k дается двойной факториал (2k - 1) !!. Перестановки Стирлинга были введены Гессель и Стэнли (1978) чтобы показать, что некоторые числа (числа перестановок Стирлинга с фиксированным числом спусков) неотрицательны. Они выбрали название из-за связи с определенными многочлены определяется из Числа Стирлинга, которые, в свою очередь, названы в честь шотландского математика XVIII века Джеймс Стирлинг.[1]

Построение перестановки Стирлинга из Эйлер тур из посадить дерево с его краями, помеченными в порядке построения

Перестановки Стирлинга можно использовать для описания последовательностей, с помощью которых можно построить корневую посадить дерево с k края, добавляя листья один за другим к дереву. Ибо, если края пронумерованы в порядке их вставки, то последовательность чисел в Эйлер тур дерева (образованного путем удвоения ребер дерева и обхода дочерних узлов каждого узла в порядке слева направо) является перестановкой Стирлинга. И наоборот, каждая перестановка Стирлинга описывает последовательность построения дерева, в которой следующее ребро ближе к корню от ребра, помеченного я тот, чья пара значений наиболее близко окружает пару я значения в перестановке.[2]

Перестановки Стирлинга были обобщены для перестановок мультимножества с более чем двумя копиями каждого значения.[3] Исследователи также изучили количество перестановок Стирлинга, которые избегают определенных закономерностей.[4]

Смотрите также

Рекомендации

  1. ^ Гессель Ира; Стэнли, Ричард П. (1978), «Многочлены Стирлинга», Журнал комбинаторной теории, Серия А, 24 (1): 24–33, Дои:10.1016/0097-3165(78)90042-0, МИСТЕР  0462961.
  2. ^ Янсон, Сванте (2008), «Плоские рекурсивные деревья, перестановки Стирлинга и модель урны», Пятый коллоквиум по математике и информатике, Дискретная математика. Теор. Comput. Sci. Proc., AI, доц. Дискретная математика. Теор. Comput. Sci., Нэнси, стр. 541–547, arXiv:0803.1129, Bibcode:2008arXiv0803.1129J, МИСТЕР  2508813.
  3. ^ Клингсберг, Пол; Шмальцрид, Синтия (1990), "Семейство конструктивных биекций, включающих перестановки Стирлинга", Материалы двадцать первой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1990), Congressus Numerantium, 78, стр. 11–15, МИСТЕР  1140465.
  4. ^ Куба, Маркус; Панхольцер, Алоис (2012), «Формула перечисления для перестановок Стирлинга с ограничением по шаблону», Дискретная математика, 312 (21): 3179–3194, Дои:10.1016 / j.disc.2012.07.011, МИСТЕР  2957938.