Let us suppose that we have a group of $n$ people. Where $n\in\Bbb Z^+$. Now we have a relation of friendship in the set. In the relation there is no three people which know each other and no three people which do not know each other. How can we count the number of such relations?

It is clear that when $n\ge 6$ the number of relations is $0$. But how to compute the number of relations when $n<6$ I still do not know.

  • $\begingroup$ Use \geq or \ge to produce $\ge$ or \geqslant to produce $\geqslant$. Make sure to use $\$$ at the beginning and end of the LATEX. If we wanted to write that zero is less than $n$ and $n$ is an integer then we could write n\in\Bbb Z^- which generates $n\in\Bbb Z^-$ or n\in\Bbb Z_{<0} to produce $n\in\Bbb Z_{<0}$ or without advanced notation, we would write 0 < n\in\Bbb Z to produce $0<n\in\Bbb Z$. If you use $\Bbb J$ to denote the set of integers, replace Z with J. $\endgroup$ – Mr Pie Feb 5 '18 at 8:06
  • $\begingroup$ @user477343, thanks for the attention. I will keep it in mind. $\endgroup$ – oobarbazanoo Feb 5 '18 at 21:41

It is really good you noticed that for $n \ge 6$, there is no such relations. For $n \le 5$, my suggestion is to find number of graphs for each $n$, up to isomorphism first, then try to permute the people. For all the cases when $n \le 5$, I put a figure that shows every graph that can be constructed such that there is no cycle of length $3$ neither in original graph nor in the complement:

enter image description here

Case $n = 1$ is trivial since there is only $1$ such relation.

Case $n = 2$, they are either friends or not so there are $2$ such relations.

Case $n = 3$, there are either two friendships or one as shown. But each different placed edge will give a distinct relation. So for the first, we may have edges $\{12\}, \{13\}, \{23\}$, that is, $\binom{3}{1} = 3$ different relations. For the second one, again, we have $\binom{3}{2} = 3$ different relations so in total we have $6$ here.

Case $n = 4$, for the first graph, if we fix $1$, it can be friend with $2$ and $4$, $3$ and $4$, or $2$ and $3$. So there are $3$ different relations. For the second graph, if we fix $1$, it can be friend with $2$, $3$ or $4$ while for each case, there are $2$ different relations so there are $2 \cdot 3 = 6$ possible relations (for $1$ being friend with $2$, we may switch $3$ and $4$. That's why we have two different relations for each case). But when we fix $1$, $1$ always has one friend but it may have $2$ friend as well. So there are $12$ different relations on this graph . In the last one, similar argument to the first graph, we have $3$ different relations. Therefore in total, we have $3+12+3 = 18$ different relations here.

Case $n = 5$: If we fix $1$, since $1$ has two friends, we can choose them with $\binom{4}{2} = 6$ different ways. Then for rest of the two, we can switch their places. So there are $6 \cdot 2 = 12$ different relations here.

Therefore, we have $1+2+6+18+12 = 39$ distinct relations for $n < 6$.

  • $\begingroup$ What does the notation mean: 2−4, 3−4 or 2−3? $\endgroup$ – oobarbazanoo Feb 5 '18 at 21:41
  • $\begingroup$ There, by $2-4$ I mean it can be friend with $2$ and $4$, that is there are edges $\{12\}$ and $\{14\}$. Now edited for convenience. $\endgroup$ – ArsenBerk Feb 5 '18 at 21:42
  • $\begingroup$ Thank you for the explanation. $\endgroup$ – oobarbazanoo Feb 5 '18 at 21:44
  • 1
    $\begingroup$ Here they got a different answer for n = 4 in the message number 8. They got 18 for n=4. Did you miss something? $\endgroup$ – oobarbazanoo Feb 5 '18 at 21:50
  • 1
    $\begingroup$ You are welcome. Thank you as well. $\endgroup$ – oobarbazanoo Feb 5 '18 at 21:57

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.