Kullanıcı:Özgürcübey/deneme tahtası
__LEAD_SECTION__[değiştir | kaynağı değiştir]
Kombinatoryal matematikte, n sembol üzerindeki süper permütasyon n sembolün her permütasyonunu bir alt dize olarak içeren bir dizedir. Önemsiz süper permütasyonlar basitçe her permütasyonun bir araya getirilmesinden oluşabilirken, üst üste binmeye izin verildiği için süper permütasyonlar daha kısa da olabilir (önemsiz n = 1 durumu hariç). Örneğin, n = 2 durumunda, süper permütasyon (1221) tüm olası permütasyonları (12 ve 21) içerir, ancak daha kısa dizi (121) aynı zamanda her iki permütasyonu da içerir.
1 ≤ n ≤ 5 için n sembol üzerindeki en küçük süper permütasyonun uzunluğunun 1 olduğu gösterilmiştir! + 2! + … + n ! (OEIS'de A180632 dizisi). İlk dört en küçük süper permütasyon, 1, 3, 9 ve 33 uzunluklarına sahiptir ve 1, 121, 123121321 ve 123412314231243121342132413214321 dizilerini oluşturur. Bununla birlikte, n=5 için uzunluğu 153 olan birkaç en küçük süper permütasyon vardır. Böyle bir süperpermütasyon aşağıda gösterilmektedir, aynı uzunlukta bir diğeri ise dizenin ikinci yarısındaki (kalın 2'den sonra) dörtlü ve beşlilerin tümü değiştirilerek elde edilebilir: [1]
12345123 41523412 53412354 12314523 14253142 35142315 42312453 12435124 31524312 5431 2 134 52134251 34215342 13542132 45132415 32413524 13254132 14532143 52143251 432154321
n > 5 durumları için, en küçük süperpermütasyon henüz kanıtlanmadı ve bunları bulmak için bir model henüz bulunamadı, ancak bunlar için alt ve üst sınırlar bulundu.
- ^ Johnston, Nathaniel (July 28, 2013). "Non-uniqueness of minimal superpermutations". Discrete Mathematics. 313 (14): 1553–1557. arXiv:1303.4150 $2. doi:10.1016/j.disc.2013.03.024. Erişim tarihi: March 16, 2014.Johnston, Nathaniel (July 28, 2013). "Non-uniqueness of minimal superpermutations". Discrete Mathematics. 313 (14): 1553–1557. arXiv:1303.4150. Bibcode:2013arXiv1303.4150J. doi:10.1016/j.disc.2013.03.024. S2CID 12018639. Zbl 1368.05004. Retrieved March 16, 2014.