Results 1 to 5 of 5

Math Help - Discrete mathematics question

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    3

    Discrete mathematics question

    In how many ways can four gifts be exchanged so that no person receives her or his own gift?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Apr 2008
    Posts
    191
    Quote Originally Posted by sara1234 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,677
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by sara1234 View Post
    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.
    Last edited by mr fantastic; February 13th 2010 at 01:12 AM. Reason: No edit. Moved from a duplicate thread.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,740
    Thanks
    645
    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? . A\;\begin{array}{c} \overrightarrow{ }\\ \overleftarrow{ } \end{array} \; B

    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by sara1234 View Post
    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
    BADC

    CADB
    CDAB
    CDBA

    DABC
    DCBA
    DCAB
    Last edited by mr fantastic; February 13th 2010 at 01:12 AM. Reason: No edit. Moved from a duplicate thread.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. discrete mathematics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2010, 05:39 PM
  2. Discrete Mathematics GCD Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 5th 2010, 11:48 AM
  3. What is discrete Mathematics About ?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 4th 2009, 09:28 PM
  4. Mathematics: Discrete-Mathematics (Algorithems)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 2nd 2008, 06:27 AM
  5. Generic Question Discrete mathematics
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 11th 2007, 08:10 PM

Search Tags


/mathhelpforum @mathhelpforum