3 evli çift yuvarlak bir masa etrafinda eşler birbirleriyle yan yana olmayacka biçimde kac farklı şekilde oturabilir?

Question

Dönel PERMÜTASYON Sorusu

Comments

Siz bu soruda neler düşündünüz / denediniz?

---

Soru, Probleme des Menages olarak bilinir.

Osmanlı Devleti'nin alimlerinin sonlu matematik çalışmasını bırakmasına sebep olan problemdir. ''Böyle kafir icadı zındık bir sual ile namahrem kimselerin yan yana oturmasını hesab eylemek caiz değüldür!'' denerek bu durum protesto edilmiştir. Kombinatorik alanında ilerleyemememizi bu probleme bağlayabiliriz.

Bir de Fransızca'da Menage a trois kelimesi vardır. Karı, koca ve bunlardan birinin aşığından oluşan üç kişilik aile anlamında kullanılmıştır. Neyse ki bununla ilgili problem kurgulanmamış, yoksa kombinatorik tamamen hayatımızdan çıkabilirdi.

Bunlar, Probleme des Menages'i bir derste sunarken dinleyicilerin dikkatini toplama amaçlı anlattığım kurgu hikayelerdir :) $n$ evli çift bulunan Probleme des Menages (evli çift problemi), içerme dışarma prensibiyle genel halde çözülmüştür. İnternetten arama yapabilirsiniz.

---

Bunun yerine eşlerin bir arada olduğu tüm durumların sayısını bulabilir misin?

---

Mehmet Toktaş hocam, tüm eşlerin bir arada olduğu durum $(3-1)!\cdot 2!\cdot 2! \cdot 2!=16$ dır. Bunu çözümde nasıl kullanmayı düşünüyorsunuz?

---

Tüm oturma durumlarından eşlerin bir arada olmaları farkı istenileni vermez mi?

---

Ayzade çifti $A_1,A_2$, Beyzade çifti $B_1,B_2$, Ceyzade çifti $C_1,C_2$ olsun. $\boxed{A_1,A_2}, B_1,C_1,B_2,C_2$ dizilişini dairesel olarak yapalım. Bu istenmeyen bir durumdur. Ayrıca  $\boxed{A_1,A_2}, C_1, \boxed{B_1,B_2}, C_2$ dizilişini de dairesel olarak yaparsak yine istenmeyen bir durum oluştu. Bu istenmeyen durumlar yukarıda sayısını $16$ olarak hesapladığımız $\boxed{A_1,A_2}, \boxed{B_1,B_2},\boxed{C_1,C_2}$ türü dairesel dizilişli istenmeyen durumlardan farklıdır. Yani çıkarmamız gereken daha çok durum vardır.

---

Hocam ben bir tanesini sabit tutup diğerlerini dairesel olarak yerleştirdim fakat farklı bir sonuca ulaştım.

---

Hocam onu denedim 5!-16'dan 104 çıkıyor fakat cevap 32.

Answer 1

Genel halde $n$ evli çiftin yuvarlak masa etrafında, herhangi iki çift yan yana bulunmayacak biçimde oturma sayısını hesaplayacağız. Bu problemin az farklı versiyonu cinsiyetçi olmayan (non-sexist menage problem) veya serbest (relaxed menage problem) evlilik problemi olarak da bilinir. Az farklı dedim, sebebi şudur: relaxed menage problem'de dairesel permütasyon da uygulanmıyor. Yani yuvarlak masa etrafına yerleştirilen koltuklar da ayırtedilebilirdir. Başlayalım:

 

Tüm durumlar: $(2n-1)!$ dir.

Şimdi istenmeyen bir durum olarak bir çifti seçelim ve bunların yan yana olduğu dairesel dizilişleri hesaplayalım: $\dbinom{n}{1}(2n-2)!2!$ olur. Sondaki $2!$ çarpanının sebebini tahmin edebiliriz. Yan yana oturan çiftlerin kendi arasındaki yer değiştirmesidir.

 

Şimdi de iki çift seçelim ve bunlar da eşleriyle yan yana bulunsunlar: $\dbinom{n}{2}(2n-3)!(2!)^2$ Bu durumu tekrar ekleyeceğiz...

 

Şimdi de üç çift seçelim ve bunlar da eşleriyle yan yana bulunsunlar: $\dbinom{n}{3}(2n-4)!(2!)^3$ Bu durumu tekrar çıkaracağız ...vesaire

 

İçerme-dışarma prensibi ile genel hal  $$(2n-1)! - \dbinom{n}{1}(2n-2)!2! + \dbinom{n}{2}(2n-3)!(2!)^2 -  \dbinom{n}{3}(2n-4)!(2!)^3 + \cdots$$ biçiminde elde edilir.

 

$n=3$ evli çift için $5! - \dbinom{3}{1}4!2! + \dbinom{3}{2}3!(2!)^2 -  \dbinom{3}{3}(2)!(2!)^3 =32$ diziliş bulunur.

 

Notlar:

1. Buradaki  bağlantıda $n=3$ durumunun sayısı $m_3=192$ ile ifade edilmiş. İlk bakışta bir yazım hatası yapıldığını düşünmüştüm. Ancak bir yazım veya hesaplama hatası yoktur. Başta da belirttiğimiz gibi, relaxed menage problem'de dairesel sıralama yapılmadan hesaplandığı için $192$ elde edilmiş. $6$ kişi dairesel sıralandığında $\dfrac{192}{6}=32$ elde edilir. Yukarıda verdiğim sonuçla bağlantıdaki sonuç şimdi uyumlu oldu.

2. Aynı bağlantıda cinsiyetçi evlilik problemi de sunulmuştur: $n$ evli çift yuvarlak masa etrafına, herhangi bir çift yan yana bulunmayacak ve kadın/erkek alterne olarak dizilecek biçimde (yani aynı cinsiyetteki iki kişi yan yana bulunmayacak biçimde) kaç farklı yolla sıralanabilir? Orijinal Probleme Des Menages işte budur. Burada da dairesel permütasyon ile ilglilenilmiyor. Yani yuvarlak masa etrafındaki koltuklar ayırtedilebilirdir. Bunun çözümünü de yine içerme-dışarma prensibi ile (kolay değildir ama) yapabiliriz.