.

Printable View

- Dec 10th 2010, 10:04 AMzukiasMathematical thinking proof question about derangements
.

- Dec 10th 2010, 11:48 AMSoroban
Hello, zukias!

Quote:

. .

. .

This is the way it was explained to me . . .

We have this set of objects: . . in their original positions.

For the first position, there are choices for the replacement for

Suppose it is . .We have: .

What is placed in the second space?

There are two basic choices:

. . [1] isplaced in the second space.*not*

. . [2]placed in the second space.*is*

[1] Suppose isin the second space.*not*

. . .Then we have objects to derange.

. . .There are: . ways.

[2] Ifin the second space, we have: .*is*

. . . and has swapped places; they are already deranged.

. . .We must derange the other objects: . ways.

Hence, if is in the first space,

. . there are: . possible derangements.

Since there are choices for , the number of derangements is:

. .

- Dec 10th 2010, 12:38 PMAlso sprach Zarathustra
Also...

With Inclusion method you can prove the following: