Gönderen Konu: 3 boncuklu n renkli kolye ve bilezik sayısı {çözüldü}  (Okunma sayısı 4814 defa)

Çevrimdışı Lokman Gökçe

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3.717
  • Karma: +23/-0
  • İstanbul
[1] Kolye Problemi: Çembersel bir halkaya dizilmiş $3$ boncuk ve $n$ farklı renge sahibiz. $3$ boncuk bir eşkenar üçgenin köşelerini oluşturmaktadır. Bu renkler kullanılarak boncuklar birer renkle boyanacaktır. Bazı boncukların renkleri aynı olabilir.

Halkanın merkezi etrafında döndürülmesi sonucu biri diğerinden elde edilen boyamalar özdeş kabul edilmektedir. Kaç farklı boyama deseni yapılabilir?

Bu tür halka boyama problemlerine Kolye Problemi (İng: necklace) denir. $m$ boncuk ve $n$ renk için kolye sayısı $N(m,n)$ ile gösterilir.




[2] Bilezik Problemi: Çembersel bir halkaya dizilmiş $3$ boncuk ve $n$ farklı renge sahibiz. $3$ boncuk bir eşkenar üçgenin köşelerini oluşturmaktadır. Bu renkler kullanılarak boncuklar birer renkle boyanacaktır. Bazı boncukların renkleri aynı olabilir.

Halkanın merkezi etrafında döndürülmesi veya merkezden geçen bir doğruya göre simetrisi sonucu biri diğerinden elde edilen boyamalar özdeş kabul edilmektedir. Kaç farklı boyama deseni yapılabilir?

Bu tür halka boyama problemlerine Bilezik Problemi (İng: bracelet) denir. $m$ boncuk ve $n$ renk için bilezik sayısı $B(m,n)$ ile gösterilir.


« Son Düzenleme: Mart 31, 2020, 09:18:51 ös Gönderen: scarface »
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

Çevrimdışı Lokman Gökçe

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3.717
  • Karma: +23/-0
  • İstanbul
Ynt: 3 boncuklu n renkli kolye ve bilezik sayısı
« Yanıtla #1 : Mart 31, 2020, 09:18:33 ös »
Problemi $5$-gen ve sonra asal $p$-gen için daha genel halde çözelim.

Çözüm 1 (Simetri Prensibi ile):
Düzgün beşgenin her bir köşesi için $n$ tane renkten birini seçerek $n^5$ boyama yapabiliriz. Döndürme sonucu biri diğerinden elde edilen boyamalar özdeş kabul edildiği için tıpkı dairesel permütasyonda olduğu gibi tüm durumu $5$ e bölmek isteriz. Fakat bunun biraz sıkıntılı olduğunu görmeliyiz. Örneğin $n=2$ için $2^5$ sayısı $5$ ile tam bölünmüyor. Bu, bir boyama sayısı olamaz. Buradaki sorun, bazı boyamalar tüm durum olan $n^5$ içinde $5$ er kez görülürken bazıları yalnızca $1$ kez görülüyordur.

İşte bu yalnızca $1$ kez görülen boyamaların sayısını bulup tü durumdan çıkaralım. Bunlar, tek renkli boyamalardır. $n$ farklı renk olduğundan tam $n$ tane tek renkli boyama vardır. O halde $n^5 - n$ tane boyama, $5$ er kez görülmüşlerdir. Bunların hepsini birer kez saymak istediğimizden
$$ \dfrac{n^5 - n}{5}+n = \dfrac{n^5 +4n}{5}$$
özdeş olmayan boyama türü elde ederiz.


Çözüm 2 (Burnside Lemması ile): Beşgenin merkezi etrafında döndürme fonksiyonlarının grubu $G=\{ e, r_1, r_2, r_3, r_4 \}$ olsun. Burada $e=(1)(2)(3)(4)(5)$ özdeş fonksiyon, $r_1=(12345)$ $72^\circ$ döndürme fonksiyonudur. Diğerleri de $r_2=(13524)$, $r_3=(14253)$, $r_4=(15431)$ sırasıyla $144^\circ $, $216^\circ$, $288^\circ$ açıları ile döndürme fonksiyonlarıdır. Burnside Lemması'na göre
$$ \text{orbit sayısı} = \dfrac{1}{|G|}\sum_{f\in G}|Fix(f)|$$
dir. Şimdi $|Fix(f)|$ değerlerinin nasıl hesaplandığına bakalım.
$n$ farklı rengimiz vardır. $e$ özdeş fonksiyonu $5$ ayrık devirin çarpımı biçiminde olduğundan $|Fix(e)|=n\cdot n\cdot n\cdot n\cdot n = n^5$ tir.$r_i$ döndürme fonksiyonları $1$ ayrık devirin çarpımı biçiminde olduğundan $|Fix(r_1)|=|Fix(r_2)| = |Fix(r_3)| = |Fix(r_4)| =n $ dir. Buna göre
$$ \text{orbit sayısı} = \dfrac{1}{5}\sum_{f\in G}|Fix(f)|=\dfrac{n^5 + 4n}{5}$$
tane özdeş olmayan boyama elde edilir.


NOTLAR
1. Genel olarak $p$ asal sayı iken düzgün $p$-genin köşelerini $n$ farklı renk seçimi ile boyama sayısı birinci yol kullanılarak
$$ \dfrac{n^p - n}{p} + p = \dfrac{n^p + (p-1)n}{p} $$
ve ikinci yol kullanılarak $|Fix(e)|=n^p$, $|Fix(r_i)|=n$ olup yine
$$ \text{orbit sayısı} = \dfrac{1}{p}\sum_{f\in G}|Fix(f)|=\dfrac{n^p + (p-1)n}{p}$$
elde edilir.

2. $\dfrac{n^p - n}{p}$ bir tam sayı olduğundan $n^p \equiv n \pmod{p}$ sonucu elde edilir. Fermat teoreminin kombinatorik bir ispatıdır.

3. Eşkenar üçgen ve kare için kolye, bilezik sayıları hesaplarını bağlantı 1 , Bağlantı 2 ve Bağlantı 3'te video olarak sundum. Daha pekiştirici olması için yeni videolar da ekleyeceğim.
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 35 36 37 
SimplePortal 2.3.3 © 2008-2010, SimplePortal