Permütasyon

Altı sıranın her biri üç farklı topun farklı bir permütasyonudur ⓘ

Matematikte, bir kümenin permütasyonu, gevşek bir şekilde, üyelerinin bir dizi veya doğrusal sıraya göre düzenlenmesi veya küme zaten sıralıysa, öğelerinin yeniden düzenlenmesidir. "Permütasyon" kelimesi aynı zamanda sıralı bir kümenin doğrusal düzenini değiştirme eylemini veya sürecini de ifade eder. ⓘ

Permütasyonlar, sıralamaya bakılmaksızın bir kümenin bazı üyelerinin seçimi olan kombinasyonlardan farklıdır. Örneğin, çiftler olarak yazıldığında, {1, 2, 3} kümesinin (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) ve (3, 2, 1) olmak üzere altı permütasyonu vardır. Bunlar, bu üç elemanlı kümenin tüm olası sıralamalarıdır. Harfleri farklı olan kelimelerin anagramları da permütasyondur: harfler orijinal kelimede zaten sıralanmıştır ve anagram harflerin yeniden sıralanmasıdır. Sonlu kümelerin permütasyonlarının incelenmesi, kombinatorik ve grup teorisi alanlarında önemli bir konudur. ⓘ

Permütasyonlar matematiğin hemen her dalında ve diğer birçok bilim alanında kullanılmaktadır. Bilgisayar biliminde, sıralama algoritmalarını analiz etmek için; kuantum fiziğinde, parçacıkların durumlarını tanımlamak için; ve biyolojide, RNA dizilerini tanımlamak için kullanılırlar. ⓘ

N farklı nesnenin permütasyon sayısı n faktöriyeldir, genellikle n! olarak yazılır, bu da n'den küçük veya n'ye eşit tüm pozitif tam sayıların çarpımı anlamına gelir. ⓘ

Teknik olarak, bir S kümesinin permütasyonu, S'den kendisine bir bijeksiyon olarak tanımlanır. Yani, S'den S'ye her elemanın görüntü değeri olarak tam bir kez ortaya çıktığı bir fonksiyondur. Bu, her s elemanının karşılık gelen f(s) ile değiştirildiği S elemanlarının yeniden düzenlenmesi ile ilgilidir. Örneğin, yukarıda bahsedilen (3, 1, 2) permütasyonu şu fonksiyonla tanımlanır $\alpha$ olarak tanımlanır ⓘ

$\alpha (1)=3,\quad \alpha (2)=1,\quad \alpha (3)=2$. ⓘ

Bir kümenin tüm permütasyonlarının toplamı, kümenin simetrik grubu olarak adlandırılan bir grup oluşturur. Grup işlemi, başka bir yeniden düzenlemeyle sonuçlanan bileşimdir (verilen iki yeniden düzenlemenin art arda yapılması). Permütasyonların özellikleri küme elemanlarının doğasına bağlı olmadığından, genellikle kümenin permütasyonları $\{1,2,\ldots ,n\}$ permütasyonları incelemek için dikkate alınır. ⓘ

Temel kombinatorikte, k-permutasyonlar veya kısmi permütasyonlar, bir kümeden seçilen k farklı elemanın sıralı düzenlemeleridir. Kümenin boyutu k'ya eşit olduğunda, bunlar kümenin permütasyonlarıdır. ⓘ

Ernő Rubik tarafından 1974 yılında icat edilen popüler Rubik küpü bulmacasında, bulmaca yüzlerinin her dönüşü yüzey renklerinin bir permütasyonunu oluşturur. ⓘ

1'den 10'a kadar olan doğal sayıları içeren n elemanlı kümede r = 4 olarak alınırsa permütasyonların sayısı {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} kümesinden sırayı da gözetmek suretiyle oluşturulabilecek dört değişik elemanlı kümelerin sayısını ifade eder. ⓘ

Tarihçe

Heksagram adı verilen permütasyonlar Çin'de I Ching'de (Pinyin: Yi Jing) MÖ 1000 gibi erken bir tarihte kullanılmıştır. ⓘ

Bir Arap matematikçi ve kriptograf olan Al-Khalil (717-786) Kriptografik Mesajlar Kitabı'nı yazmıştır. Permütasyon ve kombinasyonların ilk kullanımını içeren bu kitapta, sesli ve sessiz tüm olası Arapça sözcükler listelenmiştir. ⓘ

N nesnenin permütasyon sayısını belirleme kuralı 1150 civarında Hint kültüründe biliniyordu. Hintli matematikçi Bhaskara II'nin Lilavati adlı eserinde şu anlama gelen bir pasaj bulunmaktadır:

Birlik ile başlayıp artan ve basamak sayısına kadar devam eden aritmetik serilerin çarpımının ürünü, sayının belirli rakamlarla varyasyonları olacaktır. ⓘ

1677 yılında Fabian Stedman, çan değişiminde çanların permütasyon sayısını açıklarken faktöriyelleri tanımlamıştır. İki çandan başlayarak: "ilk olarak, iki çanın iki şekilde değiştiği kabul edilmelidir" ve bunu 1 2 ve 2 1'i göstererek açıklar. Daha sonra üç çanla "üçten üç kere iki figür üretilebileceğini" açıklar ve bunu yine örneklerle gösterir. Açıklamasında "3'ü atarsak 1.2 kalır; 2'yi atarsak 1.3 kalır; 1'i atarsak 2.3 kalır" ifadeleri yer almaktadır. Daha sonra dört çana geçer ve dört farklı üçlü küme olacağını gösteren uzaklaştırma argümanını tekrarlar. Etkili bir şekilde, bu özyinelemeli bir süreçtir. "Uzaklaştırma" yöntemini kullanarak beş çan ile devam eder ve ortaya çıkan 120 kombinasyonu tablolaştırır. Bu noktada pes eder ve şöyle der:

Bu yöntemlerin doğası öyledir ki, bir sayıdaki değişiklikler daha küçük sayılardaki değişiklikleri de kapsar, ... öyle ki, bir sayıdaki değişikliklerden oluşan tam bir Peal, daha küçük sayılardaki tam Peal'lerin tek bir bütün halinde birleşmesiyle oluşmuş gibi görünür;

Stedman permütasyon düşüncesini genişletir; alfabedeki harflerin ve 20 atlık bir ahırdaki atların permütasyon sayısını düşünmeye devam eder. ⓘ

Görünüşte birbiriyle ilgisiz matematiksel soruların permütasyonlar yardımıyla incelendiği ilk vaka, 1770 civarında, Joseph Louis Lagrange'ın polinom denklemleri üzerinde çalışırken, bir denklemin köklerinin permütasyonlarının özelliklerinin denklemi çözme olasılıklarıyla ilişkili olduğunu gözlemlemesiyle ortaya çıkmıştır. Bu çalışma çizgisi, Évariste Galois'in çalışmasıyla, polinom denklemlerinin (bir bilinmeyenli) radikallerle çözülmesine ilişkin neyin mümkün neyin imkansız olduğunun tam bir tanımını veren Galois teorisiyle sonuçlandı. Modern matematikte, bir problemi anlamanın onunla ilgili belirli permütasyonları incelemeyi gerektirdiği birçok benzer durum vardır. ⓘ

Tekrarı olmayan permütasyonlar

Permütasyonların en basit örneği, n öğeyi n yere yerleştirmenin olası yollarının sayısını düşündüğümüz tekrarsız permütasyonlardır. Faktöriyel, tekrarları içermeyen bir kümedeki permütasyonların sayısını tanımlamada özel bir uygulamaya sahiptir. "n faktöriyel" olarak okunan n! sayısı, tam olarak n şeyi yeni bir düzende yeniden düzenleyebileceğimiz yolların sayısıdır. Örneğin, portakal, elma ve armut olmak üzere üç meyvemiz varsa, bunları belirtilen sırayla yiyebilir veya değiştirebiliriz (örneğin, bir elma, bir armut ve sonra bir portakal). O halde permütasyonların tam sayısı $3!=1\cdot 2\cdot 3=6$. Öğe sayısı (n) arttıkça bu sayı son derece büyük olur. ⓘ

Benzer bir şekilde, n nesneden k öğenin düzenlenme sayısına bazen kısmi permütasyon veya k-permutasyon denir. Şu şekilde yazılabilir $nPk$ ("n permute k" olarak okunur) ve sayıya eşittir $n(n-1)\cdots (n-k+1)$ (olarak da yazılır $n!/(n-k)!$). ⓘ

Tanım

