A combinatorial solution to the tool maker problem I'm trying to verify the claim presented in this question. 
Let's assume that we are interested in the following probability in both cases (i.e. sorted piles(SP) and messy heap(MH)):
The probability of choosing $k$ stones from $N$ stones with which the tool maker can make $k$ different tools.


*

*For the (SP) case:
The probability is actually one. Because we have distinct piles of each stone's type. So, one can pick one stone from each pile (Assume we have $k$ types of stone with the frequency of $n_k$ such that $\sum_{k} n_k = N$):
$P_{SP}(X) = \dfrac{{{n_1}\choose{1}}{{n_2}\choose{1}}...{{n_k}\choose{1}}}   {{{n_1}\choose{1}}{{n_2}\choose{1}}...{{n_k}\choose{1}}} = 1$

*For the (MH) case:
The selection space now is all of the stones, as there is no labelled type to any arbitrary stone. Hence:
$P_{MH}(X) = \dfrac{{{n_1}\choose{1}}{{n_2}\choose{1}}...{{n_k}\choose{1}}}   {{N}\choose{k}}$
The claim is:
$\lim_{N\to\infty} \dfrac{P_{SP}(X)}{P_{MH}(X)} = k$
Now, one can use Stirling's Approximation leading to:
$\lim_{N\to\infty} \dfrac{P_{SP}(X)}{P_{MH}(X)} = \lim_{N\to\infty} \dfrac{{N}\choose{k}}{{{n_1}\choose{1}}{{n_2}\choose{1}}...{{n_k}\choose{1}}} = \lim_{N\to\infty} \dfrac{\dfrac{N!}{k!(N-k)!}}{n_{1}*n_{2}*...*n_{k}}$
How should I proceed now?!

Update:
I myself solved the question:
Let's assume that all frequencies are the same (for the sake of simplicity):
$n_{1} = n_{2} = ... n_{k} = \psi$,
therefore, $k\psi = N \Rightarrow \psi = \dfrac{N}{k}$
$\lim_{N\to\infty} \dfrac{{N}\choose{k}}{n_{1}*n_{2}*...*n_{k}} = \lim_{N\to\infty} \dfrac{{N}\choose{k}}{(\dfrac{N}{k})^{k}}$
Now by the following approximation, we have:


*

*${{N}\choose{k}} \approx \dfrac{N^k}{k!}$ if $N\gg k$


$\lim_{N\to\infty} \dfrac{{N}\choose{k}}{(\dfrac{N}{k})^{k}} = \lim_{N\to\infty} \dfrac{\dfrac{N^k}{k!}}{\dfrac{N^k}{k^k}} = \dfrac{k^k}{k!}$  
Let $\phi = \dfrac{k^k}{k!}$
We can use the following approximation here:


*

*$\log(k!) \approx k\log k - k$,


So,
$\log \phi = \log k^{k} - \log k! = k\log k - [k\log k -k] = k$
Finally,
$\phi = exp(k)$
I should have reached to $k$, not $exp(k)$.
What's wrong with my argument?!
 A: The claim presented in the linked question is just bullshit, since the author is not in the least defining what he is talking about, let alone what his  objective function and probabilistic model is.
In this second attempt these things are made clearer. We have a large urn containing $N\gg1$ balls of $m$ different colors, whereby each color is represented with the same number of balls.
We can have slaves sort these balls into $m$ different urns, whereupon we can just take one ball out of each urn and will be in possession of a ball of each color.
If such slaves are not available we have to make random picks out of the large urn until we have seen all $m$ colors. What is the expected number of picks? We may assume that $N$ is so large that any balls picked and kept are not disturbing the involved probabilities. This is the Coupon Collector's Problem.
Denote by $E_r$ the expected number of additional picks when there are $r$ colors yet to be found. Then
$$E_0=0,\qquad E_r=1+{r\over m}E_{r-1}+{m-r\over m}E_r\quad(r\geq1)\ .$$
This leads to $$E_r={m\over r}+E_{r-1}\ ,$$ so that that
$$E_r=m\>\sum_{k=1}^r{1\over k}\ .$$
In particular
$$E_m=m\>H_m\doteq m\>\log m\qquad(m\to\infty)\ .$$
Hence for large $m$ the expected number of necessary picks is by a factor $\log m$ larger than when the slaves are available. 
A: 
the sorted architecture is roughly $k$-times more efficient than no
    architecture

means that if the sorted architecture expected time to a solution is $t$, then the messy heap can expect to solve in $kt$.
Which I'm fairly sure is nonsense, and there is nothing wrong with your argument.
