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).
Best Answer
I think the flaw in your reasoning is here:
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.