Matematik Eğitimi Kooperatifi; matematik eğitimine yönelik yenilikçi içerikler üretmek, paylaşmak ve alana etkili katkı sağlamak amacıyla kurulmuş bir eğitim kooperatifidir.

Permütasyon ve Kombinasyon Sorularına Alternatif Çözüm Yöntemleri

Yazar Alpaslan Kargın
Yayın Tarihi

Olasılık problemleri denilince hepimizin aklına ilk gelebilecek problem türleri zar problemleridir. Kaynaklarda daha çok bir veya iki zarın üst yüzüne gelen değerlerle ilgili problemlere rastlarız. Peki, soru üç veya daha fazla zar atıldığında üst yüze gelen sayıların toplamını veren olay sayısının bulunması olsaydı?

Genellikle karşılaşılan soruların içeriği bir veya iki zar üzerinden kurgulanmaktadır. Çoklu durumlara yönelik herhangi pratik bir öneri ve uygulama bulunmamaktadır. Söz gelimi 4 tane zarın üst yüzeylerine gelen sayıların toplamının 13 olma durumu inceleniyorsa {1,1,5,6}, {1,2,4,6}, {1,2,5,5} gibi tüm durumları tespit etmek ve ayrıca her bir durum için oluşan sıralama faktörünü de hesaplamak gerekir. Örneğin {1,1,5,6} için {1,5,1,6} veya {1,5,6,1} gibi 12 farklı durum olduğunu tespit ederek her durum için toplamın bulunması ve genel sonuca ulaşılması zorunludur. Bu çözüm yöntemi zaman kaybına,işlem fazlalığına ve işlem hatası yapılmasına neden olabilir. Öyleyse nasıl bir çözüm yolu izlenmelidir?

Bu aşamada J. V. Uspensky tarafından 1937’de yazılan Introduction to Mathematical Probability adlı bir kitapta yer verilen düzgün s yüzlü n tane nesne için toplamların p olma olay sayısını hesaplayan

((pn))=∑k=0kmax(−1)k(nk)(p−s·k−1p−s·k−n)

kmax=[[p−sn]] { [[x]]: x’den küçük veya eşit en büyük tam sayı }

formülüne ulaşılmıştır [1]. Formülü ifade etme kolaylığı açısından kitabın yazarının ismine ithafen “Uspensky Formülü” adı verilmiştir.

Bu yazıda, Uspensky formülünün kullanımı ve başka soru türlerinin çözümüne (karmaşık kombinatorik ve tamsayı katsayılı lineer denklem) uyarlanmasınıele almaya çalışacağız. Özellikle olimpiyat sorularında sıklıkla karşılaşılan karmaşık kombinatorik ve lineer denklem soru türlerinde hata yapma riski fazla olmayan bir yöntemle, kısa sürede çözüme odaklanılır. Bu anlamda soruların çözümünde yaşanan karmaşadan kaynaklanan hataları yok etmek üzere bir yöntem geliştirilmesi hedeflenmiş ve “Uspensky Formülü” (1) olarak adlandırılan formülün zar toplamları haricinde aşağıda belirtilen karmaşık soru tiplerine uygulanabilmesi amaçlanmıştır. Ortaöğretim matematik dersi öğretim programı içerisinde yer alan permütasyon, tekrarlı permütasyon, kombinasyon konularındaki temel bilgiler ve yaklaşımlar bu çalışmada kullanılmıştır.

Ayrıca “Uspensky Formülü” eşitliği kullanılarak Python programlama dilinde istenilen olay sayısının hesaplanabildiği bir küçük kod bloğu da oluşturulabilir.

def faktoriyel_hesapla(n):
    if n==0 or n==1:
        return 1
    else:
        return n*faktoriyel_hesapla(n-1)
def kombinasyon_hesapla(n, r):
    sonuc = faktoriyel_hesapla(n)/(faktoriyel_hesapla(r)*
        faktoriyel_hesapla(n-r))
    return sonuc
yuz_say = int(input("Kaç yüzlü bir nesne ile işlem yapılacak..: "))
nesne_say = int(input("Kaç tane nesne kullanılacak..: "))
toplam = int(input("İstenilen toplam kaç..: "))
k_max = int((toplam - nesne_say)/yuz_say)
olay_say = 0
for j in range(0,k_max + 1):
    olay_say+=int(((-1)**j)*kombinasyon_hesapla(nesne_say, j)*
        kombinasyon_hesapla(toplam - (yuz_say*j)-1,
        toplam - (yuz_say*j)-nesne_say))
print(olay_say)

Tablo 1. Uspensky Eşitliğinin Python dilinde yazımı.

Öncelikle en çok kullanılan yöntemleri listeleyelim ve bu çalışmada kullanılmak üzere bu yöntemleri isimlendirelim.

Örnek Soru: a ve b toplamları 8 olan iki pozitif doğal sayı olsun. Kaç farklı (a,b) ikilisi vardır?

Listeleme Yöntemi: Olası tüm olayların sıralama faktörü de dikkate alınarak listelenmesi ve elde edilen tüm listelerin sayılmasına dayanır.

