Number of permutations question

Hello all,

After solving Puzzle 54 'History quiz' of The Weekly Puzzle (http://www.primroselodge.com/Playtime/ weekly_puzzles.htm) I still haven't managed in *proving* my answer correct. Perhaps one of you can help me on the part that I'm stuck on?

Essentially this puzzle is about permutations: place N items numbered from 1 to N in N places, also numbered 1 to N. Obviously there are N! ways to do that. But how many permutations are there in which of the items is in the correct place (i.e., in the place that has the same number as the item)?

I'm not going to give the solution here; see The Weekly Puzzle site for that. My question is about an observation I made, but cannot

of N numbers so that exactly i of them are in the correct location.

determined by the equations

and

By experimentation I found out that

But how can this be proved from the first two equations??

Groetjes, <><

It is quite clear that the number of permutations that leave exactly i elements fixed is (N-i)!, the number of permutations of the remaining N-i. Anyway, using the inclusion/exclusion principle, one can show that the number of permuations that fix nothing is

N!/0! - N!/1! + N!/2! - N!/3! + ... + (-1)^N N!/N! = N!(1 - 1 + 1/2! - 1/3! + ... + (-1)^N/N!)

which turns out to be the nearest integer to N!/e.

Michael Barr

[...]

Hint: expand (1 - 1)^N

[rest of post snipped]

You might want to search for articles on 'derangements'- orderings where nothing is in the right place. If D(n) is the number or derangements of n objects, then the number of combinations of n objects with exactly i in the right place is: nCi*D(n-i) ie: the number of ways to choose i correct positions, times the number of ways to derange the other (n-i) objects.

So there is a permutation fixing exactly N-1 elements?

I think you meant 'that leave at least i elements fixed'.