Thread: Discrete mathematics question

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

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,

Note that I wrote "-1" because there is only one way in which everyone can receive his or her own gift.

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.

Hello, sara1234!

A little more information is needed.

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? .

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



ABCD
BCDA
BDAC
BADC
CADB
CDAB
CDBA
DABC
DCBA
DCAB