Quicksort: Probability of an element being compared to fewer than $k$ pivot elements
This is not the answer to your question, but maybe you can use some elements of it.
For $i&lt;j$, let us denote $X_{ij}$ the random variable:
$$X_{ij} = \left\{\begin{array}{rl}1 &amp; \text{if }S_{(i)}\text{ and }S_{(j)}\text{ are compared}\\0&amp;\text{otherwise}\end{array}\right.$$
and $A_{ij} = \{S_{(i)}, S_{(i+1)}, …, S_{(j)}\}$.
Since a comparison between two elements only occurs if one of them is a pivot, and since a pivot is never compared to other elements after the end of the partition occurring when it was chosen, we can conclude that:
$$\mathbb{P}(X_{ij} = 1) = \mathbb{P}(S_{(i)} \text{ first pivot in }A_{ij}) + \mathbb{P}(S_{(j)} \text{ first pivot in }A_{ij})$$
This is also due to the fact that if another element of $A_{ij}$ is chosen as first pivot, $S_{(i)}$ and $S_{(j)}$ will be put in two different parts of the partition.
Since the choice of the pivot is uniform, we get $\mathbb{P}(S_{(i)} \text{ first pivot in }A_{ij}) = \frac{1}{|A_{ij}|}$ and finaly $\mathbb{P}(X_{ij} = 1)  = \frac{2}{j - i +1}$.
Now, the expected number of comparisons where $S_{(i)}$ is involved is:
$$\begin{array}{rcl}
\displaystyle\mathbb{E}\left(\sum\limits_{j=1,j\neq i}^nX_{ij}\right) &amp; = &amp; \displaystyle\sum\limits_{j=1,j\neq i}^n\mathbb{E}(X_{ij})\\
&amp; = &amp; \displaystyle\sum\limits_{j=1,j\neq i}^n\mathbb{P}(X_{ij} = 1)\\
&amp; = &amp; \displaystyle\sum\limits_{j=1,j\neq i}^n\frac{2}{|j-i| + 1}\\
&amp; = &amp; \displaystyle\sum\limits_{j=1}^{i-1}\frac{2}{i - j +1} + \sum\limits_{j=i+1}^{n}\frac{2}{j - i +1}\\
&amp; = &amp; \displaystyle\sum\limits_{k=1}^{i-1}\frac{2}{k +1} + \sum\limits_{k=1}^{n-i}\frac{2}{k +1}\\
\end{array}$$
This analysis is generally sufficient for the analysis of the average time complexity of quicksort, because this value is $O(\log n)$. However, I am not sure as to how use part of it to find the value you want, which is:
$$\displaystyle\mathbb{P}\left(\sum\limits_{j = 1, j\neq i}^n X_{ij} = k\right)$$
Also it is not so clear that for $j\neq j'$, $X_{ij}$ and $X_{ij'}$ are independant (since for example $X_{ij}$, $X_{ij'}$ and $X_{jj'}$ are not independant because at most two of the three could be $1$).