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
Best Answer
So assume $D_n$ is the answer for $n=N.$ You are going to think of the gifts as a permutation of $n$ so if the permutation given is $2341$ then person $2$ gives to $1,$ $3$ to $2,$ $4$ to $3$ and $4$ to $1.$
In order to create a recursion you want to know to which person $n$ gives a gift. So lets say that you want $n$ to give person $i$ the gift. So you have to know that all the other people are giving gifts with the desired property. Say $$a_1a_2\cdots a_i\cdots a_{n-1},$$ so you want $n$ to give the gift to the $i$-th person so you replace $a_i$ by $n$ getting $$a_1a_2\cdots \color{red}{n}\cdots a_{n-1}$$ but no body is giving a gift to $n$ :( so you make $a_i$ which is now not giving anyone a gift to $n$ and so you end up with $$a_1a_2\cdots \color{red}{n}\cdots a_{n-1}\color{blue}{a_i}.$$ Notice that you can do this with any $i$ and we know that we were having the desire property for the first $n-1$ people, this gives us $$(n-1)D_{n-1}.$$ Now, there is just a little problem. What if you want $i$ to give a gift to $n$?? Well, then you would have to assume that $a_i=i$ and use the same algorithm. Notice that all of the other $n-2$ people have to be giving gifts with the desired property, so you have $$(n-1)D_{n-2}.$$ Now, if you think about it, we have all possibilities and so $$D_n=(n-1)(D_{n-1}+D_{n-2}).$$ Be careful with the cases $D_1$ and $D_2$ and you are done.