Matematik metinlerinde permütasyonları küçük Yunan harfleri kullanarak ifade etmek gelenekseldir. Genellikle, ya $\alpha$ ve $\beta$veya $\sigma ,\tau$ ve $\pi$ kullanılır. ⓘ

Permütasyonlar bir S kümesinden kendi üzerine bijectionlar olarak tanımlanabilir. N elemanlı bir kümenin tüm permütasyonları simetrik bir grup oluşturur ve şu şekilde gösterilir $S_{n}$Burada grup işlemi fonksiyon bileşimidir. Böylece iki permütasyon için, $\pi$ ve $\sigma$ grup içinde $S_{n}$dört grup aksiyomu geçerlidir: ⓘ

1. Kapanış: Eğer $\pi$ ve $\sigma$ içinde $S_{n}$ o zaman öyle $\pi \sigma .$
2. İlişkisellik: Herhangi üç permütasyon için $\pi ,\sigma ,\tau \in S_{n}$, $(\pi \sigma )\tau =\pi (\sigma \tau ).$
3. Özdeşlik: Bir özdeşlik permütasyonu vardır, şöyle gösterilir $\operatorname {id}$ ve tarafından tanımlanan $\operatorname {id} (x)=x$ herkes için $x\in S$. Herhangi biri için $\sigma \in S_{n}$, $\operatorname {id} \sigma =\sigma \operatorname {id} =\sigma .$
4. Ters çevrilebilirlik: Her permütasyon için $\pi \in S_{n}$varsa $\pi ^{-1}\in S_{n}$ böylece $\pi \pi ^{-1}=\pi ^{-1}\pi =\operatorname {id} .$

Genel olarak, iki permütasyonun bileşimi değişmeli değildir, yani, $\pi \sigma \neq \sigma \pi .$ ⓘ

Bir kümeden kendisine bir bijeksiyon olarak permütasyon, bir kümenin yeniden düzenlenmesini gerçekleştiren bir fonksiyondur ve kendisi bir yeniden düzenleme değildir. Daha eski ve daha temel bir bakış açısı ise permütasyonların yeniden düzenlemelerin kendisi olduğudur. Bu ikisini birbirinden ayırmak için bazen permütasyon teriminin önüne aktif ve pasif tanımlayıcıları eklenirken, eski terminolojide ikameler ve permütasyonlar kullanılır. ⓘ

Bir permütasyon bir veya daha fazla ayrık döngüye, yani permütasyonun bazı elemanlar üzerindeki uygulamasının tekrar tekrar izlenmesi ile bulunan yörüngelere ayrıştırılabilir. Örneğin, permütasyon $\sigma$ tarafından tanımlanan $\sigma (7)=7$ 1 döngüsüne sahiptir, $(\,7\,)$ permütasyon ise $\pi$ tarafından tanımlanan $\pi (2)=3$ ve $\pi (3)=2$ 2 döngüye sahiptir $(\,2\,3\,)$ (sözdizimiyle ilgili ayrıntılar için aşağıdaki § Döngü gösterimi bölümüne bakınız). Genel olarak, k uzunluğundaki, yani k elemandan oluşan bir döngüye k-döngüsü denir. ⓘ

1-döngüsündeki bir eleman $(\,x\,)$ permütasyonun sabit noktası olarak adlandırılır. Hiçbir sabit noktası olmayan bir permütasyona sapma denir. 2-döngülere transpozisyon denir; bu tür permütasyonlar sadece iki elemanı değiştirir, diğerlerini sabit bırakır. ⓘ

Notasyonlar

Permütasyonları elemanter olarak, yani parçalı fonksiyonlar olarak yazmak zahmetli olduğundan, bunları daha kompakt bir şekilde temsil etmek için çeşitli notasyonlar icat edilmiştir. Döngü gösterimi, kompaktlığı ve bir permütasyonun yapısını şeffaf hale getirmesi nedeniyle birçok matematikçi için popüler bir seçimdir. Aksi belirtilmedikçe bu makalede kullanılan gösterim budur, ancak diğer gösterimler özellikle uygulama alanlarında hala yaygın olarak kullanılmaktadır. ⓘ

İki satırlı gösterim

Cauchy'nin iki satırlı gösteriminde, S'nin elemanları ilk satırda ve her biri için altındaki görüntüsü ikinci satırda listelenir. Örneğin, S = {1, 2, 3, 4, 5} kümesinin belirli bir permütasyonu şu şekilde yazılabilir

$\sigma ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}};$

Bu, σ'nın σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3 ve σ(5) = 1 değerlerini sağladığı anlamına gelir. S'nin elemanları ilk satırda herhangi bir sırada görünebilir. Bu permütasyon şu şekilde de yazılabilir:

$\sigma ={\begin{pmatrix}3&2&5&1&4\\4&5&1&2&3\end{pmatrix}},$

veya

$\sigma ={\begin{pmatrix}5&1&4&3&2\\1&2&3&4&5\end{pmatrix}}.$ ⓘ

Tek satırlık gösterim

Eğer S'nin elemanları için "doğal" bir sıra varsa, örneğin $x_{1},x_{2},\ldots ,x_{n}$sonra bunu iki satırlı gösterimin ilk satırı için kullanır:

$\sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.$ ⓘ

Bu varsayım altında, ilk satır atlanabilir ve permütasyon tek satırlık gösterimde şu şekilde yazılabilir

$(\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n}))$,

Yani, S'nin elemanlarının sıralı bir düzenlemesi olarak. Tek satır gösterimini aşağıda açıklanan döngü gösteriminden ayırt etmek için dikkatli olunmalıdır. Matematik literatüründe yaygın bir kullanım, tek satırlı gösterim için parantezleri atlarken, döngü gösterimi için parantezleri kullanmaktır. Tek satırlık gösterim aynı zamanda bir permütasyonun kelime gösterimi olarak da adlandırılır. Yukarıdaki örnek 2 5 4 3 1 şeklinde olacaktır çünkü ilk satır için 1 2 3 4 5 doğal sırası varsayılacaktır. (Bu girdileri ayırmak için virgül kullanmak tipiktir, ancak bazılarında iki veya daha fazla rakam varsa). Bu form daha derli topludur ve temel kombinatorik ve bilgisayar bilimlerinde yaygındır. Özellikle S'nin elemanlarının veya permütasyonların büyük veya küçük olarak karşılaştırılacağı uygulamalarda kullanışlıdır. ⓘ

Döngü gösterimi

Döngü gösterimi, permütasyonun küme elemanları üzerinde tekrar tekrar uygulanmasının etkisini tanımlar. Permütasyonu döngülerin bir çarpımı olarak ifade eder; farklı döngüler ayrık olduğundan, buna "ayrık döngülere ayrıştırma" denir. ⓘ

Permütasyonu yazmak için $\sigma$ çevrim gösteriminde, aşağıdaki şekilde ilerlenir:

