Probability of selecting a particular set, by sampling without replacement from a categorical distribution
For each $\Sigma \subseteq [k+1]$, you can compute the probability $q(\Sigma)$ that the first $|\Sigma|$ elements to appear are $\Sigma$ using the following recurrence: $q(\emptyset) = 1$ and when $\Sigma \neq \emptyset$,
$$
q(\Sigma) = \sum_{\sigma \in \Sigma} q(\Sigma-\sigma) \frac{p_\sigma}{p_\sigma + \sum_{\tau \notin \Sigma} p_\tau}.
$$
You are interested in $q([k])$. The total computation time is $O(k2^k)$ (ignoring arithmetic), if you compute the sum in the denominator in tandem. Perhaps this could be improved to $O(2^k)$.