Циклична пермутација

Из Википедије, слободне енциклопедије

Појам цикличне пермутације се користи на различите мада сличне начине:

Прва дефиниција[уреди]

Пресликавање пермутације

Пермутација P над скупом S са k елемената се назива цикличном пермутацијом са померајем t ако и само ако

се елементи S могу уредити (c[1] < c[2] < ... < c[k]) и пресликавање P се може записати као:
p(c[i]) = c[i + t] за i = 1, 2, ..., k  − t, и
p(c[i]) = c[i + tk] за i = k − t + 1, k − t + 2, ..., k.

Напомена: Свака циклична пермутација дефинисана на овај начин ће бити конструисана од тачно нзд(kt) дисјунктних циклуса.

Цикличне пермутације дефинисане на овај начин се називају и ротацијама.

Пример:


\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 7 & 6 & 8 \\ 3 & 4 & 5 & 7 & 6 & 8 & 1 & 2 \end{pmatrix}

је циклична пермутација са померајем 2. Може се конструисати од нзд(2, 8) = 2 циклуса; види слику. Коришћено уређење је: c[6] := 7, c[7] :=6, c[i] = i у осталим случајевима.

Друга дефиниција[уреди]

пресликавање пермутације

Пермутација се назива цикличном ако и само ако се састоји од тачно једног циклуса.

Напомена: Свака пермутација над скупом са k елемената је циклична пермутација по овој дефиницији ако и само ако је циклична пермутација по првој дефиницији и нзд(k, померај) = 1

Пример:


\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 7 & 6 & 8 \\ 4 & 5 & 7 & 6 & 8 & 1 & 2 & 3 \end{pmatrix} =
\begin{pmatrix} 1 & 4 & 6 & 2 & 5 & 8 & 3 & 7 \\ 4 & 6 & 2 & 5 & 8 & 3 & 7 & 1 \end{pmatrix}

Трећа дефиниција[уреди]

пресликавање пермутације

Пермутација се назива цикличном ако и само ако само један од циклуса који је граде има дужину ≥ 1.

Напомена: Свака циклична пермутација дефинисана на овај начин се може посматрати као унија цикличне пермутације по другој дефиницији и неких фиксираних тачака.

Свака циклична пермутација по другој дефиницији се може посматрати као циклична пермутација по трећој дефиницији са нула фиксираних тачака.

Пример:


\begin{pmatrix} 1 & 4 & 6 & 8 & 3 & 7 & 2 & 5 \\ 4 & 6 & 8 & 3 & 7 & 1 & 2 & 5 \end{pmatrix}

Литература[уреди]

  • Ayres, Frank, Schaum's Outline of Modern Abstract Algebra, McGraw-Hill; 1st edition (June 1, 1965). ISBN 0-07-002655-6.

Види још[уреди]