이산수학 질문

[늙은악마]

이산수학 인강 수강생입니다.

질문이 있는데 Q&A에 이산수학이 없어서;;;;

3.6장에 색칠문제가 나오는데요

예제 3.6.7에서

색채다항식=k(k-1)^2(k-2)

그러므로 색채수는 3이라고 나옵니다.

여기서 질문

예제 3.6.7의 그래프를 3가지 색으로 칠하는 방법의 수는 색채다항식에 3을 대입해서 나오는 12가 답인가요?

3.6장에

연습문제 5번을 푸는데 예제 3.6.7과 같은 방식으로 풀었는데 색채다항식은 답과 일치하는데

(2)의 답은 색채다항식에 5를 대입한 1440이 나오는데 답은 720이라서 색채다항식에 수를 대입하는 것이 아닌가 의문이 들어서요.

답변 부탁드려요

[정현민]

(2)번에는 5가지색을 "모두" 사용하여.. 라고 되어 있네요. 채색 다항식은 k가지색을 모두 사용할 수도 있고 일부만 사용할 수도 있는 경우이므로 5를 대입했을 때 1440가지가 나온 것은 5가지 미만의 색으로 칠하는 경우도 포함한 것 입니다. ^^

[늙은악마]

아!! 그럼 채색다항식에 5 대입한 값에 4 대입한 값을 빼면 되는거죠?

[정현민]

아니요.. ^^; 언뜻 생각하면 c_k(5)-c_k(4)라고 생각할 수 있지만 의미를 조금 더 들여다 보면 아니라는 사실을 발견할 수 있습니다. c_k(5)는 {1,2,3,4},{1,2,3,5}...{2,3,4,5}(5가지 경우)를 사용하는 경우를 모두 포함함하므로 구하고자 하는 답은 c_k(5)-5c_k(4)=720이 됩니다.