Алгоритм пошуку кількості рухомих точок підстановок із силовських 2-підгруп Syl2(S2n) симетричних груп S2n

Simple item page
dc.contributor.authorОльшевська, Віта
dc.date.accessioned2022-05-26T15:56:04Z
dc.date.available2022-05-26T15:56:04Z
dc.date.issued2021
dc.description.abstractУ статті запропоновано алгоритм пошуку кількості рухомих точок підстановок силовських 2-підгруп Syl2(S2n) симетричних груп S2n, n є N. Для побудови цього алгоритму використано ізоморфізм між групою Syl2(S2n) та групою бінарних кореневих дерев з мітками. Також обчислено складність запропонованого алгоритму та його середню кількість кроків для силовської 2-підгрупи симетричної групи S2n. Обраховано кількість підстановок із Syl2(S2n), що мають максимальну кількість рухомих точок.uk_UA
dc.description.abstractThe Symmetric permutation group S2n is a classical algebraic object that is also used in Computer science, Coding theory, Statistics, etc. In particular, the coding theory considers codes defined on the symmetric group Sn or its subgroups. The research of permutation codes has been started from 1970s. These codes can be obtained with using different distances: Hamming, Ulam, Cailey, Levenshtein. The finding distance on permutations depends on their number of fixed or unfixed points. Therefore, it is natural to count the number of unfixed points in a certain group of permutations. In this paper, we consider the number of unfixed points of permutations that are elements of the Sylow 2-subgroup Syl2(S2n) of symmetric groups S2n. Leo Kaluzhnin used tables to represent the elements of these groups [8]. Volodymyr Nekrashevych represented permutations by their portraits [9]. We use algorithms that describe the connection between the permutation group Syl2(S2n) and the group of labeled, binary rooted trees [10]. An algorithm for finding the number of unfixed points for permutations of the Sylow 2-subgroup Syl2(S2n) of the symmetric group S2n is proposed in the article. An isomorphism between the group Syl2(S2n) and a group of labeled, binary root trees was used to construct this algorithm. It is proved, that the algorithm of searching the number of unfixed point for permutations of the Sylow 2-subgroup Syl2(S2n) of the symmetric group S2n has complexity O(2n). In addition, the average number of steps of the algorithm for the Sylow 2-subgroup of the symmetric group S2n is found. The result for small n (n = 2, 3, 4) was verified with a program, that is written in the language of the computer algebra Sage. At the end of the article we find the number of permutations from Syl2(S2n) that have a maximum number of unfixed points. The number of such permutations in the symmetric group S2n is well known. Obviously that this number is smaller for the Sylow 2-subgroup of the symmetric group Syl2(S2n). In this case, we calculate the maximum number of unfixed points using a recursive formula.en_US
dc.identifier.citationОльшевська В. А. Алгоритм пошуку кількості рухомих точок підстановок із силовських 2-підгруп Syl2(S2n) симетричних груп S2n / Ольшевська В. А. // Могилянський математичний журнал. - 2021. - Т. 4. - С. 34-40. - https://doi.org/10.18523/2617-70804202134-40uk_UA
dc.identifier.issn2617-7080
dc.identifier.issn2663-0648
dc.identifier.urihttps://doi.org/10.18523/2617-70804202134-40
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/23007
dc.language.isoukuk_UA
dc.relation.sourceМогилянський математичний журналuk_UA
dc.statusfirst publisheduk_UA
dc.subjectрухомі точкиuk_UA
dc.subjectсиметричні групиuk_UA
dc.subjectсиловські підгрупиuk_UA
dc.subjectалгоритмuk_UA
dc.subjectскладність алгоритмуuk_UA
dc.subjectстаттяuk_UA
dc.subjectunfixed pointsen_US
dc.subjectsymmetric groupsen_US
dc.subjectsylow subgroupsen_US
dc.subjectalgorithmen_US
dc.subjectcomplexityen_US
dc.titleАлгоритм пошуку кількості рухомих точок підстановок із силовських 2-підгруп Syl2(S2n) симетричних груп S2nuk_UA
dc.title.alternativeSearch algorithm of the number of unfixed points of permutations from sylow 2-subgroups Syl2(S2n) of symmetric groups S2nen_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Olshevska_Alhorytm_poshuku_kilkosti_rukhomykh_tochok_pidstanovok_iz_sylovskykh_2-pidhrup_Syl2(S2n)_symetrychnykh_hrup_S2n.pdf
Size:
278.32 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Том 4