An urn contains \(C\) colors, each represented by \(B\) balls, so the total number of balls is \(CB\). We draw \(D\) balls uniformly without replacement and ask for the expected number of distinct colors that appear in the sample. For Problem 493, the concrete parameters are \((C,B,D)=(7,10,20)\).
Let \(X\) be the number of distinct colors seen in the draw. The key observation is that the expectation can be reduced to a single probability about one fixed color, and that probability is a simple hypergeometric complement.
For each color \(j\in\{1,\dots,C\}\), define an indicator variable \(I_j\) that equals \(1\) if color \(j\) appears at least once in the sample and equals \(0\) otherwise. Then the number of distinct colors is
$$X=\sum_{j=1}^{C} I_j.$$
This reformulation turns a seemingly global counting question into a sum of very small yes-or-no events, one event for each color.
Taking expectations gives
$$\mathbb{E}[X]=\sum_{j=1}^{C}\mathbb{E}[I_j]=\sum_{j=1}^{C}\Pr(I_j=1).$$
No independence is needed here; linearity of expectation always holds. By symmetry, every color has the same chance to appear. If we write
$$p=\Pr(I_1=1),$$
then
$$\mathbb{E}[X]=Cp.$$
So the whole problem is reduced to finding the appearance probability of one fixed color.
It is easier to compute the probability that the chosen color does not appear. The total number of equally likely samples of size \(D\) is
$$\binom{CB}{D}.$$
If one particular color is missing, then all \(D\) drawn balls must come from the other \(C-1\) colors, which contribute \((C-1)B\) balls altogether. Therefore
$$q=\Pr(I_1=0)=\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
Since \(p=1-q\), we obtain
$$p=1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
Substituting \(p\) into \(\mathbb{E}[X]=Cp\) yields the exact expectation
$$\boxed{\mathbb{E}[X]=C\left(1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}\right).}$$
For the Project Euler parameters, this becomes
$$\mathbb{E}[X]=7\left(1-\frac{\binom{60}{20}}{\binom{70}{20}}\right).$$
This formula is already the mathematical solution. The remaining task is simply to evaluate it numerically in a stable way.
Directly forming the two large binomial coefficients is unnecessary. Using falling products,
$$\binom{n}{D}=\frac{n(n-1)\cdots(n-D+1)}{D!},$$
so for any \(A\) and \(N\) with \(A\le N\) we have
$$\frac{\binom{A}{D}}{\binom{N}{D}}=\frac{A(A-1)\cdots(A-D+1)}{N(N-1)\cdots(N-D+1)}=\prod_{i=0}^{D-1}\frac{A-i}{N-i}.$$
With \(A=(C-1)B\) and \(N=CB\), the missing-color probability is therefore
$$q=\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}.$$
This product form is exactly what the implementations use, because it avoids huge intermediate values and matches floating-point arithmetic naturally.
This small case is easy to verify by hand. There are \(3\) colors with \(2\) balls each, so \(6\) balls in total. For one fixed color, the probability that it is absent from the two draws is
$$q=\frac{\binom{4}{2}}{\binom{6}{2}}=\frac{6}{15}=\frac{2}{5}.$$
Hence
$$p=1-q=\frac{3}{5},\qquad \mathbb{E}[X]=3\cdot\frac{3}{5}=\frac{9}{5}=1.8.$$
A direct enumeration confirms this. Among the \(\binom{6}{2}=15\) equally likely pairs, exactly \(3\) pairs have both balls of the same color and the remaining \(12\) pairs have two different colors, so
$$\frac{3\cdot 1+12\cdot 2}{15}=\frac{27}{15}=\frac{9}{5}.$$
The C++, Python, and Java implementations all use the same formula. They first compute the total number of balls \(CB\) and the number of balls that remain after excluding one fixed color, namely \((C-1)B\).
They then evaluate the product
$$\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}$$
term by term. Each iteration contributes one factor to the probability that the chosen color is missing from the sample.
After that, the implementation takes the complement of this probability and multiplies by \(C\):
$$C\left(1-\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}\right).$$
The result is printed to nine digits after the decimal point. The C++ implementation also performs small sanity checks, including the toy example above and the edge case \(D=0\), before printing the final value.
For general parameters, the method performs exactly \(D\) multiplicative updates, so the running time is \(O(D)\) and the extra memory usage is \(O(1)\). For the actual problem instance \(D=20\), the computation is tiny. The important point is that the algorithm never enumerates samples and never builds large combinatorial tables.
Eine Urne enthält \(C\) Farben, von jeder Farbe genau \(B\) Kugeln, also insgesamt \(CB\) Kugeln. Es werden \(D\) Kugeln gleichwahrscheinlich ohne Zurücklegen gezogen. Gesucht ist der Erwartungswert der Anzahl verschiedener Farben in der Stichprobe. Für Problem 493 gelten die Werte \((C,B,D)=(7,10,20)\).
Sei \(X\) die Zahl der verschiedenen beobachteten Farben. Der entscheidende Trick besteht darin, den Erwartungswert mit Hilfe von Indikatorvariablen auf genau eine Wahrscheinlichkeit für eine feste Farbe zu reduzieren; diese Wahrscheinlichkeit ist ein einfaches hypergeometrisches Komplement.
Für jede Farbe \(j\in\{1,\dots,C\}\) definieren wir eine Indikatorvariable \(I_j\), die den Wert \(1\) annimmt, wenn Farbe \(j\) mindestens einmal vorkommt, und sonst den Wert \(0\). Dann ist
$$X=\sum_{j=1}^{C} I_j.$$
Damit wird aus einer globalen Fragestellung eine Summe vieler kleiner Ja-Nein-Ereignisse, jeweils eines pro Farbe.
Durch Erwartungsbildung erhält man
$$\mathbb{E}[X]=\sum_{j=1}^{C}\mathbb{E}[I_j]=\sum_{j=1}^{C}\Pr(I_j=1).$$
Dazu ist keine Unabhängigkeit nötig; die Linearität gilt immer. Wegen der Symmetrie haben alle Farben dieselbe Auftretenswahrscheinlichkeit. Mit
$$p=\Pr(I_1=1)$$
folgt daher
$$\mathbb{E}[X]=Cp.$$
Somit muss nur noch berechnet werden, wie wahrscheinlich das Auftreten einer fest gewählten Farbe ist.
Einfacher ist die Gegenwahrscheinlichkeit: Wie wahrscheinlich ist es, dass die gewählte Farbe gar nicht erscheint? Insgesamt gibt es
$$\binom{CB}{D}$$
gleichwahrscheinliche Stichproben der Größe \(D\). Fehlt eine bestimmte Farbe vollständig, dann müssen alle \(D\) gezogenen Kugeln aus den übrigen \(C-1\) Farben stammen, also aus insgesamt \((C-1)B\) Kugeln. Daher gilt
$$q=\Pr(I_1=0)=\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
Wegen \(p=1-q\) erhält man
$$p=1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
Setzt man \(p\) in \(\mathbb{E}[X]=Cp\) ein, so ergibt sich
$$\boxed{\mathbb{E}[X]=C\left(1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}\right).}$$
Für die Euler-Parameter wird daraus
$$\mathbb{E}[X]=7\left(1-\frac{\binom{60}{20}}{\binom{70}{20}}\right).$$
Damit ist die Mathematik im Wesentlichen abgeschlossen; anschließend muss dieser Ausdruck nur noch numerisch stabil ausgewertet werden.
Es ist unnötig, die beiden großen Binomialkoeffizienten separat auszurechnen. Mit der fallenden Produktdarstellung
$$\binom{n}{D}=\frac{n(n-1)\cdots(n-D+1)}{D!}$$
folgt für beliebige \(A\) und \(N\) mit \(A\le N\)
$$\frac{\binom{A}{D}}{\binom{N}{D}}=\frac{A(A-1)\cdots(A-D+1)}{N(N-1)\cdots(N-D+1)}=\prod_{i=0}^{D-1}\frac{A-i}{N-i}.$$
Mit \(A=(C-1)B\) und \(N=CB\) ergibt sich also
$$q=\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}.$$
Genau diese Produktform verwenden die Implementierungen, weil dadurch keine riesigen Zwischenwerte entstehen und Fließkommaarithmetik direkt ausreicht.
Dieser kleine Fall lässt sich vollständig von Hand prüfen. Es gibt \(3\) Farben mit jeweils \(2\) Kugeln, also insgesamt \(6\) Kugeln. Für eine feste Farbe ist die Wahrscheinlichkeit ihres Fehlens in zwei Zügen
$$q=\frac{\binom{4}{2}}{\binom{6}{2}}=\frac{6}{15}=\frac{2}{5}.$$
Damit gilt
$$p=1-q=\frac{3}{5},\qquad \mathbb{E}[X]=3\cdot\frac{3}{5}=\frac{9}{5}=1.8.$$
Direkte Enumeration liefert denselben Wert. Unter den \(\binom{6}{2}=15\) möglichen Paaren sind genau \(3\) einfarbig, die übrigen \(12\) enthalten zwei verschiedene Farben. Also
$$\frac{3\cdot 1+12\cdot 2}{15}=\frac{27}{15}=\frac{9}{5}.$$
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe Formel. Zuerst berechnen sie die Gesamtzahl der Kugeln \(CB\) sowie die Zahl \((C-1)B\) der Kugeln, die nach dem Ausschluss einer festen Farbe übrig bleiben.
Anschließend werten sie das Produkt
$$\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}$$
termweise aus. Jede Schleifeniteration liefert genau einen Faktor zur Wahrscheinlichkeit, dass die gewählte Farbe fehlt.
Danach wird das Komplement gebildet und mit \(C\) multipliziert:
$$C\left(1-\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}\right).$$
Das Ergebnis wird mit neun Nachkommastellen ausgegeben. Die C++-Implementierung prüft zusätzlich einen kleinen Handtest und den Randfall \(D=0\), bevor sie den Endwert ausgibt.
Für allgemeine Parameter benötigt die Methode genau \(D\) multiplikative Aktualisierungen. Damit beträgt die Laufzeit \(O(D)\) und der Zusatzspeicher \(O(1)\). Beim eigentlichen Problem ist \(D=20\), also ist die numerische Arbeit verschwindend klein. Entscheidend ist, dass weder Stichproben enumeriert noch große kombinatorische Tabellen aufgebaut werden.
Bir torbada \(C\) farklı renk vardır ve her renkten \(B\) adet top bulunur; toplam top sayısı \(CB\)'dir. Geri koymadan eşit olasılıkla \(D\) top çekiyoruz ve örnekte görülen farklı renk sayısının beklenen değerini istiyoruz. Problem 493 için parametreler \((C,B,D)=(7,10,20)\) şeklindedir.
\(X\), çekilişte görülen farklı renk sayısı olsun. Ana fikir, beklenen değeri her renk için tanımlanan gösterge değişkenlerine ayırmak ve böylece problemi tek bir sabit rengin görünme olasılığına indirmektir. Bu olasılık da basit bir hipergeometrik tamamlayıcı olayla hesaplanır.
Her \(j\in\{1,\dots,C\}\) rengi için \(I_j\) gösterge değişkenini tanımlayalım. Bu değişken, renk \(j\) en az bir kez görülürse \(1\), hiç görülmezse \(0\) değerini alır. O halde farklı renk sayısı
$$X=\sum_{j=1}^{C} I_j$$
olur. Böylece küresel bir sayım problemi, renk başına birer küçük evet-hayır olayına ayrılmış olur.
Beklenen değer alırsak
$$\mathbb{E}[X]=\sum_{j=1}^{C}\mathbb{E}[I_j]=\sum_{j=1}^{C}\Pr(I_j=1)$$
elde ederiz. Burada bağımsızlık gerekmez; lineerlik her zaman geçerlidir. Simetri nedeniyle bütün renklerin görünme olasılığı aynıdır. Eğer
$$p=\Pr(I_1=1)$$
dersek, doğrudan
$$\mathbb{E}[X]=Cp$$
sonucuna ulaşırız. Yani artık tek yapılması gereken, sabit bir rengin en az bir kez görülme olasılığını bulmaktır.
Bunu doğrudan hesaplamak yerine sabit rengin hiç görünmeme olasılığını bulmak daha kolaydır. Toplam \(D\) topluk örnek sayısı
$$\binom{CB}{D}$$
kadardır. Seçilen bir rengin hiç gelmemesi için tüm çekilişlerin geri kalan \(C-1\) renkten gelmesi gerekir; bu renklerde toplam \((C-1)B\) top vardır. Dolayısıyla
$$q=\Pr(I_1=0)=\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}$$
olur. Buradan
$$p=1-q=1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}$$
elde edilir.
\(p\) değerini \(\mathbb{E}[X]=Cp\) eşitliğine koyunca tam formül çıkar:
$$\boxed{\mathbb{E}[X]=C\left(1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}\right).}$$
Euler parametreleri için bu
$$\mathbb{E}[X]=7\left(1-\frac{\binom{60}{20}}{\binom{70}{20}}\right)$$
şeklini alır. Matematiksel çözüm aslında burada bitmiş olur; geriye sadece bu ifadeyi sayısal olarak güvenli biçimde hesaplamak kalır.
İki büyük kombinasyonu ayrı ayrı hesaplamaya gerek yoktur. Düşen çarpım gösterimini kullanırsak
$$\binom{n}{D}=\frac{n(n-1)\cdots(n-D+1)}{D!}$$
olduğundan, \(A\le N\) için
$$\frac{\binom{A}{D}}{\binom{N}{D}}=\frac{A(A-1)\cdots(A-D+1)}{N(N-1)\cdots(N-D+1)}=\prod_{i=0}^{D-1}\frac{A-i}{N-i}$$
yazabiliriz. Burada \(A=(C-1)B\) ve \(N=CB\) alınırsa
$$q=\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}$$
elde edilir. Uygulama tam olarak bu biçimi kullanır; çünkü çok büyük ara değerler oluşmaz ve kayan nokta hesabı yeterlidir.
Bu küçük örnek elle doğrulanabilir. \(3\) renk ve her renkten \(2\) top olduğundan toplam \(6\) top vardır. Sabit bir rengin iki çekilişte hiç gelmeme olasılığı
$$q=\frac{\binom{4}{2}}{\binom{6}{2}}=\frac{6}{15}=\frac{2}{5}$$
olur. O halde
$$p=1-q=\frac{3}{5},\qquad \mathbb{E}[X]=3\cdot\frac{3}{5}=\frac{9}{5}=1.8.$$
Doğrudan sayım da aynı sonucu verir. \(\binom{6}{2}=15\) olası ikilinin yalnızca \(3\) tanesi tek renklidir; kalan \(12\) tanesi iki farklı renk içerir. Dolayısıyla
$$\frac{3\cdot 1+12\cdot 2}{15}=\frac{27}{15}=\frac{9}{5}.$$
C++, Python ve Java uygulamaları aynı formülü kullanır. Önce toplam top sayısı \(CB\) ve bir sabit rengin dışarıda bırakılmasıyla kalan top sayısı \((C-1)B\) hesaplanır.
Daha sonra
$$\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}$$
çarpımı terim terim oluşturulur. Döngünün her adımı, sabit rengin hiç görünmeme olasılığına bir çarpan ekler.
Son aşamada bu olasılığın tümleyeni alınır ve \(C\) ile çarpılır:
$$C\left(1-\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}\right).$$
Sonuç dokuz ondalık basamakla yazdırılır. C++ uygulaması ayrıca küçük bir oyuncak örnek ve \(D=0\) sınır durumu üzerinde kısa doğrulamalar yapar.
Genel parametreler için yöntem tam olarak \(D\) adet çarpımsal güncelleme yapar. Bu nedenle çalışma süresi \(O(D)\), ek bellek kullanımı ise \(O(1)\)'dir. Gerçek problemde \(D=20\) olduğundan hesap son derece küçüktür. Asıl kazanım, örnekleri tek tek saymaya veya büyük kombinasyon tabloları oluşturmaya hiç ihtiyaç kalmamasıdır.
Una urna contiene \(C\) colores y cada color aparece exactamente \(B\) veces, de modo que hay \(CB\) bolas en total. Se extraen \(D\) bolas uniformemente y sin reemplazo, y se pide la esperanza del número de colores distintos observados en la muestra. En el caso de Problem 493, \((C,B,D)=(7,10,20)\).
Sea \(X\) el número de colores distintos vistos en la extracción. La idea central es escribir \(X\) como suma de variables indicadoras y reducir todo a la probabilidad de que un color fijo aparezca al menos una vez. Esa probabilidad se obtiene cómodamente mediante un evento complementario hipergeométrico.
Para cada color \(j\in\{1,\dots,C\}\), definimos una variable indicadora \(I_j\) que vale \(1\) si el color \(j\) aparece al menos una vez y \(0\) en caso contrario. Entonces
$$X=\sum_{j=1}^{C} I_j.$$
De esta forma, una pregunta global sobre cuántos colores aparecen se convierte en una suma de eventos elementales de sí o no.
Al tomar esperanza obtenemos
$$\mathbb{E}[X]=\sum_{j=1}^{C}\mathbb{E}[I_j]=\sum_{j=1}^{C}\Pr(I_j=1).$$
No hace falta independencia entre los indicadores; la linealidad siempre es válida. Como todas las clases de color son simétricas, todas tienen la misma probabilidad de aparecer. Si definimos
$$p=\Pr(I_1=1),$$
entonces
$$\mathbb{E}[X]=Cp.$$
Por tanto, el problema completo se reduce a calcular la probabilidad de aparición de un solo color fijo.
Es más fácil calcular la probabilidad contraria, es decir, que ese color fijo no aparezca. El número total de muestras de tamaño \(D\) es
$$\binom{CB}{D}.$$
Si un color concreto falta por completo, entonces las \(D\) bolas extraídas deben proceder de los otros \(C-1\) colores, que en conjunto aportan \((C-1)B\) bolas. Por ello
$$q=\Pr(I_1=0)=\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
Como \(p=1-q\), resulta
$$p=1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
Sustituyendo en \(\mathbb{E}[X]=Cp\) se llega a
$$\boxed{\mathbb{E}[X]=C\left(1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}\right).}$$
Para los valores del problema de Euler, esto se convierte en
$$\mathbb{E}[X]=7\left(1-\frac{\binom{60}{20}}{\binom{70}{20}}\right).$$
Esta ya es la respuesta matemática exacta; luego solo queda evaluarla numéricamente de manera estable.
No hace falta calcular por separado dos coeficientes binomiales enormes. Usando el producto descendente,
$$\binom{n}{D}=\frac{n(n-1)\cdots(n-D+1)}{D!},$$
se obtiene para \(A\le N\)
$$\frac{\binom{A}{D}}{\binom{N}{D}}=\frac{A(A-1)\cdots(A-D+1)}{N(N-1)\cdots(N-D+1)}=\prod_{i=0}^{D-1}\frac{A-i}{N-i}.$$
Tomando \(A=(C-1)B\) y \(N=CB\), la probabilidad de ausencia es
$$q=\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}.$$
Esta es exactamente la forma usada por la implementación, porque evita valores intermedios gigantes y encaja bien con aritmética de punto flotante.
Este caso pequeño puede verificarse a mano. Hay \(3\) colores con \(2\) bolas cada uno, así que el total es \(6\). Para un color fijo, la probabilidad de que falte en dos extracciones es
$$q=\frac{\binom{4}{2}}{\binom{6}{2}}=\frac{6}{15}=\frac{2}{5}.$$
Entonces
$$p=1-q=\frac{3}{5},\qquad \mathbb{E}[X]=3\cdot\frac{3}{5}=\frac{9}{5}=1.8.$$
La enumeración directa confirma el mismo resultado. Entre las \(\binom{6}{2}=15\) parejas posibles, exactamente \(3\) son monocromáticas y las otras \(12\) contienen dos colores distintos, de modo que
$$\frac{3\cdot 1+12\cdot 2}{15}=\frac{27}{15}=\frac{9}{5}.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma fórmula. Primero calculan el total de bolas \(CB\) y el número de bolas disponibles cuando se excluye un color fijo, es decir, \((C-1)B\).
Después evalúan término a término el producto
$$\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}.$$
Cada iteración del bucle añade un factor a la probabilidad de que el color elegido no aparezca.
Al final, toman el complemento y multiplican por \(C\):
$$C\left(1-\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}\right).$$
El resultado se imprime con nueve cifras decimales. La implementación en C++ además comprueba un caso pequeño verificable a mano y el caso límite \(D=0\) antes de producir la salida final.
Para parámetros generales, el método realiza exactamente \(D\) actualizaciones multiplicativas, así que el tiempo es \(O(D)\) y la memoria adicional es \(O(1)\). En la instancia de Euler, \(D=20\), por lo que el coste numérico es minúsculo. La ganancia real es evitar por completo la enumeración de muestras y la construcción de tablas combinatorias grandes.
一个袋子里有 \(C\) 种颜色，每种颜色恰好有 \(B\) 个球，因此总球数是 \(CB\)。现在从中等概率且不放回地抽取 \(D\) 个球，要求样本中“出现过的不同颜色数”的期望值。对于 Problem 493，参数是 \((C,B,D)=(7,10,20)\)。
记 \(X\) 为抽样后看到的不同颜色数量。这个问题最简洁的做法不是直接对颜色子集做容斥，而是把 \(X\) 写成若干指示变量之和，再把期望化简成“某个固定颜色至少出现一次”的概率。这个概率又可以通过一个很简单的补事件来得到。
对每一种颜色 \(j\in\{1,\dots,C\}\)，定义指示变量 \(I_j\)。如果颜色 \(j\) 在抽出的 \(D\) 个球中至少出现一次，则 \(I_j=1\)；如果一次都没有出现，则 \(I_j=0\)。于是不同颜色的总数就是
$$X=\sum_{j=1}^{C} I_j.$$
这样一来，原来“统计出现了多少种颜色”的整体问题，就被拆成了每种颜色各自对应的一个二值事件。
对上式取期望，可以得到
$$\mathbb{E}[X]=\sum_{j=1}^{C}\mathbb{E}[I_j]=\sum_{j=1}^{C}\Pr(I_j=1).$$
这里不需要各个 \(I_j\) 彼此独立，因为期望的线性性在任何情况下都成立。又由于每种颜色在题目中的地位完全对称，所以它们出现的概率都相同。设
$$p=\Pr(I_1=1),$$
那么立刻有
$$\mathbb{E}[X]=Cp.$$
因此，整个问题被压缩成一个单独的概率计算：固定某一种颜色，它至少出现一次的概率是多少。
直接算“出现”的概率不如先算“完全没有出现”的概率更方便。总共有
$$\binom{CB}{D}$$
种等可能的 \(D\) 球样本。如果某一种固定颜色完全缺席，那么这 \(D\) 个球只能从其余 \(C-1\) 种颜色中选出，而这些颜色一共提供了 \((C-1)B\) 个球。因此
$$q=\Pr(I_1=0)=\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
于是
$$p=1-q=1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
这个比值本质上就是一个超几何分布中的“某一类完全没被抽到”的概率。
把上式代回 \(\mathbb{E}[X]=Cp\)，就得到最终的精确表达式
$$\boxed{\mathbb{E}[X]=C\left(1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}\right).}$$
对本题的参数 \((C,B,D)=(7,10,20)\)，公式就是
$$\mathbb{E}[X]=7\left(1-\frac{\binom{60}{20}}{\binom{70}{20}}\right).$$
也就是说，数学上已经完全解决了问题；剩下的只是如何把这个表达式稳定地算成小数结果。
如果直接分别计算 \(\binom{60}{20}\) 和 \(\binom{70}{20}\)，中间量会非常大。更好的做法是利用下降乘积形式
$$\binom{n}{D}=\frac{n(n-1)\cdots(n-D+1)}{D!}.$$
因此，对任意 \(A\le N\) 都有
$$\frac{\binom{A}{D}}{\binom{N}{D}}=\frac{A(A-1)\cdots(A-D+1)}{N(N-1)\cdots(N-D+1)}=\prod_{i=0}^{D-1}\frac{A-i}{N-i}.$$
取 \(A=(C-1)B\)、\(N=CB\)，就得到
$$q=\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}.$$
这正是实现里采用的数值形式。它不需要构造巨大的阶乘或组合数，中间值始终保持在普通浮点范围内，因此更稳定也更直接。
这个小例子可以完全手算验证。共有 \(3\) 种颜色、每种 \(2\) 个球，所以总数是 \(6\)。对某一种固定颜色来说，两次抽取中一次都没有抽到它的概率为
$$q=\frac{\binom{4}{2}}{\binom{6}{2}}=\frac{6}{15}=\frac{2}{5}.$$
因此
$$p=1-q=\frac{3}{5},\qquad \mathbb{E}[X]=3\cdot\frac{3}{5}=\frac{9}{5}=1.8.$$
直接枚举也会得到同样的结果。因为 \(\binom{6}{2}=15\) 个等可能的二球样本中，恰好有 \(3\) 个是同色对，其余 \(12\) 个都包含两种不同颜色，所以
$$\frac{3\cdot 1+12\cdot 2}{15}=\frac{27}{15}=\frac{9}{5}.$$
C++、Python 和 Java 实现使用的是同一条公式。它们先计算总球数 \(CB\)，以及去掉一个固定颜色后剩余的球数 \((C-1)B\)。
随后逐项累乘
$$\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}$$
这个乘积。循环中的每一步都对应“固定颜色仍然没有被抽到”的一个比值因子。
乘积结束后，再取补概率并乘上颜色总数 \(C\)：
$$C\left(1-\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}\right).$$
最后把结果输出为保留九位小数的十进制数。C++ 版本还会先检查一个可以手算的小例子，以及 \(D=0\) 的边界情形，确认公式实现没有偏差。
对一般参数来说，算法只需要做 \(D\) 次乘法更新，因此时间复杂度是 \(O(D)\)，额外空间复杂度是 \(O(1)\)。在本题里 \(D=20\)，所以计算量极小。真正重要的是，这个方法完全不需要枚举抽样结果，也不需要建立任何大型组合表。
В урне есть \(C\) цветов, причём шаров каждого цвета ровно \(B\), так что всего шаров \(CB\). Из урны равновероятно и без возвращения извлекают \(D\) шаров. Требуется найти математическое ожидание числа различных цветов, попавших в выборку. В задаче Problem 493 используются параметры \((C,B,D)=(7,10,20)\).
Обозначим через \(X\) количество различных цветов, увиденных после извлечения. Ключевая идея состоит в том, чтобы представить \(X\) как сумму индикаторов и свести задачу к одной вероятности для фиксированного цвета. Эта вероятность удобно находится через дополнительное событие гипергеометрического типа.
Для каждого цвета \(j\in\{1,\dots,C\}\) введём индикатор \(I_j\), равный \(1\), если цвет \(j\) встретился хотя бы один раз, и равный \(0\), если он не встретился ни разу. Тогда число различных цветов равно
$$X=\sum_{j=1}^{C} I_j.$$
Так исходная задача о количестве разных цветов превращается в сумму простых двоичных событий, по одному на каждый цвет.
Берём ожидание и получаем
$$\mathbb{E}[X]=\sum_{j=1}^{C}\mathbb{E}[I_j]=\sum_{j=1}^{C}\Pr(I_j=1).$$
Независимость индикаторов не требуется: линейность матожидания верна всегда. По симметрии все цвета имеют одинаковую вероятность появиться. Если обозначить
$$p=\Pr(I_1=1),$$
то сразу следует
$$\mathbb{E}[X]=Cp.$$
Значит, вся задача сведена к вычислению вероятности появления одного фиксированного цвета.
Напрямую считать вероятность появления неудобно; проще сначала найти вероятность отсутствия выбранного цвета. Общее число равновероятных выборок размера \(D\) равно
$$\binom{CB}{D}.$$
Если фиксированный цвет вовсе не встретился, то все \(D\) шаров должны быть выбраны из оставшихся \(C-1\) цветов, то есть из \((C-1)B\) шаров. Поэтому
$$q=\Pr(I_1=0)=\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
Отсюда
$$p=1-q=1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
Подставляя это в \(\mathbb{E}[X]=Cp\), получаем точную формулу
$$\boxed{\mathbb{E}[X]=C\left(1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}\right).}$$
Для параметров задачи Euler это принимает вид
$$\mathbb{E}[X]=7\left(1-\frac{\binom{60}{20}}{\binom{70}{20}}\right).$$
С математической точки зрения задача на этом уже решена; остаётся лишь аккуратно вычислить выражение численно.
Вычислять два огромных биномиальных коэффициента по отдельности не нужно. Используем представление через нисходящее произведение:
$$\binom{n}{D}=\frac{n(n-1)\cdots(n-D+1)}{D!}.$$
Тогда для \(A\le N\) имеем
$$\frac{\binom{A}{D}}{\binom{N}{D}}=\frac{A(A-1)\cdots(A-D+1)}{N(N-1)\cdots(N-D+1)}=\prod_{i=0}^{D-1}\frac{A-i}{N-i}.$$
Подставляя \(A=(C-1)B\) и \(N=CB\), получаем
$$q=\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}.$$
Именно эту форму используют реализации, потому что она избавляет от гигантских промежуточных значений и естественно вычисляется в вещественной арифметике.
Этот маленький пример легко проверить вручную. Имеются \(3\) цвета по \(2\) шара каждого, то есть всего \(6\) шаров. Для одного фиксированного цвета вероятность его отсутствия в двух извлечениях равна
$$q=\frac{\binom{4}{2}}{\binom{6}{2}}=\frac{6}{15}=\frac{2}{5}.$$
Следовательно,
$$p=1-q=\frac{3}{5},\qquad \mathbb{E}[X]=3\cdot\frac{3}{5}=\frac{9}{5}=1.8.$$
Прямая проверка даёт тот же ответ. Среди \(\binom{6}{2}=15\) равновероятных пар ровно \(3\) пары одноцветные, а остальные \(12\) содержат два разных цвета, так что
$$\frac{3\cdot 1+12\cdot 2}{15}=\frac{27}{15}=\frac{9}{5}.$$
Реализации на C++, Python и Java следуют одной и той же формуле. Сначала они вычисляют общее число шаров \(CB\) и количество шаров \((C-1)B\), которое остаётся после исключения одного фиксированного цвета.
Затем поэлементно накапливают произведение
$$\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}.$$
Каждая итерация цикла добавляет один множитель к вероятности того, что выбранный цвет не встретился вовсе.
После этого берётся дополнение и результат умножается на \(C\):
$$C\left(1-\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}\right).$$
Далее число выводится с точностью до девяти знаков после запятой. В реализации на C++ дополнительно выполняются маленькие проверки: игрушечный пример и граничный случай \(D=0\).
Для общих параметров алгоритм делает ровно \(D\) мультипликативных обновлений, поэтому его время работы равно \(O(D)\), а дополнительная память равна \(O(1)\). В самой задаче \(D=20\), так что вычисление чрезвычайно маленькое. Главный выигрыш в том, что здесь нет перебора выборок и нет построения больших таблиц сочетаний.
لدينا وعاء يحتوي على \(C\) ألوان، ولكل لون \(B\) كرات، ولذلك يكون العدد الكلي للكرات هو \(CB\). نسحب \(D\) كرات عشوائياً وبدون إرجاع، والمطلوب هو القيمة المتوقعة لعدد الألوان المختلفة التي تظهر في العينة. في Problem 493 تكون القيم \((C,B,D)=(7,10,20)\).
لنرمز إلى عدد الألوان المختلفة التي ظهرت بعد السحب بالمتغير \(X\). الفكرة الأساسية هي كتابة \(X\) كمجموع لمتغيرات مؤشرية، ثم اختزال المسألة كلها إلى احتمال ظهور لون ثابت مرة واحدة على الأقل. هذا الاحتمال يُحسب بسهولة عبر الحدث المتمم ذي الطبيعة فوق الهندسية.
لكل لون \(j\in\{1,\dots,C\}\)، نعرّف متغيراً مؤشرياً \(I_j\) يساوي \(1\) إذا ظهر اللون \(j\) مرة واحدة على الأقل في السحوبات، ويساوي \(0\) إذا لم يظهر أبداً. عندئذٍ يكون عدد الألوان المختلفة
$$X=\sum_{j=1}^{C} I_j.$$
وبهذا تتحول المسألة من سؤال شامل عن عدد الألوان إلى مجموع أحداث ثنائية بسيطة، حدث واحد لكل لون.
بأخذ التوقع نحصل على
$$\mathbb{E}[X]=\sum_{j=1}^{C}\mathbb{E}[I_j]=\sum_{j=1}^{C}\Pr(I_j=1).$$
لا نحتاج هنا إلى استقلالية هذه المتغيرات، لأن خطية التوقع صحيحة دائماً. وبسبب التماثل، فاحتمال ظهور أي لون هو نفسه لأي لون آخر. إذا كتبنا
$$p=\Pr(I_1=1),$$
فإننا نحصل مباشرة على
$$\mathbb{E}[X]=Cp.$$
إذن انخفضت المسألة كلها إلى حساب احتمال ظهور لون واحد محدد.
الأسهل هو حساب احتمال عدم ظهور هذا اللون المحدد إطلاقاً. عدد العينات الممكنة ذات الحجم \(D\) هو
$$\binom{CB}{D}.$$
وإذا غاب لون ثابت تماماً، فهذا يعني أن جميع الكرات المسحوبة جاءت من الألوان الأخرى وعددها \(C-1\)، أي من بين \((C-1)B\) كرة. لذلك
$$q=\Pr(I_1=0)=\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
ومن ثم
$$p=1-q=1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}.$$
بالتعويض في العلاقة \(\mathbb{E}[X]=Cp\) نحصل على الصيغة الدقيقة
$$\boxed{\mathbb{E}[X]=C\left(1-\frac{\binom{(C-1)B}{D}}{\binom{CB}{D}}\right).}$$
وبالنسبة لقيم مسألة أويلر تصبح
$$\mathbb{E}[X]=7\left(1-\frac{\binom{60}{20}}{\binom{70}{20}}\right).$$
وهذا ينجز الحل الرياضي بالكامل؛ وما يبقى بعد ذلك هو تقييم هذه الصيغة عددياً بطريقة مستقرة.
ليس من الضروري حساب معاملي ثنائي الحد الكبيرين كلٌّ على حدة. باستخدام صيغة الجداء التنازلي
$$\binom{n}{D}=\frac{n(n-1)\cdots(n-D+1)}{D!}$$
نحصل، لأي \(A\le N\)، على
$$\frac{\binom{A}{D}}{\binom{N}{D}}=\frac{A(A-1)\cdots(A-D+1)}{N(N-1)\cdots(N-D+1)}=\prod_{i=0}^{D-1}\frac{A-i}{N-i}.$$
وباختيار \(A=(C-1)B\) و\(N=CB\) نحصل على
$$q=\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}.$$
وهذه هي الصيغة التي تعتمدها التطبيقات فعلاً، لأنها تتجنب القيم الوسيطة الضخمة وتنسجم مباشرة مع الحسابات العائمة.
هذا المثال الصغير يمكن التحقق منه يدوياً. لدينا \(3\) ألوان، ولكل لون \(2\) كرة، أي إن العدد الكلي \(6\). احتمال غياب لون ثابت تماماً في سحبتين يساوي
$$q=\frac{\binom{4}{2}}{\binom{6}{2}}=\frac{6}{15}=\frac{2}{5}.$$
ومن ثم
$$p=1-q=\frac{3}{5},\qquad \mathbb{E}[X]=3\cdot\frac{3}{5}=\frac{9}{5}=1.8.$$
والعد المباشر يؤكد النتيجة نفسها. فمن بين \(\binom{6}{2}=15\) زوجاً محتملاً، يوجد بالضبط \(3\) أزواج أحادية اللون و\(12\) زوجاً يحتوي كل منها على لونين مختلفين، ولذلك
$$\frac{3\cdot 1+12\cdot 2}{15}=\frac{27}{15}=\frac{9}{5}.$$
تستخدم تطبيقات C++ وPython وJava الصيغة نفسها تماماً. فهي تبدأ بحساب العدد الكلي للكرات \(CB\)، ثم تحسب عدد الكرات المتبقية بعد استبعاد لون ثابت واحد، أي \((C-1)B\).
بعد ذلك تُقيَّم قيمة الجداء
$$\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}$$
حداً بعد حد. كل دورة في الحلقة تضيف عاملاً واحداً إلى احتمال غياب اللون المختار من العينة.
ثم يؤخذ المتمم ويُضرب الناتج في \(C\):
$$C\left(1-\prod_{i=0}^{D-1}\frac{(C-1)B-i}{CB-i}\right).$$
وأخيراً يُطبع الناتج مع تسعة أرقام بعد الفاصلة العشرية. كما أن تنفيذ C++ يجري فحوصات صغيرة إضافية، منها المثال اليدوي أعلاه وحالة الحافة \(D=0\)، قبل طباعة النتيجة النهائية.
بالنسبة للمعاملات العامة، تنفذ الطريقة بالضبط \(D\) تحديثات ضرب، ولذلك يكون الزمن \(O(D)\) والذاكرة الإضافية \(O(1)\). وفي المسألة الفعلية لدينا \(D=20\)، لذا فالحمل العددي صغير جداً. الفائدة الجوهرية أن الخوارزمية لا تعدّ العينات واحدة واحدة ولا تبني أي جداول توافقية كبيرة.