티스토리 뷰

다음과 같은 상황을 생각해보자. $n$명의 사람이 있고, 이들 중 일부는 연인 관계를 맺고 있을수도, 그렇지 않을 수도 있다. 이 때, 연인 관계로 가능한 경우의 수는 총 얼마인가?

Thanks to: Chan Bae (이 분과 대화를 나누다 나온 이야기입니다.)

 

짚어두기. ${}_n C_r = {n \choose r}$이다.

 

여러 답이 나왔는데, 개인적으로는 마지막 답에 동의하는 바이다.

 

1. $2^{n \choose 2}$가지

$n$명의 사람으로 이루어진 simple graph를 생각하자. 두 명의 사람이 연인 관계에 있다면, 해당하는 사람 사이에 간선을 긋는다. 그러면, graph들과 연인 관계들은 1-1 대응된다. 따라서, $2^{n \choose 2}$가지가 있다.

 

2. $2^{n+1 \choose 2}$가지

1에서 만든 그래프를 생각한다. 그런데, 어떤 사람은 자신과 연인 관계에 있을 수도 있을 것이다. 따라서, loop를 가지는 것은 허용하는 것이 옳다고 할 수 있다. Multiple edge(parallel edge)는 허용하지 않고, loop를 허용한다면, 총 $2^{n+1 \choose 2}$가지가 있다.

 

3. $2^{2^n}$가지 

그런데, 3명 이상의 사람이 동시에 연인 관계를 맺고 있을 수도 있다. 세 명의 사람 $(a, b, c)$가 연인 관계에 있는 것은 $(a, b), (b, c), (c, a)$가 각각 연인 관계에 있는 상황과 다르게 취급하는 것이 자연스럽다. 따라서, $\{1, 2, \cdots, n\}$의 부분집합 가운데 연인 관계에 해당하는 부분집합을 결정하는 경우의 수인 $2^{2^n}$가지가 있다.

여기에서 본인이 한 가지 의문을 제기했는데, $A \subsetneq B$에 대해 $A$와 $B$ 모두 연인 관계일 수 있냐는 것이다. 하지만, $B \setminus A$에 있는 사람이 관계를 깰 때 관계 $B$는 깨지지만, 관계 $A$는 깨지지 않는다는 점에서 $A$와 $B$가 연인 관계로 공존하는 것이 가능하다 보는게 자연스럽다는 결론에 도달했다.

 

P.S. Multiple edge에 대한 질문

이 글을 읽은 분으로 부터 다음과 같은 질문을 받았다.

"어떤 사람들 사이의 연인 관계가 한 종류만 있다고 보는게 자연스러운가?"

즉, 다시 말해, multiple edge를 허용하는 것이 더 자연스러울수도 있다는 취지의 질문이다. 이에 대해 고민해보았으나, 허용하는 쪽과 허용하지 않는 쪽 중 어느 쪽이 더 자연스러운지는 잘 모르겠다.

Multiple edge를 허용하게 된다면, 무수히 많은 경우의 수가 있을 것이다!

'일상' 카테고리의 다른 글

제 1회 Uni-CODE 에디토리얼 및 후기  (3) 2019.11.03
연인 관계의 수에 대한 짧은 이야기  (1) 2019.10.25
위스키  (0) 2019.10.21
KAIST 9th ICPC Mock Competition 참가 후기  (0) 2019.10.04
UCPC 2019 온라인 예선 후기  (0) 2019.07.29
UCPC 2018 연습 후기  (0) 2019.07.27
댓글
댓글쓰기 폼