Sorunun listeleme yöntemine göre çözümü {(1,7), (2,6), (3,5), (4,4), (5,3), (6,2), (7,1)} şeklindedir. Cevap 7 bulunur.

Ayraç Yöntemi: Olası tüm olay sayısının bir bütünün parçalara ayrılması ile bulunmasına dayanır. Kombinasyon kullanılarak hesaplanır. Alttan veya üstten sınırlandırılmış problemlerin çözümünde yeterli olmamaktadır.

Sorunun ayraç yöntemine göre çözümü 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 burada bütün yani 8 en küçük birim olan 1’ler kullanılarak 8 parçaya bölünmüştür. Şimdi bu 8 parça iki gruba ayrılacaktır. 8 parçanın aralarında yedi adet boşluk vardır. Bu boşluklardan biri seçilerek oraya bir adet ayraç konulduğunda iki farklı grup elde edilecektir. Bu grupların sol taraftaki sayıların toplamı a sayısını, sağ taraftakilerin toplamı ise b sayısını verecektir. Bu durumda ayracı yerleştirebileceğimiz 7 adet yerden 1 tanesini seçmeliyiz. C(7,1) = 7 sorunun cevabı olacaktır.

Olay Ağacı Yöntemi: Bu yöntem ikinci sayının kendini birinci sayının durumuna göre konumlandırmasına bağlı olarak kurgulanan yöntemdir. Şöyle kibirinci sayı şu ise ikinci sayı bu olmalıdır.

Sorunun olay ağacı yöntemine göre çözümü: ((pn)) p: istenen toplam, n: değişken sayısını ifade etsin. Bu durumda hesaplanması gereken olayların sayısı ((82)) olur. Bu durumda b sayısı a sayısından gelen değere göre şekillenecektir. Nihayetinde toplamları 8 olan iki pozitif doğal sayıdan bahsedilmektedir. a sayısının alabileceği durumlar ise ((11))((21))((31))((41))((51))((61))((71)) olmak üzere 7 farklı durumdur. a sayısı 1’den küçük veya 7’den büyük olamaz.

Yazı boyunca Uspensky formulünün de kullanılabileceği aşağıda verilen altı farklı problem tipinin nasıl çözülebileceğine dair genelleştirmeler yapılacaktır.

i) Bir çocuk en az 1, en fazla s adet oyuncak alacak şekilde p tane özdeş oyuncak, n tane çocuğa kaç farklı şekilde dağıtılabilir?

ii) Bir çocuk en fazla s adet oyuncak alacak şekilde p tane özdeş oyuncak, n tane çocuğa kaç farklı şekilde dağıtılabilir?

iii) Belli bir çocuk en az 1 ve bir çocuk en fazla s oyuncak alacak şekilde p tane özdeş oyuncak, n tane çocuğa kaç farklı şekilde dağıtılabilir?

iv) a,b,c,d sıfırdan farklı birer rakam olmak üzere ve a+b+c+d=p olacak şekilde kaç farklı (a,b,c,d) sıralı dörtlüleri oluşturulabilir?

v) a,b,c,d birer rakam olmak üzere ve a+b+c+d=p olacak şekilde kaç farklı (a,b,c,d) sıralı dörtlüleri oluşturulabilir?

vi) a,b,c,d birer rakam olmak üzere ve a+b+c+d=p olacak şekilde kaç farklı dört basamaklı abcd sayısı yazılır?

Bu yazının içeriğini oluşturmaya yol açan soru üç veya daha fazla zar atıldığında üst yüze gelen sayıların toplamını veren olay sayısını bulmaktı. Söz gelimi 3 tane zarın üst yüzeylerine gelen sayıların toplamının 11 olma durumunu inceleyelim.

Başlangıçta şu sistematik düşünce yapısına göre formül arayışı yapılmıştır. Bir tane zar atıldığında üst yüze gelen sayılar için 6 farklı olay vardır. Bunlar {1,2,3,4,5,6} olaylarıdır ve her bir olay bir kere meydana gelir. İki zar atıldığında ise olay sayısı 36 olur. Bu durum 3 zara çıktığında 63=216, n tane zar için 6n kadar olay sayısı meydana gelir. Örneğin 2 zar için aşağıdaki 36 farklı durum meydana gelir.

{(1,1), (1,2),(1,3), (1,4), (1,5), (1,6), (2,1), (2,2), (2,3), (2,4), (2,5), (2,6), (3,1), (3,2), (3,3), (3,4), (3,5), (3,6), (4,1), (4,2), (4,3), (4,4), (4,5), (4,6), (5,1), (5,2), (5,3), (5,4), (5,5), (5,6), (6,1), (6,2), (6,3), (6,4), (6,5), (6,6)}