1. Bir açılış parantezi yazın ve ardından rastgele bir x elemanı seçin $S$ ve yazınız: $(\,x$
2. Sonra x'in yörüngesinin izini sürün; yani, x'in ardışık uygulamaları altındaki değerlerini yazın $\sigma$: $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots$
3. Değer x'e dönene kadar tekrarlayın ve x yerine bir kapanış parantezi yazın: $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)$
4. Şimdi S'nin henüz yazılmamış bir y elemanı ile devam edin ve aynı şekilde ilerleyin: $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)(\,y\,\ldots \,)$
5. S'nin tüm elemanları döngüler halinde yazılana kadar tekrarlayın. ⓘ

Böylece 2 5 4 3 1 permütasyonu (tek satırlık gösterimde) döngü gösteriminde (125)(34) olarak yazılabilir. ⓘ

Genel olarak permütasyonlar gidip gelmezken, ayrık döngüler gider; örneğin,

$$(\,1\,2\,5\,)(\,3\,4\,)=(\,3\,4\,)(\,1\,2\,5\,).$$

Ayrıca, her bir döngü farklı başlangıç noktaları seçilerek farklı şekillerde yazılabilir; örneğin,

$$(\,1\,2\,5\,)(\,3\,4\,)=(\,5\,1\,2\,)(\,3\,4\,)=(\,2\,5\,1\,)(\,4\,3\,).$$

Belirli bir permütasyonun ayrık döngülerini birçok farklı şekilde yazmak için bu eşitlikler birleştirilebilir. ⓘ

Bağlamın açık olması koşuluyla, 1-döngüler genellikle döngü gösteriminden çıkarılır; S'de herhangi bir döngüde görünmeyen herhangi bir x elemanı için, örtük olarak $\sigma (x)=x$. Yalnızca 1-döngülerinden oluşan özdeşlik permütasyonu tek bir 1-döngüsü (x), 1 sayısı veya id ile gösterilebilir. ⓘ

Döngü gösteriminin kullanışlı bir özelliği, bir permütasyonun tersinin döngü gösteriminin, permütasyonun döngülerindeki elemanların sırasını tersine çevirerek verilmesidir. Örneğin,

$$[(\,1\,2\,5\,)(\,3\,4\,)]^{-1}=(\,5\,2\,1\,)(\,4\,3\,).$$

ⓘ

Kanonik döngü gösterimi

Bazı kombinatoryal bağlamlarda, döngülerdeki elemanlar ve (ayrık) döngülerin kendileri için belirli bir sırayı sabitlemek yararlıdır. Miklós Bóna aşağıdaki sıralama seçeneklerini kanonik döngü gösterimi olarak adlandırır:

• her döngüde en büyük eleman ilk olarak listelenir
• döngüler ilk elemanlarına göre artan sırada sıralanır ⓘ

Örneğin, (312)(54)(8)(976) kanonik döngü gösteriminde bir permütasyondur. Kanonik döngü gösterimi tek döngüleri atlamaz. ⓘ

Richard P. Stanley aynı gösterim seçimini bir permütasyonun "standart gösterimi" olarak adlandırır ve Martin Aigner aynı kavram için "standart form" terimini kullanır. Sergey Kitaev de "standart biçim" terminolojisini kullanır, ancak her iki seçimi de tersine çevirir; yani, her döngü önce en az elemanını listeler ve döngüler en az, yani ilk elemanlarına göre azalan sırada sıralanır. ⓘ

Permütasyonların bileşimi

İki permütasyonun bileşimini göstermenin iki yolu vardır. $\sigma \cdot \pi$ kümenin herhangi bir x elemanını $\sigma (\pi (x))$. En sağdaki permütasyon ilk olarak argümana uygulanır, fonksiyon uygulamasının yazılma şekli nedeniyle. ⓘ

Fonksiyon bileşimi ilişkisel olduğu için permütasyonlar üzerindeki bileşim işlemi de ilişkiseldir: $(\sigma \pi )\tau =\sigma (\pi \tau )$. Bu nedenle, ikiden fazla permütasyonun çarpımları genellikle gruplamayı ifade etmek için parantez eklenmeden yazılır; ayrıca genellikle bileşimi belirtmek için nokta veya başka bir işaret olmadan yazılırlar. ⓘ

Bazı yazarlar en soldaki faktörün önce hareket etmesini tercih eder, ancak bu amaçla permütasyonlar argümanlarının sağına, genellikle üs olarak yazılmalıdır, burada x üzerine etki eden σ, x^σ olarak yazılır; daha sonra çarpım xσ-π = (x^σ)^π ile tanımlanır. Ancak bu permütasyonları çarpmak için farklı bir kural verir; bu makale en sağdaki permütasyonun ilk uygulandığı tanımı kullanır. ⓘ

Permütasyon teriminin diğer kullanımları

Sıralı bir düzenleme olarak permütasyon kavramı, permütasyon olmayan ancak literatürde permütasyon olarak adlandırılan birkaç genellemeyi kabul eder. ⓘ

n'in k-permutasyonları

Permütasyon teriminin bazen temel kombinatorik metinlerinde kullanılan daha zayıf bir anlamı, hiçbir elemanın birden fazla kez yer almadığı, ancak belirli bir kümedeki tüm elemanları kullanma zorunluluğu olmayan sıralı düzenlemeleri belirtir. Bunlar özel durumlar dışında permütasyon değildir, ancak sıralı düzenleme kavramının doğal genellemeleridir. Aslında, bu kullanım genellikle n büyüklüğündeki belirli bir kümeden alınan elemanların sabit bir k uzunluğundaki düzenlemelerini dikkate almayı içerir, başka bir deyişle, n'nin bu k-permutasyonları, bir n kümesinin k elemanlı bir alt kümesinin farklı sıralı düzenlemeleridir (bazen eski literatürde varyasyonlar veya düzenlemeler olarak adlandırılır). Bu nesneler kısmi permütasyonlar veya tekrarsız diziler olarak da bilinir; bu terimler "permütasyon "un daha yaygın olan diğer anlamıyla karıştırılmasını önler. Bu tür nesnelerin sayısı $k$-permutasyonları $n$ gibi çeşitli sembollerle gösterilir. $P_{k}^{n}$, $_{n}P_{k}$, $^{n}P_{k}$, $P_{n,k}$veya $P(n,k)$ve değeri çarpım tarafından verilir

$P(n,k)=\underbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} _{k\ \mathrm {factors} }$, ⓘ

Bu değer k > n olduğunda 0'dır ve aksi takdirde

${\frac {n!}{(n-k)!}}.$ ⓘ

Ürün, şu varsayım olmaksızın iyi tanımlanmıştır $n$ negatif olmayan bir tamsayıdır ve kombinatorik dışında da önemlidir; Pochhammer sembolü olarak bilinir $(n)_{k}$ ya da $k$-th düşen faktöriyel güç $n^{\underline {k}}$ . $n$. ⓘ

Permütasyon teriminin bu kullanımı kombinasyon terimiyle yakından ilişkilidir. Bir n-kümesi S'nin k-elemanlı bir kombinasyonu, elemanları sıralanmamış S'nin k elemanlı bir alt kümesidir. S'nin tüm k elemanlı alt kümelerini alıp her birini mümkün olan tüm şekillerde sıraladığımızda, S'nin tüm k-permutasyonlarını elde ederiz. n kümesinin k-kombinasyonlarının sayısı, C(n,k), bu nedenle n'nin k-permutasyonlarının sayısı ile ilişkilidir:

$C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {\tfrac {n!}{(n-k)!}}{\tfrac {k!}{0!}}}={\frac {n!}{(n-k)!\,k!}}.$ ⓘ

Bu sayılar binom katsayıları olarak da bilinir ve şu şekilde gösterilir ${\binom {n}{k}}$. ⓘ

Tekrarlı permütasyonlar

Bir S kümesinin k elemanının, tekrara izin verilen sıralı düzenlemelerine k-tuples denir. Genel olarak permütasyon olmasalar da bazen tekrarlı permütasyon olarak da adlandırılırlar. Bazı bağlamlarda S alfabesi üzerinde sözcükler olarak da adlandırılırlar. Eğer S kümesinin n elemanı varsa, S üzerindeki k-tuple sayısı $n^{k}.$ Bir elemanın bir k-tuple'da ne kadar sık görünebileceği konusunda bir kısıtlama yoktur, ancak bir elemanın ne kadar sık görünebileceği konusunda kısıtlamalar getirilirse, bu formül artık geçerli değildir. ⓘ

Çoklu kümelerin permütasyonları

Çoklu kümelerin permütasyonları ⓘ

Eğer M sonlu bir çoklu küme ise, çoklu küme permütasyonu, M'nin elemanlarının, her bir elemanın M'deki çokluğuna eşit sayıda göründüğü sıralı bir düzenlemesidir. Bazı tekrarlanan harflere sahip bir kelimenin anagramı, çoklu küme permütasyonuna bir örnektir. Eğer M'nin elemanlarının çoklukları (belli bir sırayla alındığında) $m_{1}$, $m_{2}$, ..., $m_{l}$ ve bunların toplamı (yani M'nin boyutu) n ise, M'nin çok kümeli permütasyonlarının sayısı multinom katsayısı ile verilir,

${n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}={\frac {\left(\sum _{i=1}^{l}{m_{i}}\right)!}{\prod _{i=1}^{l}{m_{i}!}}}.$ ⓘ

Örneğin, MISSISSIPPI sözcüğünün farklı anagramlarının sayısı:

${\frac {11!}{1!\,4!\,4!\,2!}}=34650$. ⓘ

Bir M çoklu kümesinin k-permutasyonu, her bir elemanın M'deki çokluğuna (bir elemanın tekrar sayısı) eşit veya daha az sayıda göründüğü M'nin elemanlarının k uzunluğundaki bir dizisidir. ⓘ

Dairesel permütasyonlar

