АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 2001 г.

элемент, абеленизация которого есть ( т,п ) Буквенное выражение слова Wmjl определяется формулой ( V т+п xv x2)= П хА ), К-\ где гк вычисляются из равенств 1+ (К - 1^п = Хк(т + п)+гк ; К = 1 +n;Q<rK<т +п; и / Ы = 1, если 0 <гк <т или 2, если т<гк <т +п. Число вхождений х, в первые К букв слова Wmn равно Хк + 1. Имеется геометрическая характериза­ ция слова W . Рассмотрим отрезок (без крайних точек) прямой у - ” х от т точки 0(0;0) до точки А(т,п\ Этот отрезок пересекает сеть 0 прямых линий, параллельных координатным осям и проходящих через точки с целыми коор­ динатами. Если отрезок ОА не пересекает горизонтальной линии сети © между вертикальными линиями с х - координатами Хк и Хк„, то > (М ) - целая часть а , и, наоборот - из равенства целых _ и частей следует, что прямая у - х не пересекает между соответствующими т вертикальными линиями горизонтальной. Пересечение горизонтальной прямой соответствует неравенству Хк ” <(Х4.„) ” . Процесс пересечения отрезком ли- т т ний сети 0 определяет слово 1>Гии(х,,ас2) Когда этот отрезок пересекает верти­ кальную линию слева направо - записываем х,, а когда пересекает горизон­ тальную линию снизу вверх, записываем х 2 . Соответственно, х,~' и х21, если пересечение происходит в обратном направлении. Для точек О и А не за­ писывается ничего. В результате получаем слово К^л(х,,х2) Из него получаем слово Ит »(х,,х2)= х |х2 Кя„(х,хг) В [6] доказывается, что Ж„я(х|,х2)=Кяя(х|,х2) для взаимно простых т,п. Здесь же доказаны следую- 173