Код Лемера

В математике и, в частности, в комбинаторике, код Лемера - это особый способ кодирования каждой возможной перестановки последовательности из n чисел. Это пример схемы перестановок нумерации и пример таблицы инверсии.

Код Лемера назван со ссылкой на Деррик Генри Лемер, но код известен как минимум с 1888 года.

• 1 Код
• 2 Кодирование и декодирование
• 3 Приложения к комбинаторике и вероятностям
  • 3.1 Независимость относительных рангов
  • 3.2 Количество минимумов и максимумов справа налево
  • 3.3 Задача секретаря
• 4 Подобные концепции
• 5 Ссылки
• 6 Библиография

Код Лемера использует тот факт, что существует

$n!\; =\; n\; \times \; (n\; -\; 1)\; \times \; \cdots \; \times \; 2\; \times \; 1\; \{\backslash \; displaystyle\; n!\; =\; n\; \backslash \; times\; (n-1)\; \backslash \; times\; \backslash \; cdots\; \backslash \; times\; 2\; \backslash \; times\; 1\}$

перестановок последовательности из n чисел. Если перестановка σ задана последовательностью (σ 1,…, σ n) ее изображений 1,…, n, то она кодируется последовательностью из n чисел, но не все такие последовательности допустимы, так как каждое число должно использоваться только один раз. В отличие от рассматриваемых здесь кодировок выбирают первое число из набора из n значений, следующее число из фиксированного набора из n - 1 значений и т. Д., Уменьшая количество возможностей до последнего числа, для которого используется только одно фиксированное значение. разрешается; каждая последовательность чисел, выбранных из этих наборов, кодирует одну перестановку. Хотя можно определить несколько кодировок , код Лемера имеет несколько дополнительных полезных свойств; это последовательность

другими словами, термин L (σ) i подсчитывает количество членов в (σ 1,…, σ n) справа от σ i, которые меньше его, число от 0 до n - i, с учетом n + 1 - i различных значений.

Пара индексов (i, j) с i < j and σi>σjназывается инверсией σ, а L (σ) i подсчитывает количество инверсий (i, j) с фиксированным i и изменяющимся j. Отсюда следует, что L (σ) 1 + L (σ) 2 +… + L (σ) n - общее количество инверсий σ, которое также количество смежных транспозиций, которые необходимы для преобразования перестановки в тождественную перестановку. Другие свойства кода Лемера включают то, что лексикографический порядок кодировок двух перестановок такой же, как и у их последовательностей (σ 1,…, σ n), что любое значение 0 в коде представляет минимум справа налево в перестановке (т. е. σ i меньше любого σ j справа от него), и значение n - i в позиции i аналогично обозначает максимум справа налево, и что код Лемера σ совпадает с представлением факториальной системы счисления его позиции в списке перестановок n в лексикографическом порядок (нумерация позиций начиная с 0).

Варианты этого кодирования могут быть получены путем подсчета инверсий (i, j) для фиксированного j, а не для фиксированного i, путем подсчета инверсий с фиксированным меньшим значением σ j вместо меньшего индекса i, или подсчетом не инверсий, а не инверсий; хотя это не приводит к принципиально другому типу кодирования, некоторые свойства кодирования соответственно изменятся. В частности, подсчет инверсий с фиксированным меньшим значением σ j дает таблицу инверсии σ, которая, как можно видеть, является кодом Лемера обратной перестановки.

Обычный способ доказать, что есть n! различные перестановки n объектов - это наблюдать, что первый объект может быть выбран n разными способами, следующий объект n - 1 разными способами (потому что выбор того же числа, что и первый, запрещен), следующий n - 2 разными способами (потому что теперь есть 2 запрещенных значения) и так далее. Переводя эту свободу выбора на каждом шаге в число, можно получить алгоритм кодирования, который находит код Лемера данной перестановки. Необязательно предполагать, что объекты переставляются как числа, но требуется полное упорядочение набора объектов. Поскольку номера кода должны начинаться с 0, соответствующий номер для кодирования каждого объекта σ i - это количество объектов, которые были доступны в этой точке (поэтому они не встречаются перед позицией i), но которые меньше фактически выбранного объекта σ i. (Такие объекты неизбежно должны появиться в некоторой позиции j>i, и (i, j) будет инверсией, которая показывает, что это число действительно L (σ) i.)

Это число для кодирования каждого объекта можно найти путем прямого подсчета несколькими способами (прямым подсчетом инверсий или корректировкой общего числа объектов, меньших заданного, то есть его порядкового номера, начиная с 0 в наборе, теми, которые недоступен на своем месте). Другой метод, который существует на месте, но не очень эффективен, - это начать с перестановки {0, 1,… n - 1}, полученной путем представления каждого объекта его упомянутым порядковым номером, а затем для каждой записи x в В порядке слева направо исправьте элементы справа, вычтя 1 из всех записей (все еще) больше x (чтобы отразить тот факт, что объект, соответствующий x, больше не доступен). Конкретно, код Лемера для перестановки букв B, F, A, G, D, E, C, упорядоченных в алфавитном порядке, сначала дал бы список порядковых номеров 1,5,0,6,3,4,2, который является последовательно преобразованные