Permütasyonlar, düzenlemeler olarak düşünüldüğünde, bazen doğrusal sıralı düzenlemeler olarak adlandırılır. Bu düzenlemelerde bir birinci eleman, bir ikinci eleman ve bu şekilde devam eder. Ancak, nesneler dairesel bir şekilde düzenlenirse, bu ayırt edici sıralama artık mevcut değildir, yani düzenlemede "ilk eleman" yoktur, herhangi bir eleman düzenlemenin başlangıcı olarak kabul edilebilir. Nesnelerin dairesel bir şekilde düzenlenmesine dairesel permütasyonlar denir. Bunlar resmi olarak nesnelerin sıradan permütasyonlarının denklik sınıfları olarak tanımlanabilir, çünkü denklik ilişkisi doğrusal düzenlemenin son elemanını önüne taşıyarak oluşturulur. ⓘ

İki dairesel permütasyon, biri diğerinin içine döndürülebiliyorsa (yani, elemanların göreceli konumlarını değiştirmeden çevrilebiliyorsa) eşdeğerdir. Dört harf üzerinde aĢağıdaki dört dairesel permütasyonun aynı olduğu kabul edilir. ⓘ

     1           4           2           3
   4   3       2   1       3   4       1   2
     2           3           1           4 <span title="Kaynak: İngilizce Vikipedi, Bölüm "Circular permutations"" class="plainlinks">[https://en.wikipedia.org/wiki/Permutation#Circular_permutations <span style="color:#dddddd">ⓘ</span>]</span>

Dairesel düzenlemeler saat yönünün tersine okunmalıdır, bu nedenle aşağıdaki ikisi eşdeğer değildir çünkü hiçbir döndürme birini diğerine getiremez.

     1          1
   4   3      3   4
     2          2 <span title="Kaynak: İngilizce Vikipedi, Bölüm "Circular permutations"" class="plainlinks">[https://en.wikipedia.org/wiki/Permutation#Circular_permutations <span style="color:#dddddd">ⓘ</span>]</span>

N elemanlı bir S kümesinin dairesel permütasyonlarının sayısı (n - 1)! ⓘ

Özellikler

n farklı nesnenin permütasyonlarının sayısı n! ⓘ

k ayrık döngüye sahip n-permutasyon sayısı, c(n, k) ile gösterilen birinci türden işaretsiz Stirling sayısıdır. ⓘ

Permütasyon türü

Bir permütasyonun döngüleri (sabit noktalar dahil) $\sigma$ n elemanlı bir kümenin bu kümeyi bölümlemesi; bu nedenle bu döngülerin uzunlukları n'nin bir bölümünü oluşturur ve bu bölüm n'nin döngü tipi olarak adlandırılır. $\sigma$. 'nin her sabit noktası için döngü tipinde bir "1" vardır. $\sigma$, her transpozisyon için bir "2" ve bu şekilde devam eder. Döngü tipi $\beta =(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)$ o $(3,2,2,1).$ ⓘ

Bu, daha kompakt bir biçimde [1¹2²3¹] olarak da yazılabilir. Daha kesin olarak, genel form şöyledir $[1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]$, nerede $\alpha _{1},\ldots ,\alpha _{n}$ ilgili uzunluktaki döngülerin sayısıdır. Belirli bir türdeki permütasyonların sayısı

${\frac {n!}{1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}\alpha _{1}!\alpha _{2}!\dotsm \alpha _{n}!}}$. ⓘ

Eşlenik permütasyonlar

Genel olarak, döngü gösteriminde yazılmış permütasyonların bileşimi kolayca tanımlanabilen bir model izlemez - bileşimin döngüleri bileştirilenlerden farklı olabilir. Bununla birlikte, bir permütasyonun eşlenik hale getirildiği özel durumda döngü yapısı korunur $\sigma$ başka bir permütasyonla $\pi$Bu da ürünün oluşturulması anlamına gelir $\pi \sigma \pi ^{-1}$. İşte, $\pi \sigma \pi ^{-1}$ 'nin eşleniğidir. $\sigma$ tarafından $\pi$ için döngü gösterimi alınarak elde edilebilir. $\sigma$ ve uygulamak $\pi$ tüm girdilere eşleniktir. Buradan, iki permütasyonun aynı türe sahip olduklarında tam olarak eşlenik oldukları sonucu çıkar. ⓘ

Permütasyon sırası

Bir permütasyonun sırası $\sigma$ m en küçük pozitif tamsayı olmak üzere $\sigma ^{m}=\mathrm {id}$. Döngü uzunluklarının en küçük ortak katıdır. Örneğin, sırası $(\,1\,3\,2)(\,4\,5\,)$ o $2\cdot 3=6$. ⓘ

Bir permütasyonun paritesi

Sonlu bir kümenin her permütasyonu, transpozisyonların çarpımı olarak ifade edilebilir. Belirli bir permütasyon için bu tür birçok ifade mevcut olsa da, ya hepsi çift ya da tek sayıda transpoze içerir. Böylece tüm permütasyonlar bu sayıya bağlı olarak çift ya da tek olarak sınıflandırılabilir. ⓘ

Bu sonuç bir işaret atayacak şekilde genişletilebilir, şöyle yazılabilir $\operatorname {sgn} \sigma$her permütasyon için. $\operatorname {sgn} \sigma =+1$ eğer $\sigma$ çifttir ve $\operatorname {sgn} \sigma =-1$ eğer $\sigma$ tektir. O zaman iki permütasyon için $\sigma$ ve $\pi$ ⓘ

$\operatorname {sgn} (\sigma \pi )=\operatorname {sgn} \sigma \cdot \operatorname {sgn} \pi .$ ⓘ

Bundan şu sonuç çıkar $\operatorname {sgn} \left(\sigma \sigma ^{-1}\right)=+1.$ ⓘ

Matris gösterimi

Bir permütasyon matrisi, her sütunda ve her satırda tam olarak bir girişi 1 olan ve diğer tüm girişleri 0 olan bir n × n matrisidir. Bir permütasyon matrisini {1, 2, ..., n}'nin bir permütasyonuna atamak için kullanılabilecek birkaç farklı kural vardır. Doğal yaklaşımlardan biri σ permütasyonuna şu matrisi atamaktır $M_{\sigma }$ (i, j) girişi i = σ(j) ise 1, aksi takdirde 0'dır. Bu konvansiyonun iki çekici özelliği vardır: birincisi, matrislerin ve permütasyonların çarpımı aynı sıradadır, yani, $M_{\sigma }M_{\pi }=M_{\sigma \circ \pi }$ tüm σ ve π permütasyonları için. İkinci olarak, eğer ${\bf {e}}_{i}$ standardı temsil eder $n\times 1$ sütun vektörü (ith girişi 1'e ve diğer tüm girişleri 0'a eşit olan vektör), o zaman $M_{\sigma }{\bf {e}}_{i}={\bf {e}}_{\sigma (i)}$. ⓘ

Örneğin, bu konvansiyonla, permütasyonla ilişkili matris $\sigma (1,2,3)=(2,1,3)$ o ${\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}$ ve permütasyon ile ilişkili matris $\pi (1,2,3)=(2,3,1)$ o ${\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}$. O halde permütasyonların bileşimi $(\sigma \circ \pi )(1,2,3)=\sigma (2,3,1)=(1,3,2)$'dir ve karşılık gelen matris çarpımı

$$M_{(2,1,3)}M_{(2,3,1)}={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}=M_{(1,3,2)}.$$

ⓘ

Permütasyon matrislerinin çarpımına karşılık gelen permütasyonların bileşimi. ⓘ

Literatürde, bir σ permütasyonunun aşağıdaki matrisle ilişkilendirildiği ters konvansiyonu bulmak da yaygındır $P_{\sigma }=(M_{\sigma })^{-1}=(M_{\sigma })^{T}$ (i, j) girişi j = σ(i) ise 1 ve aksi takdirde 0 olan. Bu konvansiyonda, permütasyon matrisleri permütasyonların tersi sırada çarpılır, yani, $P_{\sigma }P_{\pi }=P_{\pi \circ \sigma }$ Bu yazışmada, permütasyon matrisleri standart σ ve π indislerinin permütasyonu ile hareket eder. $1\times n$ satır vektörleri $({\bf {e}}_{i})^{T}$bir tane var $({\bf {e}}_{i})^{T}P_{\sigma }=({\bf {e}}_{\sigma (i)})^{T}$. ⓘ

Sağdaki Cayley tablosu 3 elemanlı permütasyonlar için bu matrisleri göstermektedir. ⓘ

Foata'nın geçiş lemması

Tek çizgi ile kanonik döngü gösterimi arasında bir ilişki vardır. Permütasyonu düşünün $(\,2\,)(\,3\,1\,)$, kanonik döngü gösteriminde, döngü parantezlerini silersek, permütasyonu elde ederiz $(2,3,1)$ tek satırlık gösterimde. Foata'nın geçiş lemması, bu yazışmanın doğasını n-permutasyon kümesi (kendisine) üzerinde bir bieksiyon olarak belirler. Richard P. Stanley bu bağıntıyı temel bağıntı olarak adlandırmaktadır. ⓘ

İzin verin $f$ parantez silici dönüşüm olsun. Tersi $q=f(p)$ biraz daha az sezgiseldir. Tek satırlık gösterimle başlayarak $q=q_{1}q_{2}\cdots q_{n}$ile başlarsa, kanonik çevrim gösterimindeki ilk çevrim $q_{1}$. Sonraki elemanlar aşağıdakilerden daha küçük olduğu sürece $q_{1}$aynı döngü içindeyiz. İkinci döngü en küçük indeksten başlar $j$ öyle ki $q_{j}>q_{1}$. Başka bir deyişle, $q_{j}$ solundaki diğer her şeyden daha büyüktür, bu nedenle soldan sağa maksimum olarak adlandırılır. Kanonik döngü gösterimindeki her döngü soldan sağa bir maksimum ile başlar. ⓘ

Örneğin, tek satırlık gösterimde $(3,1,2,5,4,8,9,7,6)$5, 3'ten büyük ilk elemandır, bu nedenle ilk döngü $(\,3\,1\,2\,)$. O halde 8, 5'ten büyük bir sonraki elemandır, bu nedenle ikinci döngü $(\,5\,4\,)$. 9, 8'den büyük olduğu için, $(\,8\,)$ kendi başına bir döngüdür. Son olarak, 9 sağında kalan tüm elemanlardan daha büyüktür, bu nedenle son döngü $(\,9\,7\,6\,)$. ⓘ

'nin altı permütasyonu $123$ ile kanonik döngü haritalarıdır:

$$123(1)(2)(3),132(1)(32),213(21)(3),231(312),312(321),321(2)(31).$$

ⓘ

İlk sonuç olarak, tam olarak k soldan sağa maksimuma sahip n-permutasyonların sayısı da birinci türden işaretsiz Stirling sayısına eşittir, $c(n,k)$. Ayrıca, Foata'nın eşlemesi k-zayıf çıkışlı bir n-permutasyonu k - 1 çıkışlı bir n-permutasyona götürür. Örneğin, (2)(31) = 321'in iki zayıf çıkışı vardır (indeks 1 ve 2'de), oysa f(321) = 231'in bir çıkışı vardır (indeks 1'de; yani 2'den 3'e). ⓘ

Tamamen sıralı kümelerin permütasyonları

Bazı uygulamalarda, permütasyon yapılan kümenin elemanları birbirleriyle karşılaştırılacaktır. Bu, herhangi iki elemanın karşılaştırılabilmesi için S kümesinin bir toplam sıraya sahip olmasını gerektirir. 1, 2, ..., n} kümesi olağan "≤" bağıntısı ile tam sıralıdır ve bu nedenle bu uygulamalarda en sık kullanılan kümedir, ancak genel olarak herhangi bir tam sıralı küme iş görür. Bu uygulamalarda, bir permütasyondaki konumlar hakkında konuşmak için bir permütasyonun sıralı düzenleme görünümüne ihtiyaç duyulur. ⓘ

S'nin toplam sıralamasıyla doğrudan ilişkili olan bir dizi özellik vardır. ⓘ

Çıkışlar, inişler, koşular ve çıkışlar

n'nin bir σ permütasyonunun yükselişi, bir sonraki değerin mevcut değerden daha büyük olduğu herhangi bir i < n konumudur. Yani, σ = σ₁σ₂...σn ise, σi < σ_i+1 ise i bir yükseliştir. ⓘ

Örneğin, 3452167 permütasyonunun (1, 2, 5 ve 6 konumlarında) çıkışları vardır. ⓘ

Benzer şekilde, bir iniş σi > σ_i+1 olan bir i < n konumudur, bu nedenle her i $1\leq i<n$ σ'nın ya bir çıkışı ya da bir inişidir. ⓘ

Bir permütasyonun artan dizisi, permütasyonun her iki ucunda da genişletilemeyen, boş olmayan, artan bitişik bir alt dizisidir; ardışık yükselişlerin maksimal dizisine karşılık gelir (ikincisi boş olabilir: iki ardışık iniş arasında hala 1 uzunluğunda bir yükselen dizi vardır). Buna karşın, bir permütasyonun artan bir alt dizisi bitişik olmak zorunda değildir: permütasyondan bazı konumlardaki değerlerin çıkarılmasıyla elde edilen artan bir eleman dizisidir. Örneğin, 2453167 permütasyonu 245, 3 ve 167 artan dizilerine sahipken, 2367 artan dizisine sahiptir. ⓘ

Eğer bir permütasyon k - 1 inişe sahipse, o zaman k tane artan dizinin birleşimi olmalıdır. ⓘ

n'nin k inişli permütasyonlarının sayısı (tanım gereği) Eulerian sayısıdır $\textstyle \left\langle {n \atop k}\right\rangle$Bu aynı zamanda n'nin k inişli permütasyonlarının sayısıdır. Ancak bazı yazarlar Eulerian sayısını şöyle tanımlar $\textstyle \left\langle {n \atop k}\right\rangle$ k - 1 inişe karşılık gelen k artan koşuya sahip permütasyonların sayısıdır. ⓘ

Bir σ₁σ₂...σn permütasyonunun aşımı, σj > _j olacak şekilde bir j indisidir. Eğer eşitsizlik katı değilse (yani, σ_j ≥ j), o zaman j zayıf bir aşım olarak adlandırılır. k dışsallığa sahip n-permutasyon sayısı, k inişe sahip n-permutasyon sayısı ile çakışır. ⓘ

İnversiyonlar

15 bulmacasında amaç, kareleri artan sırada elde etmektir. Tek sayıda tersi olan başlangıç konumlarını çözmek imkansızdır. ⓘ

Bir σ permütasyonunun ters çevrilmesi, bir permütasyonun girdilerinin ters sırada olduğu bir pozisyon çiftidir (i, j): $i<j$ ve $\sigma _{i}>\sigma _{j}$. Yani bir iniş sadece iki bitişik konumdaki bir ters çevirmedir. Örneğin, σ = 23154 permütasyonunun üç tersi vardır: (2, 1), (3, 1) ve (5, 4) giriş çiftleri için (1, 3), (2, 3) ve (4, 5). ⓘ

Bazen bir ters çevirme, sırası tersine çevrilmiş değer çifti (σi,σ_j) olarak tanımlanır; bu ters çevirme sayısı için bir fark yaratmaz ve bu çift (ters çevrilmiş) aynı zamanda σ-1 ters permütasyonu için yukarıdaki anlamda bir ters çevirmedir. Ters çevirme sayısı bir permütasyonun girdilerinin ne derece sıra dışı olduğunu gösteren önemli bir ölçüdür; σ ve σ-1 için aynıdır. K tersi olan bir permütasyonu sıraya sokmak (yani özdeşlik permütasyonuna dönüştürmek), bitişik transpozeleri art arda uygulayarak (sağa çarpma) her zaman mümkündür ve bu tür k işlem dizisi gerektirir. Dahası, bitişik transpozeler için herhangi bir makul seçim işe yarayacaktır: her adımda i ve i + 1'in bir transpozesini seçmek yeterlidir; burada i, o ana kadar değiştirilmiş permütasyonun bir inişidir (böylece transpozisyon, başka inişler yaratabilse de bu belirli inişi ortadan kaldıracaktır). Bunun nedeni, böyle bir transpozisyonun uygulanmasının ters çevirme sayısını 1 azaltmasıdır; bu sayı sıfır olmadığı sürece permütasyon özdeş değildir, dolayısıyla en az bir inişi vardır. Bubble sort ve insertion sort, bir diziyi sıraya koymak için bu prosedürün özel örnekleri olarak yorumlanabilir. Bu arada bu prosedür, herhangi bir σ permütasyonunun bitişik transpozelerin bir çarpımı olarak yazılabileceğini kanıtlar; bunun için σ'yı özdeşliğe dönüştüren bu tür transpozelerin herhangi bir dizisini tersine çevirmek yeterlidir. Aslında, σ'yı özdeşliğe dönüştürecek tüm bitişik transpoze dizilerini sıralayarak, (tersine çevirmeden sonra) σ'yı bitişik transpozelerin bir çarpımı olarak yazan minimum uzunluktaki tüm ifadelerin tam bir listesini elde ederiz. ⓘ

n'nin k tersi ile permütasyonlarının sayısı bir Mahonian sayısı ile ifade edilir, bu sayı çarpımın açılımındaki Xk katsayısıdır

$$\prod _{m=1}^{n}\sum _{i=0}^{m-1}X^{i}=1\left(1+X\right)\left(1+X+X^{2}\right)\cdots \left(1+X+X^{2}+\cdots +X^{n-1}\right),$$

(X yerine q konulduğunda) q-faktöriyel [n]_q! olarak da bilinir. . Çarpımın açılımı Necklace'de (kombinatorik) görünür. ⓘ

İzin verin $\sigma \in S_{n},i,j\in \{1,2,\dots ,n\}$ öyle ki $i<j$ ve $\sigma (i)>\sigma (j)$. Bu durumda, ters çevirmenin ağırlığına $(i,j)$ o $\sigma (i)-\sigma (j)$. Kobayashi (2011) numaralandırma formülünü kanıtlamıştır

$$\sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}$$

ⓘ

nerede $\leq$ simetrik gruplarda Bruhat mertebesini gösterir. Bu dereceli kısmi düzen genellikle Coxeter grupları bağlamında ortaya çıkar. ⓘ

Hesaplamada permütasyonlar

Numaralandırma permütasyonları

Sayı ile bir permütasyonun sıralı bir düzenleme (dizi) olarak temsili arasında dönüşüm yapmak için uygun yöntemler verilmesi koşuluyla, n şeyin permütasyonlarını temsil etmenin bir yolu, 0 ≤ N < n! olan bir N tamsayısıdır. Bu, keyfi permütasyonların en kompakt gösterimini verir ve hesaplamada, N bir makine sözcüğünde tutulabilecek kadar küçük olduğunda özellikle caziptir; 32 bitlik sözcükler için bu, n ≤ 12 ve 64 bitlik sözcükler için bu, n ≤ 20 anlamına gelir. Dönüşüm, dn, dn-1, ..., d₂, d₁ sayı dizilerinin ara formu aracılığıyla yapılabilir; burada di, i'den küçük negatif olmayan bir tamsayıdır (d₁ her zaman 0 olduğu için atlanabilir, ancak varlığı daha sonra permütasyona dönüşümün tanımlanmasını kolaylaştırır). O halde ilk adım, N'yi basitçe faktöriyel sayı sisteminde ifade etmektir; bu, n'den küçük sayılar için ardışık basamakların tabanlarının (yer değerleri veya çarpım faktörleri) (n - 1)!, (n - 2)!, ..., 2!, 1! olduğu belirli bir karışık radiks gösterimidir. İkinci adım bu diziyi bir Lehmer kodu veya (neredeyse eşdeğer olarak) bir ters çevirme tablosu olarak yorumlar. ⓘ

için + Rothe diyagramı $\sigma =(6,3,8,1,4,9,7,2,5)$ ⓘ
σi i	1	2	3	4	5	6	7	8	9	Lehmer kodu
1	×	×	×	×	×	•				d9 = 5
2	×	×	•							d8 = 2
3	×	×		×	×		×	•		d7 = 5
4	•									d6 = 0
5		×		•						d5 = 1
6		×			×		×		•	d4 = 3
7		×			×		•			d3 = 2
8		•								d2 = 0
9					•					d1 = 0
İnversiyon tablosu	3	6	1	2	4	0	2	0	0

Bir σ permütasyonu için Lehmer kodunda, dn sayısı ilk terim σ₁ için yapılan seçimi, dn-1 sayısı ise ikinci terim için yapılan seçimi temsil eder σ₂ kümenin kalan n - 1 elemanı arasında ve bu şekilde devam eder. Daha doğrusu, her dn+1-i, σi teriminden kesinlikle daha az kalan eleman sayısını verir. Bu kalan elemanlar daha sonra σj terimi olarak ortaya çıkacağından, dn+1-i rakamı i'yi daha küçük indeks olarak içeren ters çevirmeleri (i,j) sayar (i < j ve σi > σj olan j değerlerinin sayısı). σ için ters çevirme tablosu oldukça benzerdir, ancak burada dn+1-k, ters çevrilmiş sırada görünen iki değerden daha küçük olanı olarak k = σj'nin meydana geldiği ters çevirmelerin (i,j) sayısını sayar. Her iki kodlama da (i,σi) noktalarının permütasyonun girişlerini ve (i,σj) çarpı işaretinin de ters çevirmeyi (i,j) işaret ettiği n'ye n Rothe diyagramı (Heinrich August Rothe'nin adıyla anılır) ile görselleştirilebilir; ters çevirmelerin tanımına göre, hem sütunundaki (j,σj) noktasından önce hem de satırındaki (i,σi) noktasından önce gelen herhangi bir karede çarpı işareti görünür. Lehmer kodu ardışık satırlardaki çarpıların sayısını listelerken, ters çevirme tablosu ardışık sütunlardaki çarpıların sayısını listeler; bu sadece ters permütasyon için Lehmer kodudur ve bunun tersi de geçerlidir. ⓘ

