Yükleniyor, lütfen bekleyiniz!
7 Ağustos 2010

Üretici fonksiyonlar yardımıyla kombinatorik problem çözümleri google ara
Facebookta paylaş

üretici fonksiyonlarÜretici fonksiyonlar yardımıyla Kombinatorik problem çözümlerinden bahsetmek istiyorum sizlere. Daha anlaşılır şekilde söylemek gerekirse;bazı permütasyon veya kombinasyon sorularını bir fonksiyon yardımıyla çözmeyi anlatacağım sizlere.
Jeneratör fonksiyon demeye alışmış olanlardan özür diliyorum ama o tabir hiç hoşuma gitmediği için üretici fonksiyon demeyi uygun buldum. Üretici fonksiyonlar (generating functions) katsayıları bir sayı dizisini temsil eden tek değişkene bağlı üslü serilerdir.

Örneğin, G(x)=1+x+x2+x3+...+xn= 1 / (1-x)

Polinomlarda olduğu gibi toplanabilirler, çarpılabilirler, türevleri alınabilir.

Matematikte bu fonksiyonların birçok kullanım alanı olduğunu belirtmekle beraber bunlardan küçük bir kısmı olan olasılık-permütasyon-kombinasyon kısaca 'sayma' sorularındaki kullanımlarına dair sadece iki örnek soru ve bu soruların üretici fonksiyonlar yardımıyla çözümleriyle bir alıştırma sorusu vermek istiyorum.

Soru: 8 bilyeyi 5 çocuğa kaç değişik şekilde dağıtabiliriz?
Çözüm: 1 çocuğun alabileceği bilye sayıları için üretici fonksiyonu yazalım çocuk 0 bilye alabilir, 1 bilye alabilir , 2 bilye alabilir ... 
G(x)=1+x+x2+x3+x4+x5+x6+x7+x8 ...= 1 / (1-x)   fonksiyonda  xn in katsayısı çocuğun n tane bilye almasını gösteriyor.
5 çocuğumuz olduğuna göre her çocuk için yazdığımız fonksiyonları çarpalım,
G(x)= (1+x+x2+x3+x4+x5+x6+x7+x8 +...)5= 1 / (1-x)5 bu eşitliği sol tarafının açılımı bilmemiz gerekiyor.
G(x)= 1+5x+15x2+35x3+70x4+126x5+210x6+330x7+495x8 +...
Burada bu sorunu cevabı 495. Eğer fonksiyonu hesaplamak zor görünüyorsa direkt aradığımız terimin katsayısını hesaplayabiliriz.
Oda g (x)= 1 / (1-x)5 ifadesinin 8 defa türevi alınırsa 5.6.7.8.9.10.11.12.(1-x)-13 bulunur. Bu fonksiyondaki sabit terim aradığımız katsayının 8! Katıdır, x=0 daki değerini 8! e böldüğümüzde 12!/(4!*8!)=495 değerine ulaşırız.


Artık tüm dağıtım işleminin üretici fonksiyonuna sahibiz, 8 bilye olduğu için bu fonksiyonda teriminin katsayısı 495 aradığımız cevaptır. “Çocukları 1, bilyeleri 0 gibi düşünseydik bu çözümden kat be kat kısa bir çözüm yapardık” dediğinizi duyar gibiyim :)
Peki sizin istediğiniz olsun soruda bazı değişiklikler yapalım,
-12 bilye olsun
-4 çocuk olsun
-Her çocuk en az 1 bilye alsın
-Hiçbir çocuk 3 bilye almasın
-Her çocuk en fazla 5 bilye alsın

artık sorumuzun cevabını C(15,3) ya da hadi bir adım ilerisi olan her çocuğa 1 bilyenin en baştan dağıtılması durumu için C(11,3) diyip kolayca çözemeyiz. Tüm durumları ya tek tek inceleyeceğiz ya da bir çocuk için üretici fonksiyonumuzu yazacağız.
g(x)= x+x2+x4+x5 = x. (1+x+x3+x4)

Hiçbir çocuk 0 ya da 3 bilye ve 5 ten fazla bilye alamadığı için o terimlerin katsayıları fonksiyonumuzda 0. 
Tüm durumlar için fonksiyonumuzun 4. kuvvetini almalıyız
Bu kuvvet alma işlemini gereksiz terimleri atıp sadeleştirmeler yardımıyla -örneğin 9. kuvvetlere ihtiyacınız yoktur- kendiniz yapabileceğiniz gibi bu sitede önceden Online Matematik başlığı altında sunulan mathway.com gibi siteler ve programlar yardımıyla da yapabilirsiniz. Ben program kullanmayı tercih ediyorum :)

(g(x))4 = G(x)= x4 (1+4x+6x2+8x3+17x4+24x5+22x6+28x7+36x8 +... )  aradığımız cevap x12 teriminin katsayısı olan 36 dır. 



Şimdi gelelim ikinci ve daha zor bir soruya;
Soru: Bir tabanı 7x7 portakal alan ve 7 sıra üst üste portakal istiflenmiş bir kasanın (343 portakal) tam merkezindeki portakal çürümüştür. (Her portakalı eşit büyüklükte küp ya da küre gibi düşüneceğiz, her portakal 3 doğrultuda toplam 6 portakala temas ediyor) Hergün çürük portakal temas ettiği 6 portakalı eğer halen çürümemişlerse çürütmektedir. 5. gün sonunda kasada kaç sağlam portakal kalır?

