Числа Эйлера на множествах перестановок и аналоги теоремы Вильсона | ПДМ. Приложение. 2014. № 7.

Числа Эйлера на множествах перестановок и аналоги теоремы Вильсона

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

Euler's numbers on sets of permutations and analogues of wilson's theorem.pdf На симметрической группе Sn-1 статистика des(a) = \{iE[n-1] : ai>ai+i, an=0}\ при фиксированном n ^ 2 описывает число спусков перестановки а=а1... an-1 ESn-1 над алфавитом [n-1]={1,... , n-1}. На множестве перестановок U С Sn-1 определим производящий многочлен Эйлера Е tdes(a), а его коэффициенты назовём числами Эйлера на U .В частности, этот многочлен на Sn-1 совпадает с многочленом Эйлера n- 1 An-1(t)= J2 An-1,k tk степени n-1, а An-1,k = \{aESn-1: des(a) = k}\ [1]. k= 1 Для простого числа p имеем Ap-1 (1) = \Sp-1\ = (p- 1)! = - 1 (mod p), что отвечает теореме Вильсона [2], а её усилением служит следующее утверждение. Теорема 1. Ap-1,k = 1 (mod p), k = 1,... ,p-1. Теорему 1 можно доказать с помощью формул для чисел Эйлера Ap-1,k, но интереснее получить её прямое доказательство на основе свойств перестановок aESn-1, что позволяет также найти аналоги теоремы Вильсона для чисел, связанных с трудными перечислительными проблемами полных отображений. Определим биекцию c : Sn-1 ^ Sn-1 с помощью равенств cai=n - ai, iE[n- 1], для символов aESn-1, а дополнение к а обозначим a=ca. В криптографии сложение перестановок aESn-1 часто выполняется посимвольно по mod n, т. е. на аддитивной группе Zn, отождествляемой с {0,1,... , n - 1}, причём это переносится и на умножение aESn-1 на целое число. Будем также использовать n- 1 формулу des(a)=n-1 ^ (ai+1-ai), в которой разности берутся по mod n, а a0=an=0. i=0 Непосредственно из определений следует, что c есть инволюция, а а + а = 0, причём элементарное равенство des(a) + des(a) = n влечёт соотношение tnAn-1(t-1) = An-1(t). Определение 1. Перестановки a, a E Sn-1 назовём сопряжёнными относительно £ E Sn-1, если a + 4 = £, а £ E Sn-1 -единичная перестановка (сопряжённость можно рассматривать относительно любой перестановки т E Sn-1). Все a E Sn-1, сопряжённые относительно £ E Sn-1, задают множество CM(Zn) всех стандартных полных отображений [3], а \CM(Zn)\ = \CM(Zn)\, CM(Zn) -множество всех a E Sn-1 из определения 1. Множество всех стандартных сильных полных отображений SCM-(Zn) = CM(Zn) n CM(Zn), \CM(Zn)\ = 0 при чётном n и \SCM(Zn)\ = 0 также и при n, кратном трём, а задачи вычисления чисел \CM(Zn)\ и \SCM(Zn)\ являются #Р-полными [3] (\CM(Zn)\ при нечётном n = 1, 3,... , 25 приведены в [4]). Свойства чисел Эйлера из теоремы 1 наследуются числами Эйлера An-1,k на CM(Zn), An-1,k на SCM(Zn) и приводят к аналогам теоремы Вильсона. Теорема 2. Ap-1,k = 1 (mod p), k = 1,...,p - 2; a4p-1,p-1 = 0, что влечёт \CM(Zp)\ = - 2 (mod p). Теорема 3. a4p-1,1 = 0; Ap-1,k = 1 (mod p), k = 2,...,p - 2; Ap-1,p-1 = 0, что влечёт \SCM(Zp)\ = -3 (mod p). ' Доказательство теорем базируется на следующих вспомогательных утверждениях. Лемма 1. Пусть Rn = {r£ : r E [n-1], (r,n) = 1,£ E Sn-1} отвечает приведённой системе вычетов по modn. Тогда des(r£) = r, а \Rn\ = ^(n), где при n = Пpordp(n), p|n n > 1, функция Эйлера 1 с определением 1 даёт |(Rn П CM(Zn))| = n П(1 - 2p-1) и |(Rn П SCM(Zn))| = n П(1 - 3p-1). p| n p| n Лемма 2. Если a G CM(Zn), то des(a) + des(a) = n - 1. Применение формулы вычисления статистики des к перестановкам из определения 1 даёт требуемое. Так как deg An-1(t) = n - 2, то по лемме 2 имеем tn-1 An-1(t-1) = = An-1(t), а также deg An-1(t) = n - 2, Ап-1д = 0 и tnAn-1(t-1) = An-1(t). Определение 2. т = т1... тп-1 G Sn-1, т = da назовём смещением a G Sn-1, если биекция d : Sn-1 ^ Sn-1 задана выражениями т = ai+1 - a^ (mod n), i = 1,... , n - 2, и Tn-1 = n - a1, а порядком d = d(a) назовём наименьшее k G Z+, для которого dka = a. Лемма 3. Если a G Sn-1, то des(da) = des(a) и d|n. Равенство des(da) = des(a) получается из свойств des, а делимость d|n следует из определения 2, так как повторное применение d разбивает Sn-1 на классы эквивалентности (так, dre = re, re G Rn, т.е. d = 1). При n > 4 в словах dka G Sn-1, k = 0,... , d - 1, имеется n/d - 1 неподвижных символов a^, кратных d, с индексом i, кратным d. Теоремы 1-3 доказываются с помощью лемм 1, 2 и леммы 3, справедливой также на CM(Zn) и SCM(Zn), причём применяемый метод дополнительно даёт следующие сравнения: |CM(Zn)| = 1 (mod 2) при нечётном n и |SCM(Zn)| = 0 (mod 2) при n > 1.

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

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

Авторы

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

Ссылки

Стенли Р. Перечислительная комбинаторика. Т. 1. М.: Мир, 1990.
Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987.
Hsiang J., Hsu D. F., and Shieh Y. P. On the hardness of counting problems of complete mappings // Discr. Math. 2004. V. 277. P. 87-100.
http://oeis.org/A003111 - Sloane N.J. A. The on-line encyclopedia of integer sequences.
 Числа Эйлера на множествах перестановок и аналоги теоремы Вильсона | ПДМ. Приложение. 2014. № 7.

Числа Эйлера на множествах перестановок и аналоги теоремы Вильсона | ПДМ. Приложение. 2014. № 7.