Bir Lehmer kodunu dn, dn-1, ..., d₂, d₁ sıralı bir S kümesinin permütasyonuna etkili bir şekilde dönüştürmek için, S'nin artan sıradaki elemanlarının bir listesiyle başlanabilir ve 1'den n'ye kadar artan i için σi listede dn+1-i diğerlerinden önce gelen elemana ayarlanır ve bu eleman listeden çıkarılır. Bir dn, dn-1, ..., d₂, d₁ ters çevirme tablosunu karşılık gelen permütasyona dönüştürmek için, S'nin elemanlarını başlangıçta boş olan bir diziye büyükten küçüğe doğru yerleştirirken d₁'den dn'ye kadar sayılar arasında dolaşılabilir; ters çevirme tablosundaki d sayısını kullanan adımda, S'nin elemanı, d elemanından önce geldiği noktada diziye yerleştirilir. Alternatif olarak, ters çevirme tablosundaki sayılar ve S'nin elemanları ters sırada işlenebilir, n boş yuvadan oluşan bir satırla başlanabilir ve her adımda S'nin elemanı d boş yuvadan önce gelen boş yuvaya yerleştirilebilir. ⓘ

Ardışık doğal sayıları faktöriyel sayı sistemine dönüştürmek, bu dizileri leksikografik sırada üretir (herhangi bir karışık radiks sayı sisteminde olduğu gibi) ve Lehmer kod yorumunun kullanılması koşuluyla bunları permütasyonlara dönüştürmek leksikografik sıralamayı korur (ters çevirme tabloları kullanıldığında, permütasyonları ilk girişlerinin değerine göre değil, girişlerinin 1 yerine göre karşılaştırarak başlanan farklı bir sıralama elde edilir). Faktöriyel sayı sistemi gösterimindeki sayıların toplamı permütasyonun ters çevirme sayısını verir ve bu toplamın paritesi permütasyonun imzasını verir. Ayrıca, ters çevirme tablosundaki sıfırların konumları permütasyonun soldan sağa maksimum değerlerini verirken (örnekte 6, 8, 9), Lehmer kodundaki sıfırların konumları sağdan sola minimum değerlerin konumlarıdır (örnekte 1, 2, 5 değerlerinin 4, 8, 9 konumları); bu, tüm permütasyonlar arasında bu tür ekstremumların dağılımının hesaplanmasına olanak tanır. Lehmer kodu dn, dn-1, ..., d₂, d₁ olan bir permütasyon, ancak ve ancak di ≥ d_i+1 ise bir n - i çıkışına sahiptir. ⓘ

