چرخه‌ها

یک مثال ساده از جایگشت به صورت زیر به دست می‌آید: هر دو عدد صحیح متمایز بین $1$ و $k$ را انتخاب کنید، مثلاً $p$ و $q$ ، و بنویسید $هرگاه و$ جایگشت $τ$ که بدین ترتیب تعریف می‌شود با $(p, q)$ نشان داده می‌شود؛ هر جایگشتی از این فرم یک جابه‌جایی نامیده می‌شود. اگر $τ$ یک جابه‌جایی باشد، آنگاه $τ^{2} = ϵ$ .

روش مفید دیگر برای ساختن مثال‌ها این است که $p$ عدد صحیح متمایز بین $1$ و $k$ انتخاب کنیم، مثلاً $i_{1}, \dots, i_{p}$ ، و بنویسیم $هرگاه هرگاه$ جایگشت $σ$ که بدین ترتیب تعریف می‌شود با $(i_{1}, \dots, i_{p})$ نشان داده می‌شود. اگر $p = 1$ ، آنگاه $σ = ϵ$ ؛ اگر $p = 2$ ، آنگاه $σ$ یک جابه‌جایی است. برای هر $p$ با شرط $1 < p \leq k$ ، هر جایگشتی به فرم $(i_{1}, \dots, i_{p})$ یک دور p ، یا به سادگی یک دور نامیده می‌شود؛ دورهای $2$ دقیقاً همان جابه‌جایی‌ها هستند. هشدار: فرض نمی‌شود که $i_{1} < \dots < i_{p}$ . اگر، برای مثال، $k = 5$ و $p = 3$ باشد، آنگاه بیست دور متمایز وجود دارد. همچنین توجه کنید که نمادگذاری برای دورها یکتا نیست؛ نمادهای $(1, 2, 3)$ ، $(2, 3, 1)$ ، و $(3, 1, 2)$ همگی نشان‌دهنده یک جایگشت واحد هستند. دو دور $(i_{1}, \dots, i_{p})$ و $(j_{1}, \dots, j_{q})$ در صورتی مجزا هستند که هیچ‌یک از $i$ ها با هیچ‌یک از $j$ ها برابر نباشد. اگر $σ$ و $τ$ دورهای مجزا باشند، آنگاه $σ τ = τ σ$ ، یا به عبارت دیگر، $σ$ و $τ$ جابه‌جاپذیرند.

قضیه ۱. هر جایگشتی حاصل‌ضرب دورهای دو به دو مجزا است.

اثبات. اگر $π$ یک جایگشت باشد و اگر $i$ به گونه‌ای باشد که $π (i) \neq i$ (فعلاً فرض کنید که $π \neq ϵ$ )، دنباله $(i, π (i), π^{2} (i), \dots)$ را تشکیل دهید. از آنجا که تنها تعداد متناهی عدد صحیح متمایز بین $1$ و $k$ وجود دارد، باید توان‌های $p$ و $q$ $(0 \leq p < q)$ وجود داشته باشند به طوری که $π^{p} (i) = π^{q} (i)$ . ویژگی یک‌به‌یک بودن $π$ ایجاب می‌کند که $π^{q - p} (i) = i$ ، یا با یک تغییر بدیهی در نمادگذاری، آنچه ثابت کرده‌ایم این است که باید یک توان اکیداً مثبت $p$ وجود داشته باشد به طوری که $π^{p} (i) = i$ . اگر $p$ به عنوان کوچکترین توان با این ویژگی انتخاب شود، آنگاه اعداد صحیح $i, \dots, π^{p - 1} (i)$ از یکدیگر متمایز هستند. (در واقع، اگر $0 \leq q < r < p$ و $π^{r} (i) = π^{q} (i)$ ، آنگاه $π^{r - q} (i) = i$ ، که با کمینه بودن $p$ در تناقض است.) نتیجه می‌شود که $(i, \dots, π^{p - 1} (i))$ یک دور $p$ است. اگر یک $j$ بین $1$ و $k$ وجود داشته باشد که با هر یک از $i, \dots, π^{p - 1} (i)$ متفاوت باشد و با $π (j)$ نیز متفاوت باشد، رویه‌ای را که ما را به این دور رساند تکرار می‌کنیم، با جایگزینی $j$ به جای $i$ . ما به تشکیل دورها به این شیوه ادامه می‌دهیم تا زمانی که پس از هر گام همچنان بتوانیم عدد صحیح جدیدی پیدا کنیم که $π$ آن را به خودش نمی‌نگارد؛ حاصل‌ضرب دورهای مجزای ساخته شده بدین ترتیب برابر با $π$ است. حالت $π = ϵ$ توسط این توافق کاملاً طبیعی پوشش داده می‌شود که یک حاصل‌ضرب بدون عامل، یعنی یک «حاصل‌ضرب تهی»، باید به عنوان جایگشت همانی تفسیر شود. ◻

قضیه ۲. هر دوری حاصل‌ضربی از جابه‌جایی‌ها است.

