How to calculate pass@k

pass@k本质上是计算组合数。标准公式是一个取反公式：\(1-\frac{\binom{n-c}{k}}{\binom{n}{k}}\), assuming \(\binom{n}{k}\) means choosing k from n. And c is the number of correct solutions. \(\binom{n}{k}\)为组合数。关于组合数的基础知识，参见《组合数》。

理解取反公式

\(\frac{\binom{n-c}{k}}{\binom{n}{k}}\)算的是取到错误答案的概率，然后1减该数就是取到至少一个正确答案的概率。

\(\frac{\binom{n-c}{k}}{\binom{n}{k}}\)里面，分母是n取k的数量；分子是取k个，但是都取错的情况——从n-c个错误答案里取了k个。

直接计算

直接计算的公式为：

\begin{equation}
\frac{\sum_{i=1}^{\min(k,c)} \binom{c}{i}\binom{n-c}{k-i}}{\binom{n}{k}} \label{direct}
\end{equation}

分母是一样的，我们来研究分子。

首先看\(\binom{{\color{Blue} c}}{{\color{Red} i}}\binom{{\color{Blue} n-c}}{{\color{Red} k-i}}\)。Choosing k solutions，k个里面有i个正确答案和k-i个错误答案。

接下来，我们计算此直接公式。这里有两种情况，c>k or otherwise.

若c>k

若c>k，则\(\eqref{direct}\)等于

$$
\frac{\sum_{i=1}^{k} \binom{c}{i}\binom{n-c}{k-i}}{\binom{n}{k}}
=\frac{\left( \sum_{i=0}^{k} \binom{c}{i}\binom{n-c}{k-i}\right) – \binom{c}{0}\binom{n-c}{k-0}}{\binom{n}{k}}
$$

By Vandermonde’s identity, we get

$$
\frac{\binom{c+n-c}{k} – 1\times\binom{n-c}{k}}{\binom{n}{k}}
= \frac{\binom{n}{k} – \binom{n-c}{k}}{\binom{n}{k}}
= 1 – \frac{\binom{n-c}{k}}{\binom{n}{k}}
$$

因此，若c>k，则直接计算公式与标准公式相等。

若c<=k

若\(c\leqslant k\)，则\(\eqref{direct}\)等于

$$
\frac{\sum_{i=1}^{c} \binom{c}{i}\binom{n-c}{k-i}}{\binom{n}{k}}
= \frac{\left( \sum_{i=0}^{k} \binom{c}{i}\binom{n-c}{k-i} \right)-\left(\sum_{i=k+1}^{c} \binom{c}{i}\binom{n-c}{k-i}\right) – \binom{c}{0}\binom{n-c}{k-0} }{\binom{n}{k}}
$$

By Vandermonde’s identity, we get

$$
\frac{\binom{c+n-c}{k} -\left(\sum_{i=k+1}^{c} \binom{c}{i}\binom{n-c}{k-i}\right) – 1\times\binom{n-c}{k-0} }{\binom{n}{k}}
$$

By 组合数基础, if \(k\lt 0\) in \(\binom{n}{k}\), then \(\binom{n}{k}=0\). Thus in \(\sum_{i=k+1}^{c} \binom{c}{i}\binom{n-c}{k-i}\), every \(\binom{n-c}{k-i}\) is 0. Thus \(\sum_{i=k+1}^{c} \binom{c}{i}\binom{n-c}{k-i}=0\). Thus we get

$$
\frac{\binom{c+n-c}{k} – \binom{n-c}{k-0} }{\binom{n}{k}}
= \frac{\binom{n}{k} – \binom{n-c}{k}}{\binom{n}{k}}
= 1 – \frac{\binom{n-c}{k}}{\binom{n}{k}}
$$

因此，若\(c\leqslant k\)，则直接计算公式与标准公式相等。

所以，总的来说， 不论k和c谁大谁小，直接计算公式总是与标准公式相等。