Permütasyon üretmek için algoritmalar

Hesaplamada, verilen bir değerler dizisinin permütasyonlarını üretmek gerekebilir. Bunu yapmak için en iyi uyarlanmış yöntemler, rastgele seçilmiş bazı permütasyonların mı yoksa tüm permütasyonların mı istendiğine ve ikinci durumda belirli bir sıralamanın gerekli olup olmadığına bağlıdır. Bir başka soru da, verilen dizideki girdiler arasındaki olası eşitliğin dikkate alınıp alınmayacağıdır; eğer öyleyse, kişi dizinin yalnızca farklı çok kümeli permütasyonlarını üretmelidir. ⓘ

n'nin permütasyonlarını üretmenin bariz bir yolu Lehmer kodu için değerler üretmek (muhtemelen n'ye kadar tamsayıların faktöriyel sayı sistemi gösterimini kullanarak!) ve bunları karşılık gelen permütasyonlara dönüştürmektir. Bununla birlikte, ikinci adım, basit olmasına rağmen, verimli bir şekilde uygulanması zordur, çünkü her biri keyfi bir konumda bir diziden seçme ve ondan silme işlemlerinin n işlemini gerektirir; dizinin bir dizi veya bağlantılı bir liste olarak açık temsillerinden her ikisi de (farklı nedenlerle) dönüşümü gerçekleştirmek için yaklaşık n² / 4 işlem gerektirir. Muhtemelen oldukça küçük olan n ile (özellikle tüm permütasyonların üretilmesi gerekiyorsa) bu çok fazla bir sorun değildir, ancak hem rastgele hem de sistematik üretim için önemli ölçüde daha iyi yapan basit alternatifler olduğu ortaya çıkmaktadır. Bu nedenle, Lehmer kodundan permütasyona dönüşümü O(n log n) zamanda gerçekleştirmeyi sağlayacak özel bir veri yapısı kullanmak kesinlikle mümkün olsa da yararlı görünmemektedir. ⓘ

