Results 1 to 3 of 3

Math Help - Combinatorics

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    23

    Combinatorics

    n guys are collecting one hat and one umbrella from the valet.

    a) In how many ways the valet can bring them back their stuff such that nobody will get both the hat and the umbrella (but they can get one of them).

    b) In how many ways the valet can bring them back their stuff such that nobody will get their hat or the umbrella (or both)?

    I've tried to solve this problem with the inclusion-exclusion prinicple, but i didn't succeed.

    Thanks for any kind of help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by rebecca View Post
    n guys are collecting one hat and one umbrella from the valet.

    a) In how many ways the valet can bring them back their stuff such that nobody will get both the hat and the umbrella (but they can get one of them).

    b) In how many ways the valet can bring them back their stuff such that nobody will get their hat or the umbrella (or both)?

    I've tried to solve this problem with the inclusion-exclusion prinicple, but i didn't succeed.

    Thanks for any kind of help
    First of all let's tackle this for 4 guys call them P1, P2, P3, and P4

    For part a) P1 can get H1 (hat) and is limitted to U2, U3, and U4; but if he gets any of H2, H3, or H4, he can get any U1, U2, U3, or U4 (set it up as a tree). That means he can get 3 alternatives if he gets H1 (his own hat) and has 4 alternatives each for getting H2, H3, or H4.

    The way I see it for each of the 4 guys you have 15 alternatives multiplied by the 4 guys gives 60 different outcomes with those constraints.

    I've tried this with n=5 and n=6 and the formula seems to come out to
    \left(n+1\right)_{3}. This means you are counting an 3 list from an n+1 set. I'm just beginning combinatorics, so let's hear more from the experts!

    That's (n+1)! / ((n+1) - 3)!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by rebecca View Post
    n guys are collecting one hat and one umbrella from the valet.

    a) In how many ways the valet can bring them back their stuff such that nobody will get both the hat and the umbrella (but they can get one of them).

    b) In how many ways the valet can bring them back their stuff such that nobody will get their hat or the umbrella (or both)?

    I've tried to solve this problem with the inclusion-exclusion prinicple, but i didn't succeed.

    Thanks for any kind of help
    a) Inclusion-exclusion should work.

    Start by counting the total number of ways in which hats and umbrellas can be assigned to the guys, without any restriction.

    Then say an arrangement has "property i" if guy #i gets both his hat and umbrella. Use PIE to find the number of arrangements which have none of the forbidden properties.

    Does that help?
    Last edited by awkward; May 2nd 2010 at 12:01 PM. Reason: Added a)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 20th 2010, 02:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 08:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 05:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 10:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum