Том 7, серия 1, номер 2, 2000 г., Стр. 65-70
УДК 519.115.1
В. Ню, Д. Фон-Дер-Флаасс
Оценки длины универсальной последовательности для перестановок
Аннотация:
Получены оценки длины$L(n)$ минимальной универсальной последовательности для множества всех перестановок из$n$ символов. Показано, что
$$ n!+(n-1)!+\frac{n-1}{2n-3}(n-2)!+n-3\leqslant L(n)\leqslant n!+(n-1)!+\dots+1!. $$
Приведены две конструкции одной и той же универсальной последовательности длины$n!+(n-1)!+\dots+1!$ .
Библиогр. 3.
Ню В. 1
Фон-Дер-Флаасс Д. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 20 января 2000 г.
