Originally posted by neilariniIt is just 1 - 1/n.
n
The series of probabilities that all letters will be in the wrong envelop is:
P = (n-1)/n * (n-2)/(n-1) * ... * 2/3 * 1/2
which reduces to
P = (n - 1)! / n! = 1/n
The probably of any given letter being in the correct envelop is the inverse:
~P = 1 - P
~P = 1 - 1/n
This is actually the same odds you get for card games like poker: "If I draw n cards, and I need to draw any one of X cards to win, what are my chances of winning?"
For 1 envelop, (n-1)! / n! doesn't quite simplify to 1/n, you're right.
P = (n-1)! / n! = 0/1
~P = 1 - 0/1 = 1
I'm trying to figure why it doesn't work for n > 3. I think because I'm double-counting certain cases like:
n = 4
3/4 chance of not drawing 1: draw 3
2/3 chance of not drawing 2: draw 4
Now there are no possible ways to match any envelope.
Consider this as all the possible permutations of n numbers. Letter to the right envelope then matches the case of some number k is at the k'th place.
n = 1: only sequence is 1. 1 / 1! = 1, so 100% chance.
n = 2: new sequences can be generated by replacing any number in any above sequence with a 2, and moving the replaced number to the end of the sequence. If it was formerly in the right place, this reduces the # of letters to the right place by one; if not, it the number of letters to the right place stays the same. OR, for any sequence above, 2 can be added to the end, increasing the # of letters to the right place by one.
Replace: 1 --> 21. reduces the # of hits to zero. "zero hits, two misses." (0,2)
Add to the end: 1 --> 12. adds the # of hits to two. "zero misses, two hits." (2,0)
n = 3:
(0,2) sequence; replace either with a three for 2x(0,3) or add 3 to the end (1,2).
(2,0) sequence; replace either with a three for 2x(1,2) or add 3 t the end (3,0)
(0,3) x2
(1,2) x3
(3,0) x1 four involve hits. 4/3! = 67%
n = 4:
(0,3)x2: replace any for 6x(0,4) or add 4 to the for 2x(1,3)
(1,2)x3: replace the only hit for 3x(0,4), replace either miss for 6x(1,3) or add the end for 3x(2,2)
(3,0): replace any hit for 3x(2,2) or add 4 to the end for (4,0).
Which yields
(0,4) x9
(1,3) x8
(2,2) x6
(4,0) x1 all but 9 include at least one hit, so 15/4! gives the likelihood.
And so on and and so forth. There is a non-trivial limit for the chance of at least one hit as n grows without limit, and the sequences approaches that value fast. Sadly, so far I haven't figured out a pretty way to get the likelihood for k envelopes in a pretty, closed form.