Функция парковки ⇐ Васина Википедия

[wiki_en]

'''Функции парковки''' являются обобщением перестановок, изучаемых в комбинаторике, разделе математики.

==Определение и применение==
Функция парковки длиной n представляет собой последовательность n положительных целых чисел, каждое из которых находится в диапазоне от 1 до n, со свойством, которое для каждый i до длины последовательности, последовательность содержит как минимум значения i, которые не превышают i. То есть она должна содержать хотя бы одну 1, как минимум два значения 1 или 2, как минимум три значения 1, 2 или 3 и т. д. Эквивалентно, если последовательность является алгоритмом сортировки | отсортирована, то для каждого i в том же диапазоне, i-е значение отсортированной последовательности не превышает i.
Например, существует 16 функций парковки длиной три:
:(1,2,3), (2,3,1), (3,1,2),
:(3,2,1), (2,1,3), (1,3,1),
:(1,1,2), (1,2,1), (2,1,1),
:(1,1,3), (1,3,1), (3,1,1),
:(1,2,2), (2,1,2), (2,2,1),
:(1,1,1).

Название объясняется следующим мысленным экспериментом. Последовательность из n водителей на автомобилях едет по улице с односторонним движением, имеющей n парковочных мест, причем каждый водитель имеет предпочтительное парковочное место. Каждый водитель едет до тех пор, пока не достигнет предпочитаемого места, а затем паркуется на первом доступном месте. Функция парковки описывает предпочтения, при которых все автомобили могут парковаться.
Функции парковки также имеют более серьезное применение при исследовании хеш-таблиц на основе линейного зондирования — стратегии размещения ключей в хеш-таблице, которая очень напоминает стратегию односторонней парковки автомобилей.
==Комбинаторное перечисление==
Количество функций парковки длиной n равно (n+1)^{n-1}. Например, для n=3 это число 4^2=16.
Джон Риордан (математик) | Джон Риордан приписывает Генри О. Поллаку следующий аргумент в пользу этой формулы. На круговой дороге с односторонним движением с n+1 местами каждый из n автомобилей всегда сможет припарковаться, независимо от того, какие предпочтения каждый водитель имеет в отношении своего стартового места. Существует (n+1)^n вариантов предпочтений, каждый из которых оставляет одно свободное место. Все пространства симметричны друг другу, поэтому в силу симметрии существует (n+1)^{n-1} вариант предпочтений, при котором пространство n+1 остается свободное место. Эти варианты выбора являются именно функциями парковки. Функции парковки также можно поместить в биекцию с остовными деревьями на полном графе с n+1 вершинами, одна из которых обозначена как корень. Эта биекция вместе с формулой Кэли для числа остовных деревьев снова показывает, что существуют (n+1)^{n-1} функции парковки.
Множество исследований изучало ряд парковочных функций специальной формы. В очень простом частном случае функции парковки, позволяющие каждому автомобилю парковаться в предпочитаемом им месте, представляют собой именно перестановки, подсчитанные с помощью факториалов. Функции парковки, которые позволяют каждому автомобилю парковаться либо в предпочитаемом им месте, либо в следующем месте, подсчитываются по упорядоченным номерам Bell.






Факториальные и биномиальные темы