0
$\begingroup$

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

  1. No self edges are allowed
  2. All edges are directed
  3. 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

$\endgroup$
9
  • $\begingroup$ Is this problem from an active contest? $\endgroup$ Aug 6 '20 at 15:49
  • $\begingroup$ No it is not ,I have shared the link of source $\endgroup$ Aug 6 '20 at 15:50
  • $\begingroup$ Have you heard about derangements? $\endgroup$
    – Phicar
    Aug 6 '20 at 15:53
  • $\begingroup$ I think I heard that term for the first time $\endgroup$ Aug 6 '20 at 15:55
  • $\begingroup$ This is a derangement problem. $\endgroup$ Aug 6 '20 at 16:22
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ this explanation indeed helped me Thanks for it ! I will surely accept this as an answer , but can we have a discussion about it's graph Theory aspect , now that you explained it it is a classical dearrangement question But I wonder for graphs is their a special name or type for such graphs am talking about here? ( PS One of the points I mentioned about graph theory is wrong assumption ) . $\endgroup$ Aug 6 '20 at 18:01
  • $\begingroup$ mmm instead of thinking about it as a graph, i would suggest thinking about it as a perfect matching in the complete directed graph. So that you can put in the matching opposite edges (i->j,j->i) like the second case of derangements. $\endgroup$
    – Phicar
    Aug 6 '20 at 18:13
  • $\begingroup$ Ok ! I will search about perfect matching ! thanks again for the answer $\endgroup$ Aug 6 '20 at 18:14
  • $\begingroup$ @KartikBhatia You are welcome. Look at this: arxiv.org/pdf/1306.6436.pdf $\endgroup$
    – Phicar
    Aug 6 '20 at 18:17
  • 1
    $\begingroup$ ahh my bad ! The dearrangements are indeed beautiful just now I got acquainted with the approx result involving euler number $\endgroup$ Aug 6 '20 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.