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