Secretary Problem - What is the solution for $n=3,4,5$? I have been reading this page for a few days and still cannot understand the solution to the Secretary Problem. In particular, I cannot understand parts 2 and 4
It goes like this. Given the assumptions of the Secretary Problem, let $n$ be the number of candidates and let the "let $k$ go by" strategy be as follows:
We let $k-1$ candidates go by, and then select the first candidate who is better than all previous candidates. If the candidate exists, select her. Else, select the last candidate. 
$k$ can take the value of $\{ 1, 2, ... n\}$. 
Given this strategy, we compute the probability of success $p_n(k)$, using "let $k$ go by" with $n$ candidates. Here is where my question comes in:
When $n=3$, we permuate $\{x_1,x_2,x_3\}$ (the smaller the number, the better the candidate) I understand why $p_3(1)=\frac 26$ and $p_3(3)=\frac 26$ because of the $6$ permutations, $x_1$ could come into the interview first in $2$ permutations. Similarly, $x_1$ could come into the interview last in $2$ permutations. However, why is it that $p_3(2)=\frac 36$? In fact, there is another confusing point. Formally, my questions are:
Is it true that by counting the permutations, we find out the numerator of $p_i(k)$ for $i=1, \cdots, n$? If so, then why is it that $\sum_i^n p_i(k) \neq 1$?
Also, how did the author arrive at the $\frac 36$ for $p_2(k)$?
This question, of course extends to the case where $n=4$ and $n=5$. Maybe consider $n=4$ and $n=5$ and someone could derive the expressions for $p_i(k)$:
$n=4$
\begin{matrix}
k & 1 & 2 & 3 & 4 \\
p_4(k) & \frac {6}{24} & \frac {11}{24} & \frac {10}{24} & \frac {6}{24}
\end{matrix}
$n=5$
\begin{matrix}
k & 1 & 2 & 3 & 4 & 5\\
p_5(k) & \frac {24}{120} & \frac {50}{120} & \frac {52}{120} & \frac {42}{120} & \frac {24}{120}
\end{matrix}
 A: It is indeed possible to find the numerator in $p_i(k)$ by counting the permutations, as outlined below.  These don't sum to $1$ for $\sum_{k=1}^n p_i(k)$ because by changing the value of $k$ you are actually modifying your strategy, and there's no reason that the probabilities of success across different strategies should sum to $1$.
It's easiest to see why the author concluded that $p_3(2)=\frac36$ by looking at the possible orderings the three candidates could have taken:
$$\begin{matrix}
\text{Candidate order} & \text{Chosen candidate for k=2}\\
x_1,x_2,x_3 & x_3 \\
x_1,x_3,x_2 & x_2 \\
x_2,x_1,x_3 & x_1 \\
x_2,x_3,x_1 & x_1 \\
x_3,x_1,x_2 & x_1 \\
x_3,x_2,x_1 & x_2
\end{matrix}$$
Now it's plain to see that 3 of the 6 possible candidate orders resulted in the optimal choice of $x_1$.  I know inspecting all cases might seem like a dissatisfying sort of an answer, so now I'll derive the general formula for $p_n(k)$, which will hopefully provide a little more insight. 

From here on I'm going to refer to the candidates using numbers (so that $1$ represents the best candidate) since it's easier to get my head around ordering the numbers $1,...,n$ than ordering candidates $x_1,...,x_n$.
We observe that if candidate $2$ was in the first $k-1$ but candidate $1$ wasn't, then we'd be guaranteed to pick candidate $1$.  So any ordering that has $2$ in the first $k-1$ positions but not $1$ will result in the optimal choice.  The number of ways that candidate $2$ can be in the first $k-1$ without candidate $1$ being there is ${n-2\choose k-2}(k-1)!$.  This is obtained by first choosing which $k-2$ candidates will be in the first $k-1$ with candidate $2$, then picking an order for them all to be in.  After appropriately choosing and ordering the first $k-1$, we need to order the remaining $n-k+1$, which naturally is done by $(n-k+1)!$.  Thus the total number of ways for candidate $2$ to be among the first $k-1$ candidates, but not candidate $1$ is
$$(k-1)!{n-2\choose k-2}(n-k+1)!$$
Again, all of these orderings result in the optimal choice.
Now we observe that if neither $1$ nor $2$ were in the first $k-1$ but $3$ was, we'd only make the optimal choice if $1$ came before $2$ in the next $n-k+1$ numbers.  The number of ways for $3$ to be in the first $k-1$ but not $1$ or $2$ is $(k-1)!{n-3\choose k-2}$, while the number of ways for $1$ to come before $2$ in the next $n-k+1$ numbers is $(n-k+1)!\over2$, giving us
$$(k-1)!{n-3\choose k-2}(n-k+1)!\over2$$
such orderings.  And, as you might expect, the number of ways for $4$ to be in the first $k-1$ candidates, but not $1,2$, or $3$ and for $1$ to come before $2$ and $3$ in the next $n-k+1$ is
$$(k-1)!{n-4\choose k-2}(n-k+1)!\over 3$$
What we're doing is considering cases in which the best candidate in the first $k-1$ is $t$ and finding the number of orderings for each case that result in the optimal choice.  If we do this for all candidates $t$, then we'll have considered every possible case and will then have the total number of orderings that result in the optimal choice.
Thus you end up with a general formula for $p_n(k)$:
$$p_n(k)=\cases{\frac{(n-1)!}{n!} &for k=1\\\ \frac1{n!}\sum_{j=1}^{n-1}(k-1)!{{n-j-1\choose k-2}(n-k+1)!\over j}&for k>1}$$
For $p_4(k)$ we get
$$\begin{matrix}
k & 1 & 2 & 3 & 4 \\
p_4(k) & \frac {6}{24} & \frac {11}{24} & \frac {10}{24} & \frac {6}{24}
\end{matrix}$$
And for $p_5(k)$ we get
$$\begin{matrix}
k & 1 & 2 & 3 & 4 & 5\\
p_5(k) & \frac {24}{120} & \frac {50}{120} & \frac {52}{120} & \frac {42}{120} & \frac {24}{120}
\end{matrix}$$
both of which match the known solutions written in your question above.
