I am solving CSES Problem set! And I came across a question where We are given N people and each one of them possesses a single gift and they have to distribute gifts among themselves, The only condition is that No one can gift himself ! in other words everyone will receive a gift only from someone else , Calculate ways for this distribution.
Approach I Tried- This seems to be an easy cliched question of Permutation and Combinations a slight variation of Handshake Problem , what I tried was using the counting principle was starting from the first person He will have (N-1) choices to distribute gift he has , further for the second person two cases arise Either second person will have N-2 choices to distribute his gift ( he can't gift himself and also can't gift to that person who Person Number One chose ) , the next case for second Person arises that the first person gifted to this very person so Now He will have (N-1) choices to distribute his gift! It seems like I can find a recurrence relation and attempt to write it down for some value of N , But am not able to deduce a more mathematical solution relying only on principles of Permutations and Combinations , Please help me out in this question :)
PS - While attempting this question it can be understood in another way in terms of graph theory where the question Just requires us to tell number of different graphs possible for a given number of vertices with conditions that
- No self edges are allowed
- All edges are directed
- The graph has only one single connected component
Solving it in terms of graph theory indeed be an exciting way But am not able to move forward