Сравнения для чисел полных отображений | ПДМ. 2014. № 4(26).

Сравнения для чисел полных отображений

Для чисел стандартных полных отображений и для чисел стандартных сильных полных отображений получены сравнения по модулю простого числа. Доказательства основаны на рассмотрении свойств некоторых статистик и чисел Эйлера на соответствующих множествах перестановок. Получены аналогичные результаты для этих множеств с учётом знака их элементов.

Comparisons for numbers of complete mappings.pdf Введение Все перестановки симметрической группы Sn-1 над алфавитом {1,... , n - 1}, вычитание из которых единичной перестановки s G Sn-1 приводит к перестановке из Sn-1, определяют множество CM(Zn) стандартных полных отображений. Если сложение £ G Sn-1 с перестановкой из CM(Zn) также приводит к перестановке из Sn-1, то все такие перестановки задают множество SCM(Zn) стандартных сильных полных отображений [1]. Рассматриваемое сложение (вычитание) перестановок выполняется посимвольно по modn, т.е. на аддитивной группе Zn, отождествляемой с множеством {0,1,... , n - 1}; такие операции с перестановками находят применение, в частности, в криптографии. В работе [1] показано, что задачи вычисления чисел #CM(Zn) и #SCM(Zn) не являются #Р-полными, но являются трудными вычислительными проблемами. В [2] доказан ряд утверждений о делимости перманента Pn = per(wfcm)n-7L=0, где ш = exp(2ni/n) - корень n-й степени из единицы, а (n х п)-матрица Шура (^^П-^о встречается в теории чисел, теории кодирования, комбинаторном анализе и т. п. В [3] вычисление чисел Pn сведено к нахождению мощности множества CM(Zn) с учётом знака его элементов. В настоящей работе получены некоторые сравнения для #CM(Zn) и #SCM(Zn), а также для мощностей множеств CM(Zn) и SCM(Zn) с учётом знака их элементов. Эти результаты связаны с нахождением сравнений по простым модулям для чисел Эйлера на соответствующих множествах перестановок. 1. Свойства некоторых статистик и отображений При делении с остатком мощности некоторого множества на заданное число можно разбить это множество на части, для которых этот вопрос решается проще, а затем использовать полученные результаты. Этот подход удобно применять для достаточно сложных по структуре множеств перестановок, определяя понятие статистики как неотрицательной целочисленной функции, заданной для каждой перестановки рассматриваемого множества. Например, статистика des(a) = #{i: 1 ^ i ^ n - 1, ai > ai+1, = 0} при фиксированном n ^ 2 описывает число спусков перестановки а = а1... ага-1 G Sn-1, т. е. спуск учитывается также на последнем символе перестановки, и индуцирует производящий многочлен Эйлера n- 1 An-1(t)= Е tdes(CT) = Е An-1,fc tfc, (1) fc=1 коэффициенты которого Ап-1,к = #{а : а G Sn-1, des(a) = k} называются числами Эйлера [4]. Так как #Sn-1 = An-1(1), остаток от деления #Sn-1 на n можно найти, используя остатки от деления чисел ап-1^ , k = 1,..., n - 1, на n. При исследовании делимости мощностей некоторых множеств перестановок полезно ввести некоторые отображения. Зададим биекцию c : Sn-1 ^ Sn-1, определяющую дополнение а = са к перестановке а = а1а2 ... an-1 G Sn-1, с помощью равенств сai = n - ai, 1 ^ i ^ n - 1. Непосредственно из этого определения следует, что отображение c есть инволюция, а а + а = 0, причём элементарное равенство des^) + des(O) = n влечёт соотношение tnAn-1(t-1) = An-1(t), т.е. An-1,fc = An-1,n-fc, k = 1,... ,n - 1. Статистика des^*) для расширения а* = а1. ..а^;! 0 G Sn перестановки а G Sn-1 обладает свойством des^*) = des(a) + 1, и справедливо простое равенство 1 n- 1 des^) = - Е (ai+l - а^, ао = аn = 0, (2) n i=0 где разности под знаком суммы вычисляются по модулю n. На симметрической группе Sn в [5] применяются биекции t : Sn ^ Sn и u : Sn ^ Sn, задаваемые для перестановки п = п1... nn G Sn над алфавитом {0,1,... n - 1} соотношениями t п=п2 ... nnn1 и u ni = ni + 1 mod n, 1 ^ i ^ n. Преобразования переноса t и единичного сдвига u позволяют ввести отношение эквивалентности на Sn: перестановки а, т G Sn называются эквивалентными, если найдутся такие целые числа k и m, что tfcита = т. Мощность фактор-множества по этому отношению эквивалентности вычисляется по формуле 1 -Е (n/d)(n/d)d d!, (3) n d|n где

Ключевые слова

полные отображения, перестановка, статистика, числа Эйлера, смещение перестановки, complete mappings, permutation, statistic, Euler's numbers, Wilson theorem, displacement of permutation

Авторы

ФИООрганизацияДополнительноE-mail
Бондаренко Леонид НиколаевичПензенский государственный университеткандидат технических наук, доцент, доцент кафедры дискретной математикиleobond5@mail.ru
Шарапова Марина ЛеонидовнаМосковский государственный университет им. М.В. Ломоносовастарший преподаватель кафедры математического анализа механико-математического факультетаmsharapova@list.ru
Всего: 2

Ссылки

Hsiang J., Hsu D. F., and Shieh Y. P. On the hardness of counting problems of complete mappings // Discrete Mathematics. 2004. V.277. P. 87-100.
Graham R. L.and Lehmer D. H. On the permanent of Schur's matrix //J. Australian Math. Soc. 1976. V. 21 (Series A). Part 4. P. 487-497.
Бондаренко Л. Н. Перманенты и «аддитивные» задачи перечисления перестановок // Материалы VII Междунар. семинара «Дискретная математика и ее приложения» (29января-2февраля 2001г.). Ч. III. М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2001. С. 335-338.
Стенли Р. Перечислительная комбинаторика. Т. 1. М.: Мир, 1990. 440 с.
Moser W. O. J. A (modest) generalization of theorems of Wilson and Fermat // Canadian Math. Bul. 1990. V. 33 (2). P. 253-256.
Мельников И. Г., Славутский И. Ш. О двух забытых доказательствах закона взаимности // Труды института истории естествознания и техники. Т. 28. История физико-математических наук. М., 1959. С. 201-218.
Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987. 416 с.
Бондаренко Л. Н., Шарапова М. Л. Применение обобщенной формулы Родрига в комбинаторном анализе // Изв. вузов. Поволжский регион. Физ.-мат. науки. 2011. №4(20). С. 44-58.
http://oeis.org/A003111 - Sloane N.J. A. The on-line encyclopedia of integer sequences.
http://oeis.org/A003112 - Sloane N.J. A. The on-line encyclopedia of integer sequences.
 Сравнения для чисел полных отображений | ПДМ. 2014. № 4(26).

Сравнения для чисел полных отображений | ПДМ. 2014. № 4(26).