Gönderen Konu: Evli Çift Problemi - Probleme Des Menages {Çözüldü}  (Okunma sayısı 787 defa)

Çevrimdışı scarface

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3199
  • Karma: +22/-0
  • İstanbul
Evli Çift Problemi - Probleme Des Menages {Çözüldü}
« : Mart 05, 2020, 05:46:11 ös »
$3$ evli çift yuvarlak bir masa etrafında eşler birbirleriyle yan yana olmayacak biçimde kaç farklı şekilde oturabilir?
« Son Düzenleme: Mart 05, 2020, 05:52:12 ös Gönderen: scarface »
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

Çevrimdışı scarface

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3199
  • Karma: +22/-0
  • İstanbul
Ynt: Evli Çift Problemi - Probleme Des Menages
« Yanıtla #1 : Mart 05, 2020, 05:51:42 ös »
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.


Çözüm:
Genel halde $n$ evli çiftin yuvarlak masa etrafında, herhangi iki çift yan yana bulunmayacak biçimde oturma sayısını hesaplayacağız. Bu problem cinsiyetçi olmayan (non-sexist menage problem) veya serbest (relaxed menage problem) evlilik problemi olarak da bilinir. 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ş. Ancak bu bağlantıda bir yazım ve hesaplama hatası yapıldığını görüyorum. 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? Bunun çözümünü de yine içerme-dışarma prensibi ile kolayca yapabiliriz.
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 
SimplePortal 2.3.3 © 2008-2010, SimplePortal