3.3 영국인의 모자 문제(교란순열)
"파티에 참석한 $n$명의 영국인들이 모두 모자를 쓰고 왔다. 파티를 시작하기 전에 모자걸이에 모자를 걸어두었다. 참석자들은 다시 집으로 돌아갈 때, 쓰고 온 모자를 다시 쓰지 않는 경우는 몇 가지나 될까?" 이 문제는$n$개의 숫자 $1, 2, \cdots, n$을 일렬로 나열한 것을 $a(1), a(2), \cdots, a(n)$ 이라 할 때, $a(k)≠k$을 만족하는 경우의 수를 구하는 문제와 같다. 그리고, 이러한 순열을 '교란순열($D(n)$)'이라 하는데 좀 더 '일반화된 교란순열'은 다음과 같이 표현된다. $D(n,r,k), \ (0\leq k\leq r)$ $1\leq r\leq n$에 대하여 $r-$순열은 $1, 2, \cdots, n$에서 $r$개를 선택하여 배열한 것이다. $a(1)..
2022. 9. 13.
3.2 일반화된 포함과 배제의 원리
다음과 같은 '일반화된 포함배제의 원리'의 서술이 가능하다. 이것에 대한 일반적인 증명은 하지 않는다. 궁금한 독자는 조합론 서적을 참조하기 바란다. 집합 $S$를 $n$개의 원소를 가지는 '전체집합'이라고 하고, 성질$1, 2, \cdots, q$를 생각하자. $m=0,1,2,\cdots,q$ 에 대하여, 다음이 성립한다. $\begin{align} E(m) = \omega(m) - C(m+1,m)\cdot \omega(m+1) \\ \\+ C(m+2,m)\cdot \omega(m+2)+\cdots \\ \\ \cdots+(-1)^{q-m}\cdot C(q,m)\cdot \omega(q) \end{align}$ 식이 길고 시각적인 난해함에 매혹되어 머리가 아파지지 않도록 하자. 일반 독자에게 이런 수식..
2022. 9. 13.