اثبات. فرض کنید $σ$ یک دور $p$ باشد؛ به منظور سادگی نمادگذاری، اثبات را که کاملاً کلی است، در حالت خاص $p = 5$ ارائه می‌دهیم. خود اثبات شامل یک خط است: $(i_{1}, i_{2}, i_{3}, i_{4}, i_{5}) = (i_{1}, i_{5}) (i_{1}, i_{4}) (i_{1}, i_{3}) (i_{1}, i_{2}) .$ چند کلمه توضیح اضافی ممکن است مفید باشد. با توجه به تعریف حاصل‌ضرب جایگشت‌ها، سمت راست معادله آخر بر روی هر عدد صحیح بین $1$ و $k$ از داخل به خارج عمل می‌کند، یا شاید بتوان گفت، از راست به چپ. بنابراین، برای مثال، نتیجه اعمال $(i_{1}, i_{5}) (i_{1}, i_{4}) (i_{1}, i_{3}) (i_{1}, i_{2})$ بر $i_{3}$ به صورت زیر محاسبه می‌شود: $(i_{1}, i_{2}) (i_{3}) = i_{3}$ ، $(i_{1}, i_{3}) (i_{3}) = i_{1}$ ، $(i_{1}, i_{4}) (i_{1}) = i_{4}$ ، $(i_{1}, i_{5}) (i_{4}) = i_{4}$ ، به طوری که $(i_{1}, i_{5}) (i_{1}, i_{4}) (i_{1}, i_{3}) (i_{1}, i_{2}) (i_{3}) = i_{4}$ . ◻

به منظور ارجاع، نتیجه فوری زیر از دو قضیه پیشین را ثبت می‌کنیم.

قضیه ۳. هر جایگشتی حاصل‌ضربی از جابه‌جایی‌ها است.

توجه کنید که جابه‌جایی‌ها در قضایای ۲ و ۳ مجزا فرض نشده‌اند؛ در حالت کلی نیز مجزا نیستند.

تمرین‌ها

تمرین ۱.

چند جایگشت در $𝒮_{k}$ وجود دارد؟
چند دور $p$ متمایز در $𝒮_{k}$ ( $1 \leq p \leq k$ ) وجود دارد؟

تمرین ۲. اگر $σ$ و $τ$ جایگشت باشند (در $𝒮_{k}$ )، آنگاه $(σ τ)^{- 1} = τ^{- 1} σ^{- 1}$ .

تمرین ۳.

اگر $σ$ و $τ$ جایگشت باشند (در $𝒮_{k}$ )، آنگاه یک جایگشت یکتای $π$ وجود دارد به طوری که $σ π = τ$ .
اگر $π$ ، $σ$ ، و $τ$ جایگشت‌هایی باشند به طوری که $π σ = π τ$ ، آنگاه $σ = τ$ .

تمرین ۴. مثالی از یک جایگشت بیاورید که حاصل‌ضرب جابه‌جایی‌های مجزا نباشد.

تمرین ۵. ثابت کنید هر جایگشت در $𝒮_{k}$ حاصل‌ضربی از جابه‌جایی‌هایی به فرم $(j, j + 1)$ است، که در آن $1 \leq j < k$ . آیا این تجزیه یکتا است؟

تمرین ۶. آیا معکوس یک دور نیز یک دور است؟

تمرین ۷. ثابت کنید که نمایش یک جایگشت به صورت حاصل‌ضرب دورهای مجزا یکتا است، مگر احتمالاً در مورد ترتیب عوامل.

تمرین ۸. مرتبه یک جایگشت $π$ کوچکترین عدد صحیح $p$ ( $> 0$ ) است به طوری که $π^{p} = ϵ$ .

هر جایگشتی دارای یک مرتبه است.
مرتبه یک دور $p$ چقدر است؟
اگر $σ$ یک دور $p$ ، $τ$ یک دور $q$ ، و $σ$ و $τ$ مجزا باشند، مرتبه $σ τ$ چقدر است؟
مثالی بیاورید تا نشان دهید که فرض مجزا بودن در بخش (c) ضروری است.
اگر $π$ جایگشتی از مرتبه $p$ باشد و اگر $π^{q} = ϵ$ ، آنگاه $q$ بر $p$ بخش‌پذیر است.

تمرین ۹. هر جایگشت در $𝒮_{k}$ ( $k > 1$ ) را می‌توان به صورت یک حاصل‌ضرب نوشت، که هر عامل آن یکی از جابه‌جایی‌های $(1, 2), (1, 3), (1, 4), \dots, (1, k)$ باشد.

تمرین ۱۰. دو جایگشت $σ$ و $τ$ در صورتی مزدوج نامیده می‌شوند که یک جایگشت $π$ وجود داشته باشد به طوری که $σ π = π τ$ . ثابت کنید $σ$ و $τ$ مزدوج هستند اگر و تنها اگر ساختار دوری یکسانی داشته باشند. (این بدان معناست که در نمایش $σ$ به عنوان حاصل‌ضرب دورهای مجزا، تعداد دورهای $p$ ، برای هر $p$ ، با تعداد متناظر برای $τ$ یکسان است.)