Permutasi dan Kombinasi

Permutasi menghitung susunan objek yang berurutan dan kombinasi menghitung pemilihan yang tidak berurutan; bersama-sama keduanya membentuk inti dasar enumerasi.

Definition

Permutasi suatu himpunan adalah susunan berurutan dari elemen-elemennya (atau bijeksi dari himpunan itu sendiri); kombinasi adalah pemilihan tidak berurutan dari sejumlah elemen tertentu dari suatu himpunan.

Scope

Topik ini mengembangkan penghitungan susunan (dengan dan tanpa pengulangan), pemilihan, dan penyempurnaannya, termasuk derangement, permutasi siklik, dan permutasi dengan posisi terbatas. Ini memperkenalkan statistik permutasi seperti penurunan (descents), inversi, dan struktur siklus, yang menghubungkan penghitungan dasar dengan teori modern yang lebih kaya dari grup simetris.

Core questions

• Berapa banyak cara n objek berbeda dapat diurutkan, dan berapa banyak cara r dari objek tersebut dapat diurutkan?
• Bagaimana pengulangan dan ketidakbedaan mengubah jumlah susunan?
• Apa itu derangement, dan seberapa sering permutasi acak tidak memperbaiki elemen apa pun?
• Statistik pada permutasi mana yang terdistribusi secara ekuivalen?

Key concepts

• Faktorial dan faktorial menurun
• Susunan dengan dan tanpa pengulangan
• Derangement
• Permutasi siklik
• Inversi dan penurunan
• Bilangan Stirling

Key theories

Dekomposisi siklus permutasi

Setiap permutasi terfaktor secara unik menjadi siklus-siklus yang terpisah; penghitungan permutasi berdasarkan jenis siklusnya diatur oleh bilangan Stirling jenis pertama dan mendasari struktur grup simetris.

Enumerasi derangement

Jumlah permutasi tanpa titik tetap, yang diturunkan melalui inklusi-eksklusi, mendekati n!/e, memberikan hasil klasik bahwa sekitar 37% permutasi adalah derangement.

Clinical relevance

Penghitungan permutasi dan kombinasi muncul dalam probabilitas (hasil yang kemungkinan sama), algoritma pengurutan dan pengacakan, desain eksperimen, dan ruang kunci kriptografi, di mana ukuran ruang susunan menentukan kesulitan dan keamanan.

History

Kombinatorika permutasi disistematisasi oleh karya MacMahon pada awal abad ke-20 tentang analisis kombinatorik dan kemudian diperdalam melalui teori modern statistik permutasi.

Key figures

• Percy MacMahon
• Richard P. Stanley

Seminal works

• stanley2011

Frequently asked questions

Berapa banyak permutasi yang dimiliki suatu himpunan dengan n elemen?

Himpunan tersebut memiliki n! permutasi, yaitu hasil kali semua bilangan bulat positif hingga n, karena setiap n posisi diisi oleh elemen berbeda yang tersisa.

Apa itu derangement?

Derangement adalah permutasi di mana tidak ada elemen yang tetap pada posisi aslinya, seperti pengacakan di mana tidak ada surat yang kembali ke amplopnya sendiri.