I have n pigeonholes and a large number of letters. There are 2 parts to this q:

1. I take n letters and randomly put each of them in a pigeonhole. On average, what fraction of the n pigeonholes will be non-empty (i.e. have at least 1 letter each). and investigate what happens as n tends to infinity.

2. Now the pigeonholes are empty again. I randomly put each letter into a pigeonhole and keep on going until I all pigeonholes have at least 1 letter each. On average, how many letters have I used (in terms of n) and find the limit (if it exists) as n tends to infinity.

Well, you do not mention how far your thinking took you.

>It'seems
>to quite ubiquitious and generic.

Yes, these are more or less common problems.

Assume there are n boxes into which you randomly place r balls. The probability p_m(r, n) of having m empty boxes can be approximated by the Poisson distribution

p(m, s) = e^-s·s^m/m!,

where s = n·e^-r/n. Note that s serves the math expectation for the Poisson distribution.

The rest requires an effort of course.

You can find all this in the first volume of Feller's classics or, probably, in any decent probability text.

let s(n,k) == Stirling 2nd kind == Stirling subset number

let k^r' == k^(r down) == k*(k-1)*(k-2)*...*(k-r+1)

# functions(n-set to k-set) with r-set range
= s(n,r)*k^r'

# functions(n-set to k-set)
= Sum(r=1..k, s(n,r)*k^r') = k^n

Average(r)
= Sum(r=1..k, r*s(n,r)*k^r') / Sum(r=1..k, s(n,r)*k^r')
= Sum(r=1..k, r*s(n,r)*k^r') / k^n
(this probably can be evaluated or simplified in some way)

If k=n, then:

Average(r)
= Sum(r=1..n, r*s(n,r)*n^r') / Sum(r=1..n, s(n,r)*n^r')
= Sum(r=1..n, r*s(n,r)*n^r') / n^n
(this probably can be evaluated or simplified in some way)

My references are:
-- Graham, Knuth, Pasternik,
Concrete Mathematics, 1st ed. (1989), ex.2 p.295
-- Biggs,
Discrete Mathematics, rev ed. (1989), ex.5.7.8 p.111

Let me know if you get further results.