Yazar: Ümit Işlak (umitislak@gmail.com)
Yıl: 2022-2
Sayı: 112
Model ve ana sorularımız
Bu yazıda sizleri çocukluğuma götüreceğim. 1996 yılında Almanya’da düzenlenen Euro 1996 futbol turnuvası Türkiye açısından özel bir önem taşıyordu. Fatih Terim yönetimindeki A Millilerimiz tarihinde ilk defa Avrupa şampiyonasına katılmanın heyecanını yaşamaktaydı. O zamanlar 11 yaşında olan ben ise sağdan soldan bulduğum tüm parayla tek bir amaç için uğraşıyordum: Euro 1996 kataloğunu tamamlayabilmek.
16 takımın katıldığı bu turnuvada her takım için 18 kart olmak üzere toplam $16 \cdot 18 = 288$ kartı toplamam gerekliydi. Topladım da! Bu, yine tamamlamış olduğum Dünya Kupası Fransa 1998 kataloğumla beraber halen annemlerin evinde durur. Ne büyük başarı! O zamanlar tabii bu kataloğu tamamlayabilmek için aşağı yukarı kaç lira harcamam gerekeceğini matematiksel olarak sorgula(ya)mıyordum ama bunu bugün sizlerin huzurunda artık gerçekleştirebilirim! İlk olarak kupon toplama probleminin bizim tartışacağımız durumdaki modeline bakalım.
Belirli bir turnuvaya katılan $m$ futbolcunun resimlerini düşünelim. Bu resimler bir sakızın içinden çıkmakta. Herhangi bir sakız paketi bu $m$ futbolcu resminin her birini $1/m$ olasılıkla içermekte. Ayrıca herhangi bir sakız paketinde çıkacak resimin geçmişte elde ettiğimiz tüm resimlerden bağımsız olduğunu varsayıyoruz.
Tabii hemen fark edeceğiniz üzere bu modelde ufak bir sorun var! Gerçek hayatta bu kataloğu toparlamak isterseniz her futbolcunun resmi eşit olasılıkla çıkmayacaktır, zira oyunu düzenleyen firma bazı futbolcu resimlerinden görece az üreterek kataloğu tamamlamaya çalışan oyuncuların bu işe daha fazla para yatırmasını sağlayacaktır. Biz bu yazıda gerçek hayattaki bu durumu göz ardı edip her resmin eş olasılıkla çıktığını varsayacağız, belki bir başka yazıda sizlere daha genel bir çerçeveden de bahsederim.
Peşinde olduğumuz oldukça ünlü sorularımız bizim durumumuzda şunlar.
Kupon toplama problemi.
$m$ ve $n$ doğal sayılar olsun.
(i) $\;m$ farklı futbolcu resminden oluşan koleksiyonun tümünü tamamlayana kadar sakız aldığımızı düşünelim. Koleksiyonun tümüne ilk defa $n$. sakızı aldığımız zaman ulaşma olasılığı nedir?
(ii) $\;m$ farklı futbolcu resmini toplamak için almamız gereken sakız sayısının beklenen değeri nedir?
Sorumuzu biraz daha net bir şekilde ifade edebilmek için, $m$ futbolcu resminden oluşan koleksiyonu tamamlamak için almamız gereken sakız sayısına $T$ diyelim ve $n \in \mathbb{N}$ için $q_n = \mathbb{P}(T=n)$ tanımlayalım. Yani $q_n$, $T$’nin $n$’ye eşit olması olasılığı. O halde ilk kısımda $q_n$ olasılığını bulmak istiyoruz. İkinci kısımda bulmak istediğimiz değerse $T$ rassal değişkeninin beklenen değeri $$\mathbb{E}[T] := \sum_{n=0}^{\infty} n q_n.$$
Bu iki hesaplamayı yapabilmek için sizi renkli bir gezintiye çıkaracağım ve gezimizde üreteç fonksiyonlar, olasılık üreteç fonksiyonları ve ikinci tip Stirling sayılarından bahsedeceğiz. Haydi başlayalım!
Üreteç fonksiyonlar
Ana sorularımıza cevap verebilmek için üreteç fonksiyonlardan yararlanacağız. Bu bölümde özellikle olasılık üreteç fonksiyonlarına odaklanarak kısa bir tekrar yapalım. İlk olarak verilen bir $a_n$, $n=0,1,2,\ldots$ dizisine denk düşen (sıradan) üreteç fonksiyonun $$F(x) = \sum_{n=0}^{\infty} a_ n x^n$$ olarak tanımlandığını hatırlayalım. Verilen bir $F(x)$ üreteç fonksiyonunda ${x^k} F(x)$, $F(x)$’de $x^k$’nin katsayısını gösteriyor olacak. Yani $${x^k} \sum_{n=0}^{\infty} a_n x^n = a_k\ .$$
Bir örnek olarak verilen bir $r $ reel sayısı için $a_n = r^n$ ($n \geq 0$) dizisinin üreteç fonksiyonu şu şekilde verilir:
$$\sum_{n=0}^{\infty} r^n x^n = \frac{1}{1\, -\, r x}\ . \tag{1}$$
Bunu görmek için $$\begin{split} \left( \sum_{n=0}^{\infty} r^n x^n \right) (1 \,-\, rx) =\,&(1+ r x+ r^2 x^2 + r^3 x^3 + \cdots) (1 \,-\, r x)\\ =\,&1+r x+r^2 x^2 + r^3 x^3 + \cdots – \,(r x + r^2 x^2 + r^3 x^3+ \cdots)\\ =\,&1 \end{split}$$ eşitliklerini gözlemlememiz yeterli. $\{\cdot\}$ sembolümüzse bu örnekte her $k \geq 0$ için $\{x^k\} \frac{1}{1- rx} = r^k$ olduğunu söylemekte. Yine bu sembolümüzle $\{x^k\} x^m \frac{1}{1 -r x} = \{x^{k-m}\} \frac{1}{1-rx} = r^{k-m}$ olduğunu da kolayca görebiliriz.
Üreteç fonksiyonların tarihi oldukça eskilere gitmekte olup temelde çeşitli sayma problemlerinde ve yineleme çözümlerinde kullanılırlar. Ancak kullanım sahaları aslında çok daha geniştir. [8] referansı üreteç fonksiyonlara dair oldukça ilginç uygulamalar içeren bir hazine. Bizim bu yazıda ihtiyacımız olacak olan özel bir durum ise olasılık üreteç fonksiyonları.
Tanım 1. $X$, $0, 1, 2,\ldots$ değerlerini $p_0, p_1, p_2, \ldots$ olasılıkları ile alan bir rassal değişken olsun. $X$ rassal değişkeninin (ya da $\{p_n: n \geq 0\}$ olasılık dağılımının) olasılık üreteç fonksiyonu $$F(x) = \sum_{n=0}^{\infty} p_n x^n$$ olarak tanımlanır.
Örnek 1. (Düzgün dağılım) $a \in \mathbb{N}$ olmak üzere, $p_n = 1 / a$, $n = 1,\ldots,a$ olsun. Her noktaya eşit olasılık atanmasından ötürü düzgün dağılım adını verdiğimiz bu olasılık dağılımının üreteç fonksiyonu şu şekildedir: $$F(x) = \sum_{n=0}^{\infty} p_n x^n = \sum_{n=1}^a p_n x^n = \frac{1}{a} \left(x + x^2 + \cdots + x^a \right)= \frac{1}{a} \left(\frac{x- x^{a+1}}{1 \, -\, x} \right).$$ Bu, $(1)$ eşitliğine benzer şekilde gösterilebilir. $\square$
$0,1,2,\ldots$ değerlerini sırasıyla $p_0, p_1, p_2, \ldots$ olasılıkları ile alan bir $X$ rassal değişkeninin beklenen değerinin $$ \mathbb{E}[X] = \sum_{n=0}^{\infty} n \mathbb{P}(X = n) = \sum_{n=0}^{\infty} n p_n$$ şeklinde tanımlandığını hatırlayalım. Olasılık üreteç fonksiyonlar bir rassal değişkenin beklenen değerini bulmak için şu şekilde kullanılabilir.
Teorem 1. $X$, $0, 1, 2,\ldots$ değerlerini $p_0$, $p_1$, $p_2, \ldots,$ olasılıkları ile alan bir rassal değişken, $F(x)$ de bu dağılıma denk düşen olasılık üreteç fonksiyon olsun. Bu durumda $$ \mathbb{E}[X] = F'(1).$$
İspat. $F(x) = \sum_{n=0}^{\infty} p_n x^n $ olduğunu hatırlayıp, $$F'(x) = \sum_{n=0}^{\infty} n p_n x^{n -1}$$ eşitliğini gözlemlersek $$F'(1) = \sum_{n=0}^{\infty} n p_n = \mathbb{E}[X] $$ buluruz. $\square $
İkinci tip Stirling sayıları
Kupon toplama problemimize yaklaşırken üreteç fonksiyonların yanında ikinci tip Stirling sayılarına da ihtiyacımız olacak. Bu sayı tipi şu soruya cevap vermek için ortaya atılmıştır: $n$ elemanlı bir küme $k$ tane boş olmayan altkümeye kaç farklı şekilde ayrılabilir?
Tanım 2. $n$ elemanlı bir kümenin $k$ tane boş olmayan altkümeye ayrılma sayısını $S_2(n,k)$ ile gösterip ikinci tip Stirling sayısı olarak adlandıracağız.
Örneğin, $n=4$, $k=2$ iken $S_2(4,2) = 7$’dir ve bu 7 durum şu şekildedir:
$$\{12\}\{34\}, \; \{13\}\{24\}, \; \{14\}\{23\}, \; \{123\}\{4\}, \; \{124\}\{3\}, \; \{134\}\{2\}, \; \{1\}\{234\}\ .$$ Hemen görüleceği üzere $$S_2(n,n) = S_2(n,1) = 1$$ eşitlikleri doğru olur. Burada hesaplarımızda kolaylık olması amacıyla eğer $k >n$ veya $n < 0$ veya $k <0$ ise $S_2(n,k) = 0$ tanımlarını vereceğiz. Ayrıca, $$S_2(n,0) = 0, \, n \neq 0 \qquad \text{ve} \qquad S_2(0,0) = 1 \tag{2}$$ tanımlarını da yine vermiş olalım.
Daha fazla ilerlemeden tanımı hissedebilmek için şu iki önermeyi sadece tanımı kullanarak
göstermenizi öneririm: (i) $n \geq 2$ için $S_2(n,n-1) = \binom{n}{2}$, (ii) $n \geq 2$ için $S_2(n,2)= 2^{n-1}\, -\, 1$.
$S_2(n,k)$ için bir yineleme ilişkisi
$S_2(n,k)$ için asıl hedefimiz kapalı bir formül bulmak. Bu amaçla ilk olarak ilgili bir üreteç fonksiyon bulacak ve sonrasında da elde ettiğimiz üreteç fonksiyonun katsayıları aracılığıyla $S_2(n,k)$ için formülümüze ulaşacağız. Bir yineleme ilişkisi çıkararak başlıyoruz.
$[n] := \{1,2,\ldots,n\}$ kümesi $k$ tane boş olmayan altkümeye ayrıldığında oluşan altkümeler kümesine $[n]$’nin bir (küme) parçalanışı diyeceğiz. Örneğin, $n = 4$, $k=2$ iken $$\{\{1,3\}, \{2,4\} \},$$ $[4] = \{1,2,3,4\}$ kümesinin parçalanışlarından bir tanesi.
Şimdi, $n$ ve $k$ herhangi iki pozitif tamsayı olsun. $S_2(n,k)$ için yinelemeyi elde etmek için kullanacağımız fikir $[n]$’nin $k$ tane altkümeli parçalanışlarını belirli bir kurala göre iki gruba ayırmak olacak. İlk grupta $[n]$’nin $k$ gruba ayrıldığı ve $n$’nin olduğu altkümede $n$’den başka eleman olmadığı durumu düşünelim. İkinci grupta ise tabii ki $n$’nin olduğu altkümede başka elemanların da olduğu parçalanışları değerlendireceğiz. Bu iki olası duruma ayrı ayrı bakarsak durum şöyle.
Birinci durum kolay. Burada, $\{n\}$ tek başına durduğu için $[n-1]$’i $k-1$ gruba ayırmamız gerekli. Bunu da $S_2(n-1,k-1)$ farklı şekilde yapabiliriz.
$n$’nin yalnız olmadığı durumda ise $n$’yi sildiğimiz zaman $[n-1]$’in $k$ gruba ayrıldığı bir parçalanış elde ediyoruz. Ancak dikkat etmemiz gereken nokta, $n$, bu $k$ altkümenin her birinin içinde olabileceği için, $n$’yi sildikten sonra elde edilen her parçalanış $k$ kez oluşmuş olacak. Bundan ötürü $n$’nin $k$ altkümeli parçalanışlarından $k S_2(n-1, k)$ tanesi bu gruptan olacak.
İki grubu da değerlendirerek gözlemlerimizi birleştirirsek $$ S_2(n,k) = S_2(n-1, k -1) + k S_2(n-1, k) \tag{3}$$ yineleme denklemini elde etmiş oluruz. Tanımlarımız gereği bu yinelemenin $(n,k) = (0, 0)$ dışındaki her bir $(n, k)$ ikilisi için doğru olduğunu not düşelim.
$S_2(n,k)$ için formül
Artık $S_2(n,k)$ için üreteç fonksiyon bulabilecek bir noktadayız. Verilen bir $k \geq 0$ için $F_k(x)$ fonksiyonunu $$F_k(x) = \sum_{n=0}^{\infty} S_2(n,k)x^n$$ olarak tanımlayalım. $(2)$’den ötürü $F_0(x) = 1$ olduğunu görmek kolay. Diğer $k$ değerleri için $(3)$’teki yinelememizin her iki tarafını da $x^n$ ile çarpıp $n\geq 0$ üzerinden toplarsak
$$\begin{split} \sum_{n=0}^{\infty} S_2(n,k) x^n =\,& \sum_{n=0}^{\infty} S_2(n-1,k-1) x^n + \sum_{n=0}^{\infty} k S_2(n-1,k) x^n \\ =\,& x \sum_{n=1}^{\infty} S_2(n-1,k-1) x^{n-1} +\, k x \sum_{n=1}^{\infty} S_2(n-1,k) x^{n-1} \\ =\, & x \sum_{n=0}^{\infty} S_2(n,k-1) x^{n} + k x \sum_{n=0}^{\infty} S_2(n,k) x^{n} \end{split}$$
elde ederiz ve bu da bize $$F_k(x) = x F_{k-1}(x) + k x F_k (x), \quad k \geq 1, \quad F_0(x) = 1 $$ ilişkisini verir. O halde
$$ F_k(x) =\frac{x}{1 \,-\, k x} F_{k-1}(x ), \quad k \geq 1, \quad F_0(x) = 1 \tag{4}$$
bulmuş olduk. Şimdi, $F_0(x) = 1$ olduğunu aklımızda tutup, $(4)$’te verilen yineleme ilişkisini ardı ardına uygularsak $$F_k(x) = \sum_{n=0}^{\infty} S_2(n,k) x^n = \frac{x^k}{(1 – x) (1 – 2x ) \cdots (1 – k x)} \tag{5}$$ olduğunu görebiliriz. Bu eşitliğin en sağındaki ifadeyi kısmi kesirler metodu ile ayırabilirsek sorumuz hemen hemen bitmiş olacak. Bu amaçla ilk olarak $$\frac{1}{(1 – x) (1 – 2x ) \cdots (1 – k x)} = \sum_{j=1}^k \frac{c_j}{1 – j x}$$ yazalım. Burada $c_j$’ler bulmamız gereken sayılar. $1 \leq r \leq k$ olacak şekilde bir $r$ alalım, her iki tarafı da $1 \,-\, r x$ ile çarpalım ve $x = 1/ r$ yerleştirelim. Bunu yapınca elde ettiğimiz ifade
$$\begin{split}c_r =\,& \frac{1}{(1 – 1/ r) (1 – 2 / r) \cdots (1 – (r – 1)/ r) (1 – (r + 1)/ r) \cdots (1 – k /r))} \\ =\,& (-1)^{k-r} \frac{r^{k-1}}{(r – 1)! (k-r)!} \end{split} $$ olmakta. Böylece $n \geq k \geq 1$ için1
$$ \begin{split} S_2(n,k) = \, & \{x^n\}F_k(x) \\ =\,& \{x^n\} \left(\frac{x^k}{(1 – x) (1 – 2x ) \cdots (1 – k x)} \right) \\
= \,& \{x^{n-k}\} \left(\frac{1}{(1 – x) (1 – 2x ) \cdots (1 – k x)} \right) \\
= \,& \{x^{n-k}\} \sum_{r = 1}^k \frac{c_r}{1 – r x} \\ =\,& \sum_{r= 1}^k c_r \{x^{n-k}\} \left( \frac{1 }{1 -rx} \right) \\
=\,& \sum_{r= 1}^k c_r r^{n-k} \\ =\,& \sum_{r= 1}^k (-1)^{k-r} \frac{r^{k-1}}{(r – 1)! (k-r)!} r^{n-k} \\
=\,& \sum_{r = 1}^k (-1)^{k-r} \frac{r^n}{r ! (k-r)!} \end{split}$$ elde ederiz. Aradığımız formüle ulaşmış olduk.
1Burada, $\{x^n\}F(x)$ ifadesinin, $F(x)$’e denk düşen seride $x^n$’nin katsayısı olduğunu hatırlayalım.
Teorem 2. $n \geq k \geq 1$ için $$S_2(n,k) = \sum_{r = 1}^k (-1)^{k-r} \frac{r^n}{r ! (k-r)!} \ .$$
Örneğin, $4$ elemanlı bir kümeyi 2 tane boş olmayan altkümeye $$\sum_{r=1}^2 (-1)^{2-r} \frac{r^4}{r! (2 – r)!} = (-1)^1 \frac{1^4}{1! 1!} + (-1)^0 \frac{2^4}{2! 2!} = 3$$ farklı şekilde parçalayabileceğimizi görmekteyiz!
Kupon toplama problemi
Şimdi olasılık üreteç fonksiyonlarının kupon toplama problemi üzerine uygulamasına geçebiliriz. İlk olarak modelimizi bir kez daha hatırlatalım: Bir sakızdan futbolcu resimleri çıktığını varsayalım. Olası toplam $m$ farklı resim olsun ve her bir sakızın içinde bu $m$ resimden herhangi biri diğer sakızlardan bağımsız olarak $1/m$ olasılıkla bulunsun.
Teorem 3. $q_n$ ile tüm futbolcu resimlerinden birer örnek toplamış olmak için tam olarak $n$ sakız almamız gerekmesi olasılığını gösterelim.
(i) $\;S_2(n,k)$ ikinci tip Stirling sayısı olmak üzere $$q_n = \frac{m! S_2(n-1, m-1)}{m^n}$$ olur.
(ii) $\; G(x)$ ile $q_n$ dizisinin olasılık üreteç fonksiyonunu gösterirsek
$$G(x)= \frac{(m – 1)! x^m}{(m – x) (m – 2x) \cdots (m – (m-1)x )} \ .$$
(iii) $\; m$ resimlik tüm koleksiyonu toplamak için almamız gereken sakızların sayısının beklenen değeri
$$\mu = m \left(1 + \frac{1}{2} + \cdots + \frac{1}{m} \right) \tag{6}$$ ifadesine eşit olur.
Teorem 3’ün ispatı. (i) Tüm koleksiyonu tam olarak $n$. resimde elde edeceğimiz $n$ uzunluğundaki olası resim dizilerini düşünelim. Tam olarak $n$. seferde koleksiyonu tamamladığımıza göre, $n$. seferde çektiğimiz resim ilk defa o denememizde çıkmış olmalı. Şimdi, ${1,2,\ldots,n – 1}$ kümesini (başta çektiğimiz $n-1$ resim), eğer $i$. resim tipi $j$. sakızda çıktıysa ($1 \leq i \leq m$, $1 \leq j \leq n – 1$), $j$’yi $i$. gruba koyarak $m – 1$ gruba ayıracağız. Oluşan $m -1$ grubun da boş olmayacağını not düşelim.
$n$’inci seferde çıkan resimi sabitlediğimizde, $\{1,2,\ldots,n – 1\}$ elemanlarını $m – 1$ gruba ayırmanın $(m – 1)! S_2(n-1,m-1) $ farklı yolu var. Burada, $(m – 1)!$, resim tiplerinin farklı sıralarda karşımıza çıkabilecek olmalarından kaynaklı. Sonuncu kartta $m$ farklı durum olabileceğini göz önünde bulundurduğumuzda, tüm koleksiyonu tam olarak $n$. resimde elde edebileceğimiz $m (m – 1)! S_2(n-1,m-1) = m! S_2(n – 1,m-1)$ farklı dizi olabileceğini görüyoruz. Hiçbir kısıtlama olmadığında toplam $m^n$ değişik dizi yazabileceğimiz için olasılığımız teoremde verildiği gibidir.
(ii) $(5)$’ten $S_2(n,k)$ dizisine denk düşen üreteç fonksiyonun $$F_k(x)= \sum_{n=0}^{\infty} S_2(n,k) x^n = \frac{x^k}{(1 – x) (1 – 2 x) \cdots (1 – kx)}$$ olduğunu hatırlayalım. Bu durumda
$$\begin{split} G(x) =\,& \sum_{n \geq 0} \frac{m! S_2(n-1, m-1)}{m^n} x^n \\
=\,& m! \sum_{n \geq 1} S_2(n-1, m-1) \left(\frac{x}{m} \right)^n \\
=\,& m! \frac{x}{m} \sum_{n \geq 0} S_2(n, m-1) \left(\frac{x}{m} \right)^n \\
=\,& m! \frac{x}{m} F_{m-1} \left( \frac{x}{m} \right) \\
=\,& m! \frac{x}{m} \left(\frac{x}{m} \right)^{m-1} \frac{1}{(1 – \frac{x}{m}) (1 – \frac{2x}{m}) \cdots (1 – \frac{(m – 1)x}{m})} \\
=\,& \frac{(m – 1)! x^m}{(m – x) (m – 2x) \cdots (m – (m – 1)x)} \end{split}$$ elde ederiz.
(iii) $G(x) = (m \,-\, 1)! \left(\frac{x^m}{\prod_{j=1}^{m-1} (m \,-\, j x)} \right)$ fonksiyonunun türevini aldığımızda
$$G'(x)=(m – 1)! \frac{m x^{m – 1} \prod_{j = 1}^{m – 1} (m \,-\, j x) \,-\, x^m \sum_{i=1}^{m – 1} (-i) \prod_{j \neq i} (m \,-\, jx)}{ \prod_{j=1}^{m – 1} (m \,-\, j x)^2}$$ buluyoruz. $x =1$ alıp Teorem 1’i kullanırsak cevabımız iddia ettiğimiz gibi
$$\begin{split} \mu=\,& G'(1) \\
=\,& (m \,-\, 1)! \left( \frac{m (m\, -\, 1)! + \sum_{i=1}^{m – 1} \frac{i}{m- i} (m -1)! }{((m – 1)!)^2} \right)\\
=\,& m + \sum_{i=1}^{m-1} \frac{i}{m \,-\, i} \\
=\,& m + \sum_{i=1}^{m-1} \frac{i- m + m }{m \,-\, i} \\
=\,& m – (m – 1) +m \sum_{i=1}^{m-1} \frac{1}{m -i} \\
=\,& 1 + m \left(1 + \frac{1}{2} + \cdots + \frac{1}{m- 1} \right)\\
=\,& m \left(1 + \frac{1}{2} + \cdots+ \frac{1}{m} \right)\end{split}$$ olur. $\square$
Sonuç
Ufak birkaç notla yazımızı sonlandırıyoruz. İlk olarak $1 + \frac{1}{2} + \cdots+ \frac{1}{m}$ harmonik toplamı asimptotik olarak $\ln m$ gibi davranmaktadır. Yani, $ \lim_{m \rightarrow \infty} \frac{1 + \frac{1}{2} + \cdots+ \frac{1}{m}}{\ln m} = 1$. O halde $(6)$ eşitliği büyük $m$ değerleri için satın almamız gereken sakız sayısının beklenen değerinin yaklaşık olarak $m \ln m$ olduğunu söylemekte. Benim çocukluğumdaki duruma dönersek 16 takımın 18’er futbolcusunun her birinin resimleri eş olasılıkla çıkıyor olsaydı demek ki ortalamada $$288 \times \ln (288) \approx 1631$$ sakız almam gerekirdi. Bir de olasılıkların farklı olduğu durumda bunu başardığım için kendimi tebrik mi etsem ya da başka bir şey mi yapsam karar veremedim!
Aşağıdaki tablo farklı $m$ değerleri için ortalamada ne kadar beklememiz gerektiğini gösteriyor:
| $m$ | 3 | 4 | 5 | 10 | 20 | 50 | 100 | 500 | 1000 |
| $*$ | 3.3 | 5.5 | 8 | 23 | 60 | 196 | 461 | 3107 | 6908 |
Kaynaklar
[1] DeGroot, Morris H., Mark J. Schervish. Probability and statistics. Pearson Education, 2012.
[2] Ferrante, Marco, and Monica Saltalamacchia. The coupon collector’s problem. Materials matematics: 0001-35, 2014.
[3] Boneh, Arnon, and Micha Hofri. The coupon-collector problem revisited. Purdue Univ., Dept. of Comp. Science Technical Reports, 1989.
[4] Işlak, Ümit. Ayrık Matematikte Seçme Konular I. Nesin Yayıncılık, 2022.
[5] Nesin, Ali. Sayma. Nesin Yayıncılık, 2013.
[6] Sheldon, Ross. A first course in probability. Pearson Education India, 2002.
[7] Levin, David A., Yuval Peres, Elizabeth Wilmer. Markov chains and mixing times. American Mathematical Soc., 2017.
[8] Wilf, Herbert S. Generatingfunctionology. Elsevier, 2013.
