# Discrete mathematics question

• Feb 4th 2010, 01: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?
• Feb 4th 2010, 01: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?

Let D(4) be the number of ways in which 4 people can exchange gifts so that no one receives his own gift. Note that there are 4! ways of distributing 4 gifts among 4 people so that D(4)=4! A distribution of 4 gifts is not favorable if exactly one person receives his gift (if exactly one person receives his own gift, the other 3 won't), or if two people receive their gifts, or if everyone receives their gifts.

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.
• Feb 4th 2010, 01: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.
• Feb 4th 2010, 01: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$

• Feb 4th 2010, 01: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