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

. 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)!