Rastgele permütasyon üretimi

Belirli bir n değer dizisinin rastgele permütasyonlarını üretmek için, diziye rastgele seçilmiş bir n permütasyonu uygulamak ya da dizinin farklı (çoklu küme) permütasyonları kümesinden rastgele bir eleman seçmek fark etmez. Bunun nedeni, tekrarlanan değerler durumunda, aynı permütasyonlu diziyle sonuçlanan n'nin birçok farklı permütasyonu olabilse de, bu tür permütasyonların sayısının her olası sonuç için aynı olmasıdır. N sayısının büyümesi nedeniyle büyük n için olanaksız hale gelen sistematik üretimin aksine, rastgele üretim için n'nin küçük olacağını varsaymak için hiçbir neden yoktur. ⓘ

Rastgele bir permütasyon üretmenin temel fikri, 0 ≤ di < i (d₁ her zaman sıfır olduğundan ihmal edilebilir) koşulunu sağlayan d₁,d₂,...,dn tamsayılarının n! dizilerinden birini rastgele üretmek ve bunu bijective bir yazışma yoluyla bir permütasyona dönüştürmektir. İkinci yazışma için (ters) diziyi bir Lehmer kodu olarak yorumlayabiliriz ve bu ilk olarak 1938'de Ronald Fisher ve Frank Yates tarafından yayınlanan bir üretim yöntemi verir. O zamanlar bilgisayar uygulaması bir sorun olmasa da, bu yöntem Lehmer kodundan permütasyona verimli bir şekilde dönüştürmek için yukarıda taslağı çizilen zorluktan muzdariptir. Bu durum farklı bir bijektif karşılık kullanılarak giderilebilir: dizinin kalan i elemanı arasından bir eleman seçmek için di kullanıldıktan sonra (i'nin azalan değerleri için), elemanı çıkarmak ve diğer elemanları bir sıra aşağı kaydırarak diziyi sıkıştırmak yerine, eleman kalan son elemanla değiştirilir. Böylece seçim için kalan elemanlar, orijinal dizide olduğu gibi aynı sırayla oluşmasalar bile, zamanın her noktasında ardışık bir aralık oluştururlar. Tamsayılar dizisinden permütasyonlara eşleme biraz karmaşıktır, ancak her permütasyonun doğrudan bir tümevarımla tam olarak tek bir şekilde üretildiği görülebilir. Seçilen eleman kalan son eleman olduğunda, takas işlemi ihmal edilebilir. Bu durum, koşulun test edilmesini gerektirecek kadar sık meydana gelmez, ancak tüm permütasyonların üretilebilmesini garanti altına almak için son eleman seçim adayları arasında yer almalıdır. ⓘ

a[0], a[1], ..., a[n - 1]'in rastgele permütasyonunu oluşturmak için ortaya çıkan algoritma sözde kod olarak aşağıdaki gibi tanımlanabilir:

for i from n downto 2 do
    di ← { 0, ..., i - 1 } 'in rastgele elemanı
    a[di] ve a[i - 1]'i değiştirin ⓘ

Bu, a[i] = i dizisinin aşağıdaki gibi başlatılmasıyla birleştirilebilir ⓘ

i için 0'dan n-1'e kadar do
    di+1 ← {0, ..., i } 'nin rastgele elemanı
    a[i] ← a[di+1]
    a[di+1] ← i ⓘ

Eğer d_i+1 = i ise, ilk atama başlatılmamış bir değeri kopyalar, ancak ikincisi bunun üzerine doğru i değerini yazar. ⓘ

Ancak Fisher-Yates bir permütasyon oluşturmak için en hızlı algoritma değildir, çünkü Fisher-Yates esasen sıralı bir algoritmadır ve "böl ve yönet" prosedürleri aynı sonuca paralel olarak ulaşabilir. ⓘ

Leksikografik sırayla üretim

Verilen bir dizinin tüm permütasyonlarını sistematik olarak üretmenin birçok yolu vardır. Klasik, basit ve esnek bir algoritma, eğer varsa, leksikografik sıralamada bir sonraki permütasyonu bulmaya dayanır. Tekrarlanan değerleri işleyebilir, bu durumda her farklı çoklu küme permütasyonunu bir kez üretir. Sıradan permütasyonlar için bile Lehmer kodu için leksikografik sırada değerler üretmekten (muhtemelen faktöriyel sayı sistemini kullanarak) ve bunları permütasyonlara dönüştürmekten önemli ölçüde daha verimlidir. Diziyi (zayıf) artan sırada sıralayarak başlar (bu da leksikografik olarak minimum permütasyonunu verir) ve daha sonra bir tane bulunduğu sürece bir sonraki permütasyona ilerlemeyi tekrarlar. Bu yöntem 14. yüzyıl Hindistan'ında Narayana Pandita'ya kadar uzanır ve sık sık yeniden keşfedilmiştir. ⓘ

Aşağıdaki algoritma, verilen bir permütasyondan sonra leksikografik olarak bir sonraki permütasyonu üretir. Verilen permütasyonu yerinde değiştirir. ⓘ

1. a[k] < a[k + 1] olacak şekilde en büyük k indisini bulun. Eğer böyle bir indis yoksa, permütasyon son permütasyondur.
2. a[k] < a[l] olacak şekilde k'dan büyük en büyük l indeksini bulun.
3. a[k] değerini a[l] değeri ile değiştirin.
4. a[k + 1]'den son eleman a[n]'ye kadar olan diziyi tersine çevirin.

Örneğin, [1, 2, 3, 4] dizisi (artan sırada) ve indeksin sıfır tabanlı olduğu göz önüne alındığında, adımlar aşağıdaki gibidir:

1. Dizin k = 2, çünkü 3, a[k + 1]'den hala küçük olan en büyük dizin olma koşulunu karşılayan bir dizine yerleştirilir, bu da 4'tür.
2. İndeks l = 3, çünkü a[k] < a[l] koşulunu sağlamak için dizide 3'ten büyük olan tek değer 4'tür.
3. a[2] ve a[3] değerleri değiştirilerek yeni dizi [1, 2, 4, 3] oluşturulur.
4. a[2] k-indeksinden sonra son elemana kadar olan dizi tersine çevrilir. Bu indeksten (3) sonra yalnızca bir değer bulunduğundan, dizi bu durumda değişmeden kalır. Böylece başlangıç durumunun leksikografik ardılı permütasyona uğrar: [1, 2, 4, 3].

Bu algoritmanın ardından, bir sonraki leksikografik permütasyon [1, 3, 2, 4] olacaktır ve 24. permütasyon [4, 3, 2, 1] olacaktır, bu noktada a[k] < a[k + 1] mevcut değildir, bu da bunun son permütasyon olduğunu gösterir. ⓘ

Bu yöntem permütasyon başına yaklaşık 3 karşılaştırma ve 1,5 takas kullanır ve ilk sıralamayı saymazsak tüm dizi boyunca amorti edilir. ⓘ

En az değişiklikle üretim

Yukarıdaki algoritmaya bir alternatif olan Steinhaus-Johnson-Trotter algoritması, çıktısındaki herhangi iki ardışık permütasyonun iki bitişik değeri değiştirerek farklı olması özelliğine sahip belirli bir dizinin tüm permütasyonları üzerinde bir sıralama oluşturur. Permütasyonlar üzerindeki bu sıralama, 17. yüzyıl İngiliz zangoçları tarafından biliniyordu ve aralarında "düz değişiklikler" olarak biliniyordu. Bu yöntemin bir avantajı, bir permütasyondan diğerine küçük miktarda değişimin, yöntemin permütasyon başına sabit zamanda uygulanmasına izin vermesidir. Aynı yöntem, diğer tüm çıktı permütasyonlarını atlayarak yine permütasyon başına sabit zamanda çift permütasyonların alt kümesini de kolayca oluşturabilir. ⓘ

