Пейринг Лэнгфорда
В комбинаторной математике пара Лэнгфорда , также называемая последовательностью Лэнгфорда , представляет собой перестановку последовательности из 2 n чисел 1, 1, 2, 2, ..., n , n, в которой две единицы находятся на расстоянии одной единицы друг от друга. две двойки находятся на расстоянии двух единиц друг от друга, и, в более общем смысле, две копии каждого числа k находятся на расстоянии k единиц друг от друга. Пары Лэнгфорда названы в честь К. Дадли Лэнгфорда, поставившего задачу их построения в 1958 г.
Проблема Лэнгфорда — это задача поиска пар Лэнгфорда для заданного значения n . [1]
Тесно связанная концепция скулемской последовательности. [2] определяется таким же образом, но вместо этого переставляет последовательность 0, 0, 1, 1, ..., n - 1, n - 1.
Пример
[ редактировать ]Спаривание Лэнгфорда для n = 3 задается последовательностью 2, 3, 1, 2, 1, 3.
Характеристики
[ редактировать ]Спаривания Лэнгфорда существуют только тогда, когда 0 или n конгруэнтно 3 по модулю 4; например, не существует спаривания Лэнгфорда, когда n = 1, 2 или 5.
Числа различных пар Лэнгфорда для n = 1, 2, …, считая любую последовательность такой же, как и ее обратную, равны
- 0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, 0, 0, 39809640, 326721800, 0, 0, 256814891280, 2636337861200, 0, 0, … (последовательность A0 14552 в ОЭИС ).
Как описывает Кнут (2008) , проблема составления списка всех пар Лэнгфорда для данного n может быть решена как пример точной проблемы покрытия , но для больших n количество решений можно более эффективно вычислить алгебраическими методами.
Приложения
[ редактировать ]Скулем (1957) использовал последовательности Скулема для построения систем троек Штейнера .
В 1960-х годах Э. Дж. Грот использовал пары Лэнгфорда для построения схем целочисленного умножения . [3]
См. также
[ редактировать ]- Перестановка Стирлинга — другой тип перестановки одного и того же мультимножества.
Примечания
[ редактировать ]Ссылки
[ редактировать ]- Гарднер, Мартин (1978), «Проблема Лэнгфорда», Mathematical Magic Show , Vintage, стр. 70 .
- Кнут, Дональд Э. (2008), Искусство компьютерного программирования , Vol. IV, выпуск 0: Введение в комбинаторные алгоритмы и логические функции, Аддисон-Уэсли, ISBN 978-0-321-53496-5 .
- Лэнгфорд, К. Дадли (1958), «Проблема», Mathematical Gazette , 42 : 228 .
- Норд, Густав (2008), «Совершенные скулемские множества», Discrete Mathematics , 308 (9): 1653–1664, arXiv : math/0506155 , doi : 10.1016/j.disc.2006.12.003 , MR 2392605 .
- Сколем, Торальф (1957), «О некоторых распределениях целых чисел в парах с заданными разностями», Mathematica Scandinavica , 5 : 57–68, MR 0092797 .
Внешние ссылки
[ редактировать ]- Джон Э. Миллер, Проблема Лэнгфорда , 2006 г. (с обширной библиографией ).
- Вайсштейн, Эрик В. «Проблема Лэнгфорда» . Математический мир .