Secretary Problem: The probability of hiring exactly $k$ times The secretary problem:
We want to hire a secretary for a company. The candidates arrive one by one (randomly). The first candidate is always hired since there is no better candidate at the time. When the second candidate arrives, we compare him/her to the current secretary. If he/she is better, we fire the previous secretary and hire the new candidate. The third candidate is also compared with the current secretary and hired in place of him/her is he/she is better. This way, we interview $n$ candidates to find the best among all of them.

The question:

What is the probability that hiring occurs $k\le n$ times? (Meaning that we
  change the secretary $k-1$ times to finally find the best person)


My try:
I worked with the arrangement of the numbers $1,\dots,n$ and assumed that there is a function $f:\mathbb N\to\mathbb N$ which gives the rank of each candidate (meaning that $f(k)=1$ iff $k$-th candidate is the best one among all). So, the question is reduced to finding all of the arrangements of $f(1), f(2), \dots, f(n)$ in which $f(1)$ comes first. (For instance, $f(1), f(5), f(2), \dots, f(n) $ can be a possible arrangement which means candidate $1$ has the best quality, the $5$-th candidate is the second best and so on).
For $k=1$, among all combinations ($n!$), there is only $(n-1)!$ in which $f(1)$ comes first. (So, $P\{\mbox{Hiring only one person}\}=\frac{(n-1)!}{n!}=\frac{1}{n}$)
For $k=2$, since always the first candidate is hired, we should have $f(1)=2$ (meaning that the first candidate should be the second-best one). So, in the combination of $f(i)$'s, we should choose some number in $\{2,3,\dots,n\}$ to be the best one ($n-1$) and for arranging other numbers, we will have $(n-2)!$ cases. (Overall cases equalling $(n-1)!$ ). So, we will have $P\{\mbox{Hiring twice}\}=\frac{1}{n}$ again!
Unfortunately, with a similar argument, I get the same number ($\frac{1}{n}$) for all $k\le n$ which is obviously wrong! I do not know why this happens and how I should count the cases correctly.

Note: There are similar questions like this which uses random indicator variables and this one in which $k=n-1$. But I do not want to use random indicator variable. Instead, I wish to solve the problem by counting rules (e.g., counting the number of cases in which hiring occurs $k$ times, and dividing it by the size of sample space).
 A: I think the flaw in your reasoning is here:

For $k=2$, since always the first candidate is hired, we should have
$f(1)=2$ (meaning that the first candidate should be the second-best
one).

For $k=2$, let us say that $f(x_0) = 1$, we only need that for all $i$ with $2 \leq i < x_0$ we have $f(i) < f(1)$. This means that the first person can be the 5th best candidate, as long as only worse candidates come after him/her till we reach the best candidate.
Given this, you then need to, for each possible position of the best candidate ($2 \leq x_0 \leq n$), find what are the values possible at the first position and then find, for each, the total number of possible permutations.
ADDENDUM
Let $r_i$ be the rank of the candidate at position $i$.
As assumed above, let $x$ be the position of the rank $1$ candidate ($r_x = 1, 2\leq x\leq n$). Let $r_1$ rank of the candidate at position $1$.
We now know that the ranks of all the candidates at position $i$ such that $1<i<x$ are higher than $r_1$ to allow for only two selections, since $r_1$ is always selected and the next selection can only be at $r_x$. There needs to be, for any given $r_1$, $x-2$ such numbers at least to fit the space between position $1$ and $x$. This restricts the possible $r_1$ to $2\leq r_1\leq n-x+2$.
Now, we just need to find the possible permutations. Given any $x$ and $r_1=y$, we have precisely these many permutations possible where the first term is the number of ways to select $x - 2$ items from $n - y$ items (i.e. selecting valid $x-2$ ranks which are greater than $y$) and the remaining two terms are the number of ways to arrange the selected $x-2$ items between $1$ and $x$ and the remaining $n-x$ items after $x$:
$$\binom{n - y}{x - 2}(x-2)!(n-x)!$$
Hence, to calculate overall number we sum for all possible $x$ and $y$:
$$\sum\limits_{x=2}^{n}\sum\limits_{y=2}^{n-x+2}\binom{n - y}{x - 2}(x-2)!(n-x)!$$
This needs to be divided by $n!$ to get the probability.
PS: I am not sure if this is the correct equation. You can try comparing the result of this to the alternative solutions, and I will be happy to know the result and modify if necessary.
A: You are correct that the chance of hiring once is $\frac 1n$.  The chance of hiring twice comes from hiring the first candidate, who must not be best, then having the best candidate precede all the other ones better than the first.  If the first candidate is rank $m$, the chance of hiring two is $\frac 1{m-1}$, so the overall chance of hiring two is $\sum_{m=2}^n\frac 1n\cdot \frac 1{m-1}=\frac 1nH_{n-1}\approx \frac 1n(\ln (n-1) + \gamma)$.  $H_n$ is the $n^{th}$ harmonic number.
A: It may be easier to find the probability that after $n$ candidates you have had $k$ hirings.  Let's call this $p(n,k)$ and we start with $p(1,1)=1$ or perhaps $p(0,0)=1$.  Since the probability of hiring on the $n$th round is $\frac1n$, we can set up the recurrence $$p(n,k)=\tfrac1n p(n-1,k-1)+\tfrac{n-1}{n}p(n-1,k)$$
This is going to give us fractions involving successive division by $n$ as it increases, so we can consider $s(n,k)=n! \, p(n,k)$ to give the number of arrangements of the $n$ candidates which lead to $k$ hirings, again starting at $s(1,1)=1$ or perhaps $s(0,0)=1$ and the recurrence $$s(n,k)= f(n-1,k-1)+(n-1)s(n-1,k).$$
This is well known and produces Stirling numbers of the first kind so $$p(n,k)=\frac{s(n,k)}{n!}.$$
You can check particular values:

*

*$s(n,n)=1$ so $p(n,n)=\frac{1}{n!}$ as you would expect  if the candidates were in ascending order

*$s(n,1)=(n-1)!$ so $p(n,1)=\frac{1}{n}$ as you would expect  if the first  candidate was the best

There are closed form expressions when $k$ is close to $n$, such as

*

*$p(n,n-1) = \frac1{2(n-2)!}$

*$p(n,n-2) = \frac{3n-1}{24(n-3)!}$
while for small $k$ you may need to sum up towards $n$ such as

*

*$p(n,2) = \frac1n\sum\limits_{i=1}^{n-1}\frac1i = \frac{H_{n-1}}{n}$
and for other small $k$ you can also have sums involving generalised harmonic numbers.
