tough! how to get that M ??-about probability topic?

Question

An absentminded professor wrote n letters and sealed them in envelopes without writing the addresses on them. Then he wrote the n addresses on the envelopes at random. what's the probability that exactly K of the envelopes were addressed correctly?
What I've done is (nCk)xM/(n!) ,then I don't know how to get M. can someone help me out with the M?thanks

Answer 1

What you're asking about (M) is the number of ways of assigning m=(n-k) addresses among the same number of envelopes so that all of them are incorrect. This is called the number of derangements of m objects.

This can be derived using the inclusion exclusion principle. There are m! total permutations from which we subtract N(1->1)+N(2->2)+...+N(m->m), then add (N(1->1,2->2)+ N(1->1,3->3)+...), then subtract (N(1->1,2->2,3->3) + ...) and so on, where N(1->1) for example denotes the total number of permuations which take 1->1 (which is (m-1)!). Similarly N(1->1,2->2)=(m-2)!.

In other words the total number of ways of entirely incorrectly assigning m addresses to the corresponding m envelopes is:

m! - C(m,1)(m-1)! + C(m,2)(m-2)! + C(m,3)(m-3)! - ... + (-1)^m C(m,m)0!
= m! - m! + (m!/2!) + (m!/3!) - ...+ (-1)^m (m!/m!)
= m!(1 - 1 + 1/2! - 1/3! + ... + (-1)^m/m!)

The problem asks for the total number of ways of correctly addressing exactly k envelopes so use this formula with m=n-k (the number of incorrectly addressed envelopes) and multiply it by the number of ways of choosing the k envelopes which are destined to have correct addresses (in other words C(n,k)). This gives:

(n!/((n-k)!k!)) * (n-k)!(1 - 1 + 1/2! - 1/3! + ... + (-1)^(n-k)/(n-k)!)
=(n!/k!) * (1 - 1 + 1/2! - 1/3! + ... + (-1)^(n-k)/(n-k)!)

As an example, the number of ways of correctly addressing exactly k envelopes for n=4 are:

N(k=0) = 24 * (1/2! - 1/3! + 1/4!) = 9
N(k=1) = 24 * (1/2! - 1/3!) = 8
N(k=2) = 12 * (1/2!) = 6
N(k=3) = 4 * (1-1) = 0
N(k=4) = 1

as you can verify.

Finally, to get the probability, divide by n!:

P =(1/k!) * (1 - 1 + 1/2! - 1/3! + ... + (-1)^(n-k)/(n-k)!)

Note that when k=n-1 the formula gives zero, as it must since there's no way of correctly addressing all but one envelope.

Answer 2

First choose any k letters to address correctly: that's (nCk).
Then find how many ways to arrange the remaining n-k: that's (n-k)!.

So there are (nCk)*(n-k)! ways out of n! ways that have exactly k of the envelopes addressed correctly.

(nCk)*(n-k)!/n! simplfies to 1/k!.

Answer 3

2. might want to be a lot harder for me. it truly is a count number of opinion. in case you're sturdy at chemistry and psychology, bypass with selection a million. in case you're sturdy at stat and econ, bypass with selection 2. For me besides the undeniable fact that, selection 2 looks harder (besides the undeniable fact that they both seem really common).

Answer 4

I think once the k are written correctly, there are still (n-k)! permutations free. So the probability should be

(n-k)! / n!

Answer 5

p one success = 1/n
p(2)=1/n*1/(n-1)
p(k)= 1/n*1/(n-1)*...1/(n-k+1) = (n-k)!/n!