Annoying math problem

[bunsen_h]

Annoying, in large part, because I'm pretty sure that I'd have been able to solve this problem rather easily when I was an undergrad, but I haven't had to deal with this kind of math for a long time.

One of my colleagues wrote a bit of code which was supposed to fill an N-sized array with the values 0 through N-1, in a random order. Having had a brain fart, what he came up with was:

for (i = 0; i < N; i++)
{
   position = random(N);
   array[position] = i;
}

... which, as you will note, will tend to write to some array positions more than once, and miss some other array positions. (The best way of getting the array we're looking for is probably to fill the array with the values, in order, then swap each array element with some other random element.)

I got to wondering about what fraction of the array would be left untouched, on average. I think it works out to ((N-1)/N))^N . Or, if you prefer, (1 - 1/N)^N . The interesting thing is that as N gets larger, the value of the expression seems to approach a constant value, roughly 0.367... but I can't see how to find an algebraic solution to find the limiting value as N approaches infinity. I'm getting bogged down in polynomial expansions.

Math geek help, please?

(Yes, this is the kind of thing I do for fun. For some value of "fun", at any rate. As in, "it's fun to be able to get to sleep, now that I don't have that math problem itching in my brain".)

Edit 1, midnight:  Managed to coax a bit more precision out of a spreadsheet.  The value is close to 0.3678.  As found by poking at a calculator, 1/e = 0.36788... so I suspect that's the answer.  Whoopee, part marks.  I still want to find the solution.  Oh well, bed time.

Edit 2, 8:30 a.m.  Never mind.  See e, mathematical constant, history of; e, mathematical constant, applications.

Comments

[foms.livejournal.com]

It does sound like fun, even for one as untutored and unpractised as I but "as you will note?" [g]

[bunsen-h.livejournal.com]

Well, assuming that one understands that language, of course.

In English (and with a slight simplification): Given N pigeon-holes and N beans, for each bean, choose a random pigeon-hole (without checking to see if it's already occupied) and drop the bean into it. For any value of N greater than 2, you'll probably end up with at least one pigeon-hole with more than one bean in it, and therefore at least one with no bean. On average, what fraction of the holes end up with no beans?

For N = 2, the fraction is ¹/₄. For N = 3, the fraction is ⁸/₂₇; for N = 4, ⁸¹/₂₅₆; etc.

[duncanmac.livejournal.com]

Edit2 ... never mind.

Oh well ... the hat check problem, I gather ... I'm glad it did not cause derangement.