Permutasi Stirling

Dalam kombinatorik, permutasi Stirling orde k adalah permutasi yang mencakup multiset 1, 1, 2, 2, ..., k, k (yang terdiri dari dua salinan dari setiap nilai yang berkisar dari 1 hingga k). Permutasi ini memiliki sifat tambahan: untuk setiap nilai i yang muncul di dalam permutasi, jumlah di antara dua salinan i lebih besar daripada i. Sebagai contoh, untuk 15 permutasi Stirling orde tiga,

1,1,2,2,3,3;   1,2,2,1,3,3;   2,2,1,1,3,3;
1,1,2,3,3,2;   1,2,2,3,3,1;   2,2,1,3,3,1;
1,1,3,3,2,2;   1,2,3,3,2,1;   2,2,3,3,1,1;
1,3,3,1,2,2;   1,3,3,2,2,1;   2,3,3,2,1,1;
3,3,1,1,2,2;   3,3,1,2,2,1;   3,3,2,2,1,1.

Jumlah permutasi Stirling orde k dirumuskan menggunakan faktorial berganda (2k − 1)!!. Permutasi Stirling diperkenalkan oleh (Gessel & Stanley 1978) yang memperlihatkan bilangan tertentu (yakni jumlah permutasi Stirling dengan jumlah menurun yang tetap) adalah non-negatif. Nama permutasi itu dipilih karena ada kaitan dengan polinomial yang didefinisikan dari bilangan Stirling, yang nyatanya bilangan itu dinamai dari James Stirling, seorang matematikawan asal Skotlandia pada abad ke-18.[1]

Konstruksi permutasi Stirling dari tour Euler suatu pohon bidang dengan sisinya dilabeli berdasarkan urutan konstruksi

Permutasi Stirling dapat digunakan untuk menggambarkan barisan, yang dapat mengkonstruksi pohon bidang berakar dengan k sisi. Caranya dengan menambahkan simpul daun satu per satu ke pohon tersebut. Karena apabila sisi pohon dinomorkan berdasarkan urutan saat dimasukkan, maka barisan bilangan di dalam tour Euler suatu pohon (yang dibentuk dengan menggandakan sisi pohon dan melintasi tsetiap simpul anak yang diurutkan dari kiri ke kanan) merupakan permutasi Stirling. Sebaliknya, setiap permutasi Stirling menggambarkan suatu barisan konstruksi pohon, dan sisi selanjutnya yang dekat dengan pada simpul akar dari suatu sisi dilabeli i adalah sisi yang pasangan nilai yang serupa mengitari pasangan i nilai dalam permutasi.[2]

Permutasi Stirling sudah digeneralisasi ke permutasi suatu multiset lebih dari dua salinan setiap nilai.[3] Beberapa penelitian juga mengkaji jumlah permutasi Stirling yang berupaya menghindari pola-pola tertentu.[4]

Referensi

  1. ^ Gessel, Ira; Stanley, Richard P. (1978), "Stirling polynomials", Journal of Combinatorial Theory, Series A, 24 (1): 24–33, doi:10.1016/0097-3165(78)90042-0, MR 0462961.
  2. ^ Janson, Svante (2008), "Plane recursive trees, Stirling permutations and an urn model", Fifth Colloquium on Mathematics and Computer Science, Discrete Math. Theor. Comput. Sci. Proc., AI, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, hlm. 541–547, arXiv:0803.1129, Bibcode:2008arXiv0803.1129J, MR 2508813.
  3. ^ Klingsberg, Paul; Schmalzried, Cynthia (1990), "A family of constructive bijections involving Stirling permutations", Proceedings of the Twenty-first Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Florida, 1990), Congressus Numerantium, vol. 78, hlm. 11–15, MR 1140465.
  4. ^ Kuba, Markus; Panholzer, Alois (2012), "Enumeration formulæ for pattern restricted Stirling permutations", Discrete Mathematics, 312 (21): 3179–3194, doi:10.1016/j.disc.2012.07.011, MR 2957938.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.
Kembali kehalaman sebelumnya