permütasyon

[kahyaoglu_4635]

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 ?

[Lokman Gökçe]

Ö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.

[kahyaoglu_4635]

Teşekkürler Lokman Hocam. Sayıgılar...

[Lokman Gökçe]

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 ...

[senior]

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!² 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!)² + 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!² + 4*2!) - 3!(2!³ + 6*2!² + 3*2!) + 2!(2*2! + 3*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)