Tekrarlı Kombinasyon

Tekrarlı kombinasyon, klasik kombinasyona benzer; tek fark, M kümesinin elemanlarının seçimde tekrar edebilmesine izin vermemizdir.

Tanım ve Formül

Güzel bir örnekle başlayalım: Bir markete gittin ve kampa götürmek için on iki şişe meyve suyu almak istiyorsun. Rafta toplam dört farklı meyve suyu var. Şimdi şişeleri alabilmen için birkaç yol var — örneğin 5 şeftali, 2 vişne, 1 elma ve 4 portakal suyu alabilirsin ya da her çeşitten tam üçer şişe alabilirsin. Tam on iki şişe olacak şekilde şişeleri kaç farklı biçimde alabilirsin?

Elimizde M = {Şeftali, Vişne, Elma, Portakal} kümesi var ve soru şu: M kümesinin elemanlarından oluşan, sıranın önemli olmadığı, r’li gruplardan (r = 12) kaç tane vardır?

Formülü çıkarmak, diğer sayma sorularına göre biraz daha zordur. Önce alışverişimizi sıfırlardan ve birlerden oluşan bir dizi olarak düşünelim: Birlerin sayısı, o çeşitten aldığımız şişe sayısına eşit olsun, sıfır da çeşitleri birbirinden ayırsın. Yani 111011101111101 dizisi şunu söyler: üç şeftali suyu aldık (ilk üç 1), sonra üç vişne suyu (0 ayraçtır, sonraki üç 1), sonra beş elma suyu (0 ayraç, sonra beş 1) ve son olarak bir portakal suyu. Bütün fikri aşağıdaki şekil gösteriyor:

$$\underset{Şef}{\underbrace{111}}0\underset{Viş}{\underbrace{111}}0\underset{Elm}{\underbrace{11111}}0\underset{Por}{\underbrace{1}}$$

6 şeftali, 4 vişne, 2 portakal ve hiç elma suyu almak istersek dizi şöyle görünürdü:

$$\underset{Şef}{\underbrace{111111}}0\underset{Viş}{\underbrace{1111}}00\underset{Por}{\underbrace{11}}$$

Bu dizinin uzunluğunun her zaman 15 olduğuna dikkat edelim — toplam 12 şişe almak için dizide 12 tane 1 olmalı. Dört farklı çeşidi ayırabilmek için de üç tane ayraç olmalı. Geriye şu kalıyor: Uzunluğu 15 olan ve tam üç tane sıfır içeren kaç dizi vardır?

Sıfırların yerini bulmamız yeter — 12 tane 1’in arasına 3 tane 0 yerleştirdiğimiz anda geçerli bir meyve suyu seçimi elde ederiz. Başka bir deyişle: 15 gözümüz var ve bunlardan 3’ünü sıfırla doldurmamız gerekiyor. Kalan gözleri otomatik olarak birlerle doldururuz.

Bu, artık tekrarsız kombinasyon ile çözülen basit bir soru. 15 gözü {1, …, 15} sayılarıyla numaralandırırız ve bu kümeden üçer sayı seçeriz; böylece sıfırı yerleştireceğimiz üç sıra numarasını buluruz. Örneğin {2, 4, 7} seçimi için şu diziyi elde ederiz: 101011011111111. 2., 4. ve 7. yerde sıfır var, geri kalanı birdir. Demek ki

$$(\genfrac{}{}{0ex}{}{15}{3})=455$$

farklı biçimde 15 göze sıfırları yerleştirebiliriz; dolayısıyla dört farklı meyve suyu varken 12 şişeyi 455 farklı biçimde alabiliriz.

Bu düşünceyi genelleyebiliriz. Büyüklüğü n olan bir M kümesi var ve bu kümeden r’li gruplar seçiyoruz; elemanlar tekrar edebiliyor. O zaman uzunluğu n + r − 1 olan, sıfırlardan ve birlerden oluşan bir dizi kurarız (r tane 1 ve n − 1 tane 0) ve n − 1 tane sıfırı kaç biçimde yerleştirebileceğimizi buluruz. Yani tekrarlı kombinasyonların sayısı, C'(n, r) ile gösterelim, şuna eşittir:

$$C^{\prime }(n,r)=(\genfrac{}{}{0ex}{}{n+r-1}{n-1})=(\genfrac{}{}{0ex}{}{n+r-1}{r}).$$

Son düzenlemeyi, binom katsayıları arasındaki temel bağıntılar sayesinde yapabildik (bkz. kombinasyon).

Çözümlü Örnekler

1. 20 tane ücretsiz tiyatro biletini 10 emekli arasında kaç farklı biçimde dağıtabiliriz? Bu, tekrarlı kombinasyon sorusudur, çünkü bir emekli birden fazla, hatta bütün ücretsiz biletleri alabilir. Yalnızca n’nin ve r’nin ne olduğunu doğru belirlememiz gerekir. Aslında 10 emekli arasından 20’li kombinasyonlar seçiyoruz; yani uzunluğu 29 olan, 20 tane 1 ve 9 tane 0 içeren bir dizi oluşturuyoruz. Demek ki n = 10, r = 20. Sonucu şöyle buluruz:

$$C^{\prime }(10,20)=(\genfrac{}{}{0ex}{}{10+20-1}{20})=10.015.005.$$