# Discrete mathematics question

• February 4th 2010, 02:04 PM
sara1234
Discrete mathematics question
In how many ways can four gifts be exchanged so that no person receives her or his own gift?
• February 4th 2010, 02:29 PM
Roam
Quote:

Originally Posted by sara1234
In how many ways can four gifts be exchanged so that no person receives her or his own gift?

Exactly one person can receive his gift in (4,1)D(3) ways. Exactly two people can receive their gifts in (4,2)D(2) ways. So, $D(4)= 4! -(4,1)D(3)-(4,2)D(2) -1 = 24-6-8-1= 9$

Note that I wrote "-1" because there is only one way in which everyone can receive his or her own gift.
• February 4th 2010, 02:30 PM
Plato
Quote:

Originally Posted by sara1234
In how many ways can four gifts be exchanged so that no person receives her or his own gift?

That is a derangement of four items.
Look up derangements.
• February 4th 2010, 02:47 PM
Soroban
Hello, sara1234!

Quote:

In how many ways can four gifts be exchanged

Are there four people involved in the exchanging?

Does an "exchange" mean a reciprocal swap? . $A\;\begin{array}{c} \overrightarrow{ }\\ \overleftarrow{ } \end{array} \; B$

• February 4th 2010, 02:55 PM
Quote:

Originally Posted by sara1234
In how many ways can four gifts be exchanged so that no person receives her or his own gift?

Hi sara1234,

For persons A, B, C and D

If A gets B's gift and B gets A's, then C must get D's, (or C and D get own)
If A gets B's gift and B gets C's, then C must get D's again, (or D will get own)
If A gets B's gift and B gets D's, then C must get A's ( to not get own)

Only these 3 are possible for A, if A gets B's.

If we count the situations for A gets C's...
and the situation for A gets D's...

this will introduce 3+3 more.

Total

$3(3) =3^2=9$

ABCD
BCDA
BDAC