$1\; 5\; 0\; 6\; 3\; 4\; 2\; 1\; 4\; 0\; 5\; 2\; 3\; 1\; 1\; 4\; 0\; 4\; 2\; 3\; 1\; 1\; 4\; 0\; 3\; 1\; 2\; 0\; 1\; 4\; 0\; 3\; 1\; 2\; 0\; 1\; 4\; 0\; 3\; 1\; 1\; 0\; 1\; 4\; 0\; 3\; 1\; 1\; 0\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{matrix\}\; \backslash \; mathbf\; \{1\}\; 5\; 0\; 6\; 3\; 4\; 2\; \backslash \backslash \; 1\; \backslash \; mathbf\; \{4\}\; 0\; 5\; 2\; 3\; 1\; \backslash \backslash \; 1\; 4\; \backslash \; mathbf\; \{0\}\; 4\; 2\; 3\; 1\; \backslash \backslash \; 1\; 4\; 0\; \backslash \; mathbf\; \{3\}\; mathbf\; \{1\}\; 2\; 0\; \backslash \backslash \; 1\; 4\; 0\; 3\; 1\; \backslash \; mathbf\; \{1\}\; 0\; \backslash \backslash \; 1\; 4\; 0\; 3\; 1\; 1\; \backslash \; mathbf\; \{0\}\; \backslash \backslash \backslash \; end\; \{matrix\}\}\}$

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

Для декодирования кода Лемера в перестановку данного набора последняя процедура может быть обратной: для каждой записи x, в порядке справа налево, исправить элементы справа, добавив 1 ко всем этим (в настоящее время) больше или равно x; наконец, интерпретировать полученную перестановку {0, 1,… n - 1} как порядковые номера (что составляет добавление 1 к каждой записи, если ищется перестановка {1, 2,… n}). В качестве альтернативы записи кода Лемера могут обрабатываться слева направо и интерпретироваться как число, определяющее следующий выбор элемента, как указано выше; это требует ведения списка доступных элементов, из которого удаляется каждый выбранный элемент. В примере это будет означать выбор элемента 1 из {A, B, C, D, E, F, G} (который является B), затем элемента 4 из {A, C, D, E, F, G} (который является F), затем элемент 0 из {A, C, D, E, G} (дающий A) и так далее, восстанавливая последовательность B, F, A, G, D, E, C.

Независимость относительных рангов

Код Лемера определяет биекцию от симметричной группы Snк декартову произведению $[n]\; \times \; [n\; -\; 1]\; \times \; \cdots \; \times \; [2]\; \times \; [1]\; \{\backslash \; displaystyle\; [n]\; \backslash \; times\; [n-1]\; \backslash \; times\; \backslash \; cdots\; \backslash \; times\; [2]\; \backslash \; times\; [1]\}$, где [k] обозначает набор k-элементов $\{0,\; 1,\dots ,\; k\; -\; 1\}\; \{\backslash \; displaystyle\; \backslash \; \{0,1,\; \backslash \; ldots,\; k-1\; \backslash \}\}$. Как следствие, при равномерном распределении на S n компонент L (σ) i определяет равномерно распределенную случайную величину на [n - i], и эти случайные величины являются взаимно независимыми, потому что они являются проекциями на различные факторы декартова произведения.

Количество минимумов и максимумов справа налево

Определение: В последовательности u = (u k)1≤k≤n существует минимум справа налево (соответственно максимум ) в ранг k, если u k строго меньше (соответственно, строго больше), чем каждый элемент u i с i>k, то есть справа от него.

Пусть B (k) (соотв. H (k)) - событие «существует минимум справа налево (соотв. максимум) в ранге k», т.е. B (k) - это множество перестановок $S\; n\; \{\; \backslash \; displaystyle\; \backslash \; scriptstyle\; \backslash \; \{\backslash \; mathfrak\; \{S\}\}\; \_\; \{n\}\}$которые демонстрируют минимум справа налево (соответственно максимум) на ранге k. Очевидно, что

$\{\omega \; \in \; В\; (к)\}\; \iff \; \{L\; (k,\; \omega )\; =\; 0\}\; и\; \{\omega \; \in \; H\; (k)\}\; \iff \; \{L\; (k,\; \omega )\; =\; k\; -\; 1\}.\; \{\backslash \; Displaystyle\; \backslash \; \{\backslash \; ome\; ga\; \backslash \; in\; B\; (k)\; \backslash \}\; \backslash \; Leftrightarrow\; \backslash \; \{L\; (k,\; \backslash \; omega)\; =\; 0\; \backslash \}\; \backslash \; quad\; \{\backslash \; text\; \{and\}\}\; \backslash \; quad\; \backslash \; \{\backslash \; omega\; \backslash \; in\; H\; (k)\; \backslash \}\; \backslash \; Leftrightarrow\; \backslash \; \{L\; (k,\; \backslash \; omega)\; =\; k-1\; \backslash \}.\}$

