1. ## 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

2. Originally Posted by rebecca
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)!

3. Originally Posted by rebecca
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?