Çözüm: Soru tabi ki geleneksel yöntemlerle parçalara ayrılıp her parçanın sonucu hesaplanıp , ve bu sonuçların hepsi toplanıp çözülebilir ama çözmenin daha kolay bir yöntemi de üretici fonksiyonlardan faydalanmaktır.
Tüm portakalları küçük küpler olarak düşündüğümüzde bir portakalın 5. gün sonunda çürüyüp çürümemesi o portakalın merkezdeki portakaldan geçişler için sadece yüzler kullanılarak 5 birim ya da daha kısa mesafede olmasına bağlıdır. O portakala sadece yüzlerden geçilerek 5 adımda ulaşılabiliyorsa portakalımız çürümeye mahkumdur.
Adımlarımızı x,y ve z eksenleri olmak üzere 3 eksende yapabiliriz ve herhangi birindeki adımımız diğerindeki adımı etkilememektedir.
Şimdi merkezdeki portakalı gözümüzün önüne getirelim ve x ekseninde düşünelim,
0 birim uzakta 1 yer vardır o da kendi yeri, 1 birim uzakta sağdan ve soldan komşusu olan 2 yer , 2 ve 3 birim uzakta yine 2şer yer vardır. 4 birim uzakta bir yer yoktur.
Bir eksen için fonksiyonumuz;
g(x)= 1+2x+2x2+2x3
herbir eksen için aynı işlem yapılıp çarpılmalı
G(x)= (1+2x+2x2+2x3 )3=  1+6x+18x2+38x3+60x4+72x5+68x6+48x7+24x8 +8x9 +... 
(katsayıların toplamının 343 olduğuna dikkat ediniz)

burada xn teriminin katsayısı n. gün kaç portakal çürüdüğünü göstermektedir. 5. gün sonu sorulduğuna göre 
1+6+18+38+60+72=195 portakal çürür
68+48+24+8=148 portakal sağlam kalır.
Sorumuzda ilk çürük portakal merkezdeki yerine sağdan 3. , alttan 5. ve derinlemesine 4. sırada bulunan olsaydı;
x ve y eksenleri için g(x)= 1+2x+2x2+x3+x4
z ekseni için  g(x)= 1+2x+2x2+2x3
fonksiyonlarıyla ve bu 3 fonksiyonun çarpımı olan
1+6x+18x2+36x3+54x4+64x5+61x6+48x7+31x8 +16x9 + 6x10 +2x11 +...
üretici fonksiyonuyla işlem yapmalıydık.


Görüldüğü gibi üretici fonksiyonlar görece basit problemler için kısa diyebileceğimiz çözümler ortaya koyamamaktadır ama işlemlerin karmaşıklaştığı durumlarda sayma problemleri için çok verimli çözümler sunmaktadır.

Öğrendiklerimizi kullamaya çalışalım;
Alıştırma: 8 harfli “KELLEBEK” kelimesinin harflarini kullanarak anlamlı anlamsız 5 harfli kaç kelime yazılabilir? Cevaplarınızı yorum olarak yazabilirsiniz.


Not:Benzer örnekler için buradaki makalede ki örneklere bakabilirsniz.
 
 
 

Alperen 12224 | 3 Ocak 2015 23:54 | Ziyaretçi
avatar
Helâl olsun vallahi helal olsun Final sınavına ilaç gibi geldi..
   
minecraft58 | 8 Aralık 2014 21:06 | Ziyaretçi
avatar
Ben cevabı buldum,
40 320
Çok güzel bir yöntem...
OLİMPİYATA GİRDİM BÖYLE SORULAR ÇIKTI.ÖĞRETMENİME KONUYU SORDUM VE ARAŞTIRDIM. SONRA BU SİTE KARŞIMA ÇIKTI .ARTIK BURAYI TERCİH EDİYORUM ÇÜNKÜ EN İYİ BU SİTEDEN ANLIYORUM...
   
Mööleyeninek | 30 Eylül 2012 19:08 | Ziyaretçi
avatar
Biraz zor,anlamak şimdilik öğrenmek için çabalamayı düşünmüyorum.Olimpiyat gibi bir durumum yok ileride belki bakacağım amacım suan unıversite.
   
gurbet | 26 Şubat 2012 13:28 | Ziyaretçi
avatar
harika bi yöntem bende yapıcam....
   
gereksizyorumcu | 12 Ağustos 2010 04:25 | Yazar
avatar
kontdragon333,
Yazıda da değindiğim gibi karşımıza çıkabilecek normal sorular için çok verimli bir yöntem değil , genel olarak normal çözümler daha kısa sürer. Her ne kadar üniversite sınavını hedef tahtasına oturtmuş birçok arkadaşımızın hiçbir işine yaramayacak olsa da böyle birşeylerin olduğunu da bilmekte fayda var

Daha iyi anlayabilmek için kolay anlaşılabilir ve gözünde canlandırabileceğin örnekler üzerinde düşünebilirsin. Misal yazıda geçen portakal kasasında 7x7 ve tek sıra olduğu durumu çözebilirsin ve kağıda çizip sayabilirsin. 
   
kontdragon333 | 11 Ağustos 2010 16:34 | Üye
avatar
Harika yöntem!...Anlamaya çabalıyorum..
   

Zorunlu

Zorunlu