Таким образом, число N b (ω) (соответственно. N h (ω)) минимума справа налево (соответственно максимума) для перестановки ω можно записать как сумму независимых случайных величин Бернулли, каждая с соответствующим параметром из 1 / k:

$N\; b\; (\omega )\; =\; \sum \; 1\; \le \; k\; \le \; n\; 1\; 1\; B\; (k)\; и\; N\; b\; (\omega )\; =\; \sum \; 1\; \le \; k\; \le \; n\; 1\; 1\; H\; (k).\; \{\backslash \; displaystyle\; N\_\; \{b\}\; (\backslash \; omega)\; =\; \backslash \; sum\; \_\; \{1\; \backslash \; leq\; k\; \backslash \; leq\; n\}\; \backslash \; 1\; \backslash !\; \backslash !\; 1\_\; \{B\; (k)\}\; \backslash \; quad\; \{\backslash \; text\; \{и\}\}\; \backslash \; quad\; N\_\; \{\; b\}\; (\backslash \; omega)\; =\; \backslash \; sum\; \_\; \{1\; \backslash \; leq\; k\; \backslash \; leq\; n\}\; \backslash \; 1\; \backslash !\; \backslash !\; 1\_\; \{H\; (k)\}.\}$

Действительно, поскольку L (k) подчиняется равномерному закону на $[[1,\; k]],\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; \backslash \; [\backslash !\; [1,\; k]\; \backslash !],\}$

$P\; (B\; (k))\; =\; P\; (L\; (k)\; =\; 0)\; =\; P\; (H\; (k))\; =\; P\; (L\; (k)\; =\; k\; -\; 1)\; =\; 1\; k.\; \{\backslash \; Displaystyle\; \backslash \; mathbb\; \{P\}\; (B\; (k))\; =\; \backslash \; mathbb\; \{P\}\; (L\; (k)\; =\; 0)\; =\; \backslash \; mathbb\; \{P\}\; (H\; (k))\; =\; \backslash \; mathbb\; \{P\}\; (L\; (k)\; =\; k-1)\; =\; \{\backslash \; tfrac\; \{1\}\; \{k\}\}.\}$

производящая функция для случайной величины Бернулли $1\; 1\; B\; (k)\; \{\backslash \; displaystyle\; 1\; \backslash \; !\; \backslash !\; 1\_\; \{B\; (k)\}\}$равно

$G\; k\; (s)\; =\; k\; -\; 1\; +\; sk,\; \{\backslash \; displaystyle\; G\_\; \{k\}\; (s)\; =\; \{\backslash \; frac\; \{k-\; 1\; +\; s\}\; \{k\}\},\}$

, следовательно, производящая функция N b равна

$G\; (s)\; =\; \prod \; k\; =\; 1\; n\; G\; k\; (s)\; =\; sn\; ¯\; n!\; \{\backslash \; Displaystyle\; G\; (s)\; =\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; G\_\; \{k\}\; (s)\; \backslash \; =\; \backslash \; \{\backslash \; frac\; \{s\; ^\; \{\backslash \; overline\; \{n\}\}\}\; \{n!\}\}\}$

(с использованием нотации возрастающего факториала ), что позволяет нам восстановить формулу произведения для производящей функции чисел Стирлинга первого вида (без знака).

Задача секретаря

Это задача оптимального останова, классическая в теории принятия решений, статистике и прикладных вероятностях, где случайная перестановка постепенно выявляется через первые элементы кода Лемера, и где цель состоит в том, чтобы остановиться точно на элементе k, таком как σ (k) = n, тогда как единственной доступной информации (k первых значений кода Лемера) недостаточно для вычисления σ (k).

Говоря менее математическими словами: ряд n кандидатов проходят собеседование один за другим. Интервьюер должен нанять лучшего соискателя, но должен принять решение («нанять» или «не нанимать») на месте, не проводя собеседования со следующим соискателем (и тем более без собеседования со всеми соискателями).

Таким образом, интервьюер знает ранг k соискателя, поэтому в момент принятия своего решения k интервьюер знает только первые k элементов кода Лемера, тогда как ему необходимо знать их все, чтобы принять обоснованное решение. Для определения оптимальных стратегий (то есть стратегии, максимизирующей вероятность выигрыша) решающее значение имеют статистические свойства кода Лемера.

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

Два похожих вектора находятся в использовать. Один из них часто называют вектором инверсии, например Автор Вольфрам Альфа. См. Также Инверсия (дискретная математика) § Инверсия связанных векторов.

• Математический портал

• Mantaci, Roberto; Rakotondrajao, Fanja (2001), «Перестановочное представление, которое знает, что означает« эйлерово »», Discrete Mathematics and Theoretical Computer Science (4): 101–108, заархивировано из оригинала на 2004-11-16
• Кнут, Дон (1981), Искусство компьютерного программирования, 3, Чтение: Аддисон-Уэсли, стр. 12–13