Steinhaus-Johnson-Trotter'a bir alternatif, Robert Sedgewick tarafından 1977'de uygulamalarda permütasyon üretmenin en hızlı algoritması olduğu söylenen Heap algoritmasıdır. ⓘ

Aşağıdaki şekil, uzunluktaki tüm permütasyonların üretilmesi için yukarıda bahsedilen üç algoritmanın çıktısını göstermektedir $n=4$ve literatürde tanımlanan altı ek algoritma. ⓘ

Uzunluktaki tüm permütasyonların sıralanması $n=4$ farklı algoritmalar tarafından üretilmiştir. Permütasyonlar renk kodludur, burada 1, 2, 3, 4. ⓘ

1. Leksikografik sıralama;
2. Steinhaus-Johnson-Trotter algoritması;
3. Heap algoritması;
4. Ehrlich'in yıldız transpozisyon algoritması: her adımda, permütasyonun ilk girişi daha sonraki bir girişle değiştirilir;
5. Zaks'ın önek tersine çevirme algoritması: her adımda, bir sonraki permütasyonu elde etmek için mevcut permütasyonun bir öneki tersine çevrilir;
6. Sawada-Williams algoritması: her permütasyon bir öncekinden ya bir pozisyonluk döngüsel sola kaydırma ya da ilk iki girdinin değişimi ile farklılık gösterir;
7. Corbett'in algoritması: her permütasyon bir öncekinden bazı öneklerin döngüsel olarak bir pozisyon sola kaydırılmasıyla farklılık gösterir;
8. Tek izli sıralama: her sütun diğer sütunların döngüsel olarak kaydırılmasıdır;
9. Tek izli Gri kod: her sütun diğer sütunların döngüsel kaydırmasıdır, ayrıca herhangi iki ardışık permütasyon sadece bir veya iki transpozisyonda farklılık gösterir. ⓘ

Meandrik permütasyonlar

Meandrik sistemler, alternatif permütasyonların özel bir alt kümesi olan meandrik permütasyonlara yol açar. 1, 2, ..., 2n} kümesinin alternatif bir permütasyonu, döngüsel gösterimdeki rakamların tek ve çift tam sayılar arasında dönüşümlü olarak oluştuğu döngüsel bir permütasyondur (sabit noktaları yoktur). Meandrik permütasyonlar RNA ikincil yapısının analizinde kullanışlıdır. Tüm alternatif permütasyonlar ortalama permütasyon değildir. Heap algoritmasının bir modifikasyonu, tüm (2n)! permütasyonları üretmeden n mertebesindeki (yani 2n uzunluğundaki) tüm alternatif permütasyonları üretmek için kullanılmıştır. Bu alternatif permütasyonların üretilmesi, meandrik olup olmadıklarını belirlemek için analiz edilmeden önce gereklidir. ⓘ

Algoritma özyinelemelidir. Aşağıdaki tablo prosedürdeki bir adımı göstermektedir. Bir önceki adımda, 5 uzunluğundaki tüm alternatif permütasyonlar üretilmiştir. Bunların her birinin üç kopyasının sağ ucuna bir "6" eklenir ve ardından bu son girişi ve çift konumdaki bir önceki girişi içeren farklı bir aktarım uygulanır (özdeşlik dahil; yani aktarım yok). ⓘ

Önceki kümeler	Rakamların yer değiştirmesi	Alternatif permütasyonlar ⓘ
1-2-3-4-5-6		1-2-3-4-5-6
	4, 6	1-2-3-6-5-4
	2, 6	1-6-3-4-5-2
1-2-5-4-3-6		1-2-5-4-3-6
	4, 6	1-2-5-6-3-4
	2, 6	1-6-5-4-3-2
1-4-3-2-5-6		1-4-3-2-5-6
	2, 6	1-4-3-6-5-2
	4, 6	1-6-3-2-5-4
1-4-5-2-3-6		1-4-5-2-3-6
	2, 6	1-4-5-6-3-2
	4, 6	1-6-5-2-3-4

Uygulamalar

Permütasyonlar, turbo kodları gibi hata tespit ve düzeltme algoritmalarının interleaver bileşeninde kullanılır, örneğin 3GPP Uzun Vadeli Evrim mobil telekomünikasyon standardı bu fikirleri kullanır (bkz. 3GPP teknik spesifikasyonu 36.212). Bu tür uygulamalar, arzu edilen belirli özellikleri karşılayan permütasyonların hızlı bir şekilde üretilmesi sorununu ortaya çıkarmaktadır. Yöntemlerden biri permütasyon polinomlarına dayanmaktadır. Ayrıca Unique Permutation Hashing'de optimal hashing için bir temel olarak kullanılır. ⓘ

Permütasyonların hesaplanması

Permütasyonun kombinasyondan farkı, sıralamanın önemli olmasıdır. ⓘ

Tekrarsız

Tekrarsız permütasyonda her eleman sadece bir kez kullanılabilir. ⓘ

n elemanlı bir kümeden seçilen r elemanlı "tekrarsız" permütasyonların toplamı (n ≥ r olmak şartıyla) aşağıdaki formülle ifade edilir: $P(n,r)={n \choose {n-r}}={\frac {n!}{(n-r)!}}$ ⓘ

Örnek ⓘ

5 atın katıldığı bir yarışta seçilen 3 yarış atının "sırasıyla" birinci, ikinci ve üçüncü gelme olasılığı hesaplanırken bu formül kullanılabilir. Bir atın aynı yarışta iki kez birinci gelmesi mümkün değildir. ⓘ

$P(5,3)={5 \choose {5-3}}={\frac {5!}{(5-3)!}}=60$ ⓘ

Seçilen sıralamanın doğru çıkma olasılığı 1/60'tır. ⓘ

Tekrarlı

"Tekrarlı" permütasyonlar ise n^r formülü ile ifade edilir. ⓘ

Bu formül ile örneğin 3 haneli rakamsal bir çanta şifresinin permütasyonları (seçilebilecek toplam şifre adedi) hesaplanabilir. Her çemberde 0-9 arası 10 rakam olduğu için toplam şifre sayısı 10 x 10 x 10 = 10³ = 1000'dir. Olası şifrelerin oluşturduğu seri 000, 001, 002 ... 997, 998, 999 şeklindedir. Yani rastgele denenen bir şifrenin çanta kilidini açma olasılığı 1/1000'dir. ⓘ

Tekrarlı Permütasyon n tane farklı elemanın n¹ tanesi aynı n² tanesi aynı , ... , n™ tanesi aynı iken

 n¹ + n²+ ...+ n™ =n tane elemanın farklı sıralanışlarının sayısı ⓘ 

                  _______n!______
                    n¹ ! .n² !....n™ ! 
  kadardır . ⓘ

Bilgisayarla hesaplama

Örnekler

C programlama dili

C kodunda permütasyon şu şekilde hesaplanabilir:

	long permutasyon (const int n, const int r) {
	 int i;
	 long sonuc = 1;
	 for (i = 0; i <= r; i++)
	 {
	 	 sonuc = sonuc*(n - i);
	 }
	 return sonuc;
	} <span title="Kaynak: Türkçe Vikipedi, Bölüm &quot;C programlama dili&quot;" class="plainlinks">[https://tr.wikipedia.org/wiki/Permütasyon#C_programlama_dili <span style="color:#dddddd">ⓘ</span>]</span>

PHP programlama dili

PHP kodunda şu şekilde bulunabilir:

function permutasyon($n,$r){
$sonuc = 1;
for((($i = ($n - $r) + 1)); $i <= $n; $i++){
$sonuc = $i*$sonuc;	
}
return $sonuc;
}
 permutasyon(7, 2); // 42 <span title="Kaynak: Türkçe Vikipedi, Bölüm &quot;PHP programlama dili&quot;" class="plainlinks">[https://tr.wikipedia.org/wiki/Permütasyon#PHP_programlama_dili <span style="color:#dddddd">ⓘ</span>]</span>

Python programlama dili

def permutasyon(n, r):
    sonuc = 1
    for i in range(r):
        sonuc = sonuc * (n - i)
    return sonuc <span title="Kaynak: Türkçe Vikipedi, Bölüm &quot;PHP programlama dili&quot;" class="plainlinks">[https://tr.wikipedia.org/wiki/Permütasyon#PHP_programlama_dili <span style="color:#dddddd">ⓘ</span>]</span>

ⓘ