30. Permutasiya, inversiya və onların sayı. Tərif 1: çoxluğunun elementlərinin müxtəlif qayda ilə götürülmüş hər bir nizamlı düzülüşünə n elementli permutasiya

30.Permutasiya, inversiya və onların sayı.
Tərif 1: çoxluğunun elementlərinin müxtəlif qayda ilə götürülmüş hər bir nizamlı düzülüşünə n elementli permutasiya deyilir.
Permutasiyada hər hansı iki element arasında aparılmış yerdəyişmə əməliyyatına transpaziisiya deyilir. Məsələn çoxluğunun 123 əvəzləməsində 1 ilə 2 –nin yerini dəyişməklə 213 permutasiyası alarıq.
Verilmiş permutasiyada böyük ədəd kiçik ədəddən əvvəl gələrəsə, bu elementlər arasında pozulma yaxud inversiya baş vermişdir deyirlər. Məsələn 132 permutasiyasında 3 və 2 arasında inversiya baş vermişdir.
78653241 inversiyasında 1-dən əvvəl 7, 2-dən əvvəl 5, 3-dən əvvəl 4, 4-dən əvvəl 4, 5-dən əvvəl 3, 6-dən əvvəl 2 inversiya baş vermişdir. Onda bütün inversiyaların sayı 7+8+6+5+3+2+4+1=25-dir.
Tərif 2: verilmiş permutasiyadakı inversiyaların sayı cütdürsə ona cüt permutasiya, təkdirsə ona tək permutasiya deyilir.
Məsələn, 3214 permutasiya tək 3241 permutasiyası isə cütdür.
Teorem: n elementli bütün permutasiyaların sayı -dir.
İsbatı: n=1 üçün aydındır. n üçün qəbul edək. İxtiyari permutasiyasına n+1 ədədini əlavə edib n+1 elementli n+1 permutasiyasını alarıq. Bu permutasiyada n+1-in növbə ilə ilə yerini dəyişməklə n sayda yeni permutasiyalar alırıq ki, a permutasiyası ilə birlikdə n+1 sayda permutasiya alınmış olar. Deməli hər bir n elementli permutasiyadan n+1 sayda permutasiya alınır. Nəticədə sayda permutasiya alınır.
*Bildiyimiz kimi permutasiyada ixtiyari iki element arasında aparılmış yerdəyişmə əməliiyyatına transpozisiya deyilir.
Qeyd edək ki, istənilən iki permutasiyanın birindən digərinə sonlu sayda transpozisiyanın köməyi ilə keçmək olar.
Teorem: Hər bir transpozisiya permutasiyanın cütlüyünü dəyişir.
İsbatı: Əgər permutasiyasında -dirsə, onda permutasiyasında bir transpozisiya aparılmış olar ki, bunun təsiri ilə permutasiya əvvəl cüt idisə indi tək, əvvəl tək idisə indi cüt olar. İndi fərz edək ki,
(1)
permutasiyasında və ədədlərinin yerdəyişməsi nəticəsində
(2)
Permutasiyası alınmışdır. Bunun üçün əvvəlcə -ni -dan sağa gətirmək üçün sayda, sonra -nı -nin yerinə gətirmək üçün sayda transpozisiya aparmaq lazımdır.Bütün transpozisiyaların sayı olar ki, nəticədə (1) permutasiyası cüt olduqda (2) tək, (1) tək olduqda (2) cüt olur.