채색다항식의 포함배제의 원리

[chimint]

채색다항식의 포함배제의 원리에 대해서 조금만 설명해주실 수 있을까요?

m개의 색을 모두 사용하여 채색하는 경우라면 채색다항식을 f(x)라 했을 때 f(m)에서 mCm-1곱하기f(m-1)이면 충분할 것 같은데 왜 포함배제가 되어야 하는지 잘 이해가 안가네요.알려주시면 감사할 것 같아요.

[현웅임용관리자1]

채색다항식 P(G, x)의 정의는 그래프G의 꼭짓점을 x개 이하의 색으로 채색하는 방법의 수 입니다.
현재 f(m)-(mCm-1)f(m-1) 을 계산하면 f(m-1)에서 각 m-2, m-3, m-4 , ... 에 해당하는 색을 선택하여 색칠하는 방법이 중복이 일어나게 됩니다.

예를들어 5가지 의 색 (빨, 주, 노 ,초 ,파) 만 이용하여 색칠한 방법의 수를 구할 때
선생님의 의견대로 하면 5가지 이하의 색으로 색칠하는 방법의 수 에서
5곱하기 4가지 이하의 색으로 색칠한 방법의 수를 뺍니다.
4가지 이하의 색으로 색칠하는 방법 중
4 가지 (빨,주,노,초), (빨,주,노,파), (빨,주,초 ,파),(빨,노,초,파),(주,노,초,파) 에서
3가지를 선택하는 방법((빨, 주, 노) , (빨, 주 ,초) , ... , (노, 초, 파))모두 중복이 2번씩 일어나게 됩니다.
f(5) - (5C4)f(4)에서 색 3가지를 선택하여 칠하는 방법의 수가 한 번 더 빠지기 때문에
f(5) - (5C4)f(4)+(5C3)f(3)를 계산하게 됩니다.

마찬가지로 계속 중복이 일어나게 되어 포함배제의 원리를 적용하게 됩니다!