Placing n numbered balls in n numbered cells

[Karlx]

Hi everybody.
I keep on reading Rohatgi's book "An introduction to Probability and Statistics".
Just now I am working in the following problem:
We have n cells numbered 1 to n and n balls numbered 1 to n.
We place at random the n balls in the n cells, with no cell receiving more than one ball.
I'm trying to find the probability to obtain exactly k matches, k=0,1,2,...,n.

Clearly, P(exactly n matches) = 1/n! and P(exactly (n-1) matches) = 0.
But I'm not able to find a general expression for P(exactly k matches).

Could anybody give me a hint.
Thanks.

 

[bpet]

Hint: the (n-k) non-matches form a Derangement.

 

[Outlined]

hint:
how many total configurations do you have?
how many configurations satisfy your claim?

 

[Karlx]

Thanks bpet and outlined.

I have n! total configurations.
I don't know how to calculate how many of them satisfy the condition of "exactly k matches".

Bpet, what is a derangement ?
OK, I found out what is a derangement. Good hint. I will work it out. Thanks.

 

[Fredrik]

The probability you seek is the number of ways to have exactly k matches, divided by the total number of ways to distribute the balls. The latter is clearly n! To find the former, start by finding the number of ways that k slots, specified in advance (e.g. the slots numbered 1-k), can have matching balls while the other ones don't. Then...I probably shouldn't give you more information than that.

 

[Krish@physics]

it will be (nCk)/n!

 

[Karlx]

A derangement is a permutation of the elements of a set such that none of the elements appear in their original position.
For a set of n elements, the number of possible derangements is

$$!n = n! \sum_{i=0}^n \frac{(-1)^i}{i!}$$

where !n is called the subfactorial of n.

With this information, is not difficult to see that the probability to obtain exactly k matches is
$$P(k)= (\stackrel{n}{k})\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$$

Just a remark: There is no need of knowing about derangements to solve the problem. It is possible (I did it) to solve it only using a combinatorial reasoning. Then, the derangements arise as an "intermediate result", not in the form of !n written above, but in a recursive expression.

Thanks for your help.

 

[Outlined]

it will be (nCk)/n!

I doubt this is correct

 

[Krish@physics]

yes it is

 

[Karlx]

A derangement is a permutation of the elements of a set such that none of the elements appear in their original position.
For a set of n elements, the number of possible derangements is

$$!n = n! \sum_{i=0}^n \frac{(-1)^i}{i!}$$

where !n is called the subfactorial of n.

With this information, is not difficult to see that the probability to obtain exactly k matches is
$$P(k)= (\stackrel{n}{k})\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$$

Just a remark: There is no need of knowing about derangements to solve the problem. It is possible (I did it) to solve it only using a combinatorial reasoning. Then, the derangements arise as an "intermediate result", not in the form of !n written above, but in a recursive expression.

Thanks for your help.

Sorry, there was a mistake in the expression for P(k).
The correct form is

$$P(k)= (1/k!)\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$$