The Wrong Letter
An individual has written k letters to each of k different friends, and addressed the k corresponding envelopes.
How many different ways are there to place every letter into a wrong envelope?
How many different ways are there to place every letter into a wrong envelope?
Labels: mathschallenge, SharedPuzzle
posted by Zaux at
12:36 PM
9 Comments:
I think its "(k-1)!"
MK
I think it's harder than that. Letter 1 can go into 1 of k-1 envelopes. If e.g. put letter 1 into envelope 2, then letter 2 can go into any of the remaining k-1 envelopes (also), so we don't get the factorial progression. I'm not saying you're wrong though.
(k-1)^k ways. But probably got the same flaw as the (k-1)! alternative.
I'll keep on pondering, I hope I see a nice way to do it.
I see what you mean. I'll try a different approach then. Thanks for the notice. All I know right now is that when there are 4 letters, there are 9 possible outcomes
MK
Some progress. I'll see if I can get a closed form expression later.
If k is the number of letters/envelopes, then let f[k] (NB [] => function brackets) be the number of ways of combining the k letters completely incorrectly.
Let the letters be a, b, c, d, e... and the envelopes be A, B, C, D, E...
There are k-1 ways of putting the first letter into an incorrect envelope. I'll use a->B for illustration. That leaves us with bcdef and ACDEF. For this case (i.e. a single letter without a corresponding envelope) be g(n) be the number of ways of getting the addresses completely wrong, where n is the number of letters. There is now 1 way to put b into A, which leave cdef and CDEF and so f(k-2) ways of doing that, and (k-2) putting b into another envelope, which leaves e.g. cdef and ADEF and so g(k-2) ways of doing that.
Altogether, f[k] = (k-1)g[k-1] = (k-1)(f(k-2) + (k-2)g[k-2])
But see that f[k-1] = (k-2)g[k-2] {examine first half of above to see this}.
So f[k] = (k-1)(f[k-1] + f[k-2]).
If k = 1, then there are no ways to get the addressing completely wrong. If k = 2 then there is only 1 way to get the addressing completely wrong. If k = 3, then there are only 2 ways to get the addressing completely wrong. No contradictions seem to have been encountered. Can now use this to develop a table.
Starting at k = 0, we get f[k] = 0,0,1,2,9,44,265,1854,...
Outstanding Chris ... the source came up with the same analysis and provided only the results you provided.
Continuing the table, from k = 8 =>
14833, 133496, 1334961, 14684570,...
The last was f(11). But 11!/f[11] = 2.71828... approx = e (Euler's constant].
So suspect that f[k] -> k!/e as k -> infinity.
So f[k] -> k!(1/0! - 1/ 1! + 1/2! + 1/3! - 1/4! + ...)
So f[k] -> k!(1/2! - 1/3! + 1/4! - 1/5! +...)
After scratching about on a sheet of paper, I found f[2] = 2!(1/2!) = 1, f[3] = 3!(1/2! - 1/3!) = 2, f[4] = 4!{1/2! - 1/3! + 1/4!) = 9 etc., - nice!
So f[k] = k!(1/2! - 1/3! + ... (-)^k/k!) {needs k > 1}
OK not closed form, but pretty good. I don't think I can do any better than that.
Hi Zaux. I didn't see your post when I made my last one. I can't tell you how relieved I am to hear that I got it right - it took me quite a while to get that recursion formula.
My last one was based on playing with the numbers. Finding the exponential asymptote, yet alone the truncated exponential series, was pure grind and luck. I'm quite amazed that I got there.
After a bit more fiddling, using the series formula, I get a slightly improved recursion formula:
f[k] = k*f[k-1] + (-1)^k
Post a Comment
Links to this post:
Create a Link
<< Home