Geomania.Org Forumları
Fantezi Cebir => Kombinatorik => Konuyu başlatan: kahyaoglu_4635 - Şubat 06, 2015, 11:00:38 öö
-
A={1,2,3,4,5,6} kümesinin permütasyonlarından kaç tanesinde yan yana olan bütün elemanlar arasında en az iki fark vardır ?
-
Önce soruyu zorlaştırıp $n$ elemanlı küme için çözelim. Bizden ardışık tamsayıların yan yana görülmediği permütasyonların sayısı istenmektedir. $A={1,2,\dots,n}$ kümesinde istenen özellikteki permütasyonların sayısı $a_n$ olsun. $a_1=a_2=a_3=0$ olduğu açıktır. $n=4$ durumuna bakalım. $(2413)$ ve $(3142)$ şeklinde iki permütasyon olduğundan $a_4=2$ dir.
$n\geq 4$ için problemi çözelim. $n$ inci sayıyı $n-1$ nin iki yanına da yazamayacağımızı göz önüne alalım. Dolayısıyla $n$ inci sayıyı $a_{n-1}$ deki her bir permütasyonda $n-2$ farklı yere yazabiliriz. Böylece $a_{n}=(n-2)a_{n-1}$ olur. Bu eşitlikte $n=5,6, \dots, k$ yazıp taraf tarafa çarparsak $a_k=2\cdot 3 \cdot 4 \cdots (k-2)$ olup $n\geq 4$ için $a_n=(n-2)!$ elde edilir.
$a_6=4!=24$ tür.
-
Teşekkürler Lokman Hocam. Sayıgılar...
-
Soruyu hatalı çözmüşüm. $n=4$ durumunda $2314$ istenmeyen bir permütasyondur, ancak bunu kullanarak $n=5$ halinde $25314$ permütasyonu elde edilebiliyor. Dolayısıyla $a_n \geq (n-2)a_{n-1}$ olmaktadır. Tekrar bakalım ...
-
Lokman Hocam, n için soru çok derin :) Önce ben n = 6 için kendi ( kirli :) ) yöntemim ile çözeceğım.
Bütün Kombinasyonlar 6!.
Bunların içinde yasak çiftlere sahip olanları var. Yasak çiftler (1,2), (2,3), (3,4), (4,5), (5,6). Yani 5 tane.
(1,2) veya (2,1) çifti olan sıralamaların sayısı 2!*5! (5! çünkü (1,2) tek eleman gibi davranıyor)
Bunu 5 çift için yaparsak yasak sıralamaların sayısı 2!*5!*5 olur. Yani sonuç 6! - 2!*5!*5 gibi bir şey. Ama çiftleri sayarken bazı şeyleri iki kez saydık. Onları geri eklemeliyiz. Mesela (1,2) ve (3,4) çiftlerinin bulunduğu permütasyonları iki defa çıkardık aslında. O yüzden herhangi iki yasak çifti birlikte düşünüp sonuca eklemeliyiz. (!)
Bu iki çifti C(5,2) = 10 farklı şekilde seçebiliriz. Burda da bir özel durum var. Eğer (1,2) ve (2,3) seçilirse bu permütasyonda iki tane 2 sayısı olamayacağından aslında öbek olarak (1,2,3) seçilmiş demektir. Böyle ardışık 4 tane çiftimiz var: ( (1,2,3),(2,3,4),(3,4,5),(4,5,6) ). Diğer 6 sı normal. Eğer ortak elemanı olmayan çiftlerden seçersek, mesela (1,2) ve (3,4) seçilirse. Her ikisini de 2! şekilde sıralayabileceğiz, yani 2!2 ama yukardaki gibi ortak elemanlı seçersek bu sefer ancak (1,2,3) ve (3,2,1) şeklinde ters çevirebiliriz, yani sadece 2!. İki durumda da öbekler tek elemanmış gibi davranır ve bizi 4 tane bağımsız elemanla bırakır. Yani toplam 4!( 6* (2!)2 + 4*2!)
Tabi burda da 3 yasak çiftin olduğu durumları fazladan topladık. Onları geri çıkarmamız lazım, aynısını 4 ve 5 için yaparsak sonuçta şunu buluyoruz:
6! - 5! (5*2!) + 4! (6*2!2 + 4*2!) - 3!(2!3 + 6*2!2 + 3*2!) + 2!(2*2! + 3*2!2) - 2! = 720 - 1200 + 768 - 228 + 32 - 2 = 90
https://oeis.org/A002464 Adresinde problem ile alakalı baya açıklama var ve dizi de şu şekilde.
a(n) = (n+1)*a(n-1) - (n-2)*a(n-2) - (n-5)*a(n-3) + (n-3)*a(n-4)