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

Printable View

- Feb 4th 2010, 01:04 PMsara1234Discrete 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 PMRoam
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, $\displaystyle 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 PMPlato
- Feb 4th 2010, 01:47 PMSoroban
Hello, sara1234!

A little more information is needed.

Quote:

In how many ways can four gifts be exchanged

so that no person receives her or his own gift?

Are there four people involved in the exchanging?

Does each person start with one gift?

Can one person to receive more than one gift?

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

- Feb 4th 2010, 01:55 PMArchie Meade
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

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

ABCD

BCDA

BDAC

BADC

CADB

CDAB

CDBA

DABC

DCBA

DCAB