Zarların üst yüzlerine gelen sayıların toplamlarını bulmak istediğimizde bir, iki ve üç tane zar için bu durumlar belki tek tek elle hesaplanabilir. Fakat daha büyük sayıda zar için durum gittikçe karmaşık ve zor bir hâle gelecektir. Aynı zorluk farklı yüz sayılarına sahip (4 yüzlü, 5 yüzlü 8 veya 10 yüzlü) nesneler için degeçerlidir. Temel yaklaşımımız bu durumda şöyle şekillenmiştir:

Üç tane zarın üst yüzeylerine gelen sayıların toplamının 11 olduğunu bulmak için iki zarın üst yüzeylerine gelen sayıların toplamının 5,6,7,8,9,10 olduğu durumları bilmek yeterlidir. Çünkü üçüncü zar ilk iki zar toplamını 11’e tamamlayacak değere sahiptir.

((pn)) p: istenen toplam, n: zar sayısını ifade etsin. Bu durumda hesaplanması gereken olayların sayısı Tablo 2’ deki gibidir.

Tablo 2. 3 zarın toplamlarının 11 olma olay sayısı

Tablo 2. 3 zarın toplamlarının 11 olma olay sayısı

Geliştirilen yöntemin geçerliliği, farklı soru türlerinin çözümü üzerinde test edilmiştir.

Aşağıda, kombinatorik ve lineer denklem soru tiplerinin “Uspensky Formülü” yardımıyla yapılan örnek soru çözümlerine yer verilmiştir.

Örnek 1: 17 özdeş oyuncak dört çocuğa;

a) Her çocuk en az bir oyuncak almak şartıyla kaç farklı şekilde dağıtılabilir?

b) Kaç farklı şekilde dağıtılabilir?

c) Bir çocuk en az 1, en fazla 9 oyuncak alabilecek şekilde kaç farklı dağıtım yapılabilir?

d) Bir çocuk en fazla 9 oyuncak alacak şekilde kaç farklı dağıtım yapılabilir?

e) Belli bir çocuk en az 1 ve bir çocuk en fazla 9 oyuncak alacak şekilde kaç farklı dağıtım yapılabilir?

Çözüm:

a) Bu tarz soruların çözümünde kullanılan bazı yöntemler vardır. Bu yöntemlerden biri de ayraç metodudur. Oyuncaklar eğer * * * * * * * * * * * * * * * * * ile temsil edilirse 17 oyuncak dört ayrı gruba ayrılacağı için 3 ayraç | | | kullanılmalıdır. 3 ayraç nesneler arasındaki boşluklardan seçileceği için 16 boşluktan 3 ü seçilmelidir. Bu durumda Cevap C16,3 kombinasyonudur. * * */ * */ * * * * * * * * * * */ * seçimlerden biri böyle olacaktır. Bunun anlamı 1.çocuk üç, 2.çocuk iki, 3.çocuk on bir ve 4.çocuk bir oyuncak alacaktır.

b) Bu seçenek için ise uygulanan ayraç yöntemine oyuncak sayısına çocuk sayısı kadar oyuncak eklendiği ve dağıtım yapıldıktan sonra her çocuktan 1 oyuncak geri alınarak toplam dağıtılan oyuncak sayısının değişmediği üzerine kurgulanmıştır. Bu durumda çözüm C20,3 lü kombinasyonudur.

c) Bu seçeneğin çözümü için ayraç yöntemi kullanılamamaktadır. Çünkü soruda üstten sınırlama mevcuttur. (1) no’lu denklemden faydalanılacaktır. p=17, n=4, s=9 ve (1, 2, 3, 4, 5, 6, 7, 8, 9) olarak seçilir.

kmax=[[17−49]]=1

((174))=∑k=01(−1)k(4k)(17−9·k−117−9·k−4)

=(−1)0(40)(1613)+(−1)1(41)(74)

=1·1·16·15·143·2·1−1·4·7·6·53·2·1

=560−140

=420 olur.

d) Bu seçenek için (1) no’lu denklem çözümünden ve (b) şıkkında düşündüğümüz yöntemden faydalanacağız. p=17, n=4, s=10 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) olarak seçilir.

((p+nn))=((17+44))

kmax=[[21−410]]=1

((214))=∑k=01(−1)k(4k)(21−10·k−121−10·k−4)

=(−1)0(40)(2017)+(−1)1(41)(107)

=1·1·20·19·183·2·1−1·4·10·9·83·2·1

=1140−480

=660

olur.

e) (1) nolu denklem yardımıyla çözülecektir. Belirli bir çocuğun hiç oyuncak almadığı durum tüm sonuçlardan çıkarılacaktır.

((p+nn))−((p+n−1n−1))

((17+44))−((17+4−14−1))

kmax=[[21−410]]=1 ve kmax=[[20−310]]=1

∑k=01(−1)k(4k)(21−10·k−121−10·k−4)−(∑k=01(−1)k(3k)(20−10·k−120−10·k−3))

=(−1)0(40)(2017)+(−1)1(41)(107)−((−1)0(30)(1917)+(−1)1(31)(97))

=1·1·20·19·183·2·1−1·4·10·9·83·2·1−(1·1·19·182·1−1·3·9·82·1)

=1140−480−171+108

=597 olur.