곱의 법칙

원문 보기: https://dawoum.duckdns.org/wiki/곱의_법칙

합의 법칙과 곱의 법칙의 차이점은

• 합의 법칙은 사건이 종료된 개별적인 경우의 수 중에서 동일한 것이 있는지 여부를 판단하는 것이 주입니다.
• 반면에 곱의 법칙은 전체 사건이 둘 이상의 부분 사건으로 구별된다는 점입니다. 또는 사건이 연이어서 발생하는 경우에 적용합니다.

예를 들어, 학교에서 집으로 돌아갈 때, 버스 노선이 3개 있고, 지하철 노선이 4개 있으면, 학교에서 집으로 오는 경우의 수는 3+4=7가지입니다. 한편, 학교에서 도서관을 거쳐서 집으로 오는 경우의 수를 구할 때에는 학교에서 도서관까지 가는 경우의 수와 도서관에서 집으로 오는 경우의 수의 곱의 법칙을 적용합니다. 이것은 합의 법칙에서 사용했던 순서쌍과 같습니다. 합의 법칙에서의 순서쌍은 전체 순서쌍에서 조건에 맞는 순서쌍을 찾는 반면에 곱의 법칙은 순서쌍 전체 개수가 경우의 수입니다. 즉, 학교에서 도서관까지 버스 노선이 3개 있고, 도서관에서 집으로 오는 지하철 노선이 4개 있으면, 3×4=12가지의 경우의 수가 있습니다.

양의 약수의 개수와 양의 약수의 총합

360의 양의 약수의 개수는 몇 개일까요? 물론 매우 큰 숫자가 아니기 때문에 일일이 세어서 경우의 수를 구할 수도 있습니다.

1×360, 2×180, 3×120, ... 몇 개일까요?

그러나 보다 큰 숫자에 대해 이런 방법이 쉽게 끝나지 않을 수도 있습니다. 양의 약수가 만들어지는 경우를 확인하기 위해서 소인수분해를 합니다.

• \(360=2^3 \times 3^2 \times 5\)

양의 약수는 소인수분해를 했을 때, 만들어지는 소수를 몇 개 선택하느냐에 따라 1개의 약수가 결정됩니다. 즉,

• 2는 0개에서 3개까지 선택할 수 있고,
• 3은 0개에서 2개까지 선택할 수 있고,
• 5는 0개에서 1개까지 선택할 수 있습니다.

예를 들어, 2는 1개, 3은 2개 5는 0개 선택되면,

• \(2^1 \times 3^2 \times 5^0 = 18\)

이 만들어집니다.

그러므로 양의 약수의 개수는

• (3+1)×(2+1)×(1+1)=24가지 입니다.

양의 약수의 총합은 다음과 같이 구해집니다.

• \((2^0+2^1+2^2+2^3)(3^0+3^1+3^2)(5^0+5^1)\)

이 식을 전개했을 때 만들어지는 것이 양의 약수 전체이고, 덧셈으로 연결되기 때문에, 이 식의 값이 양의 약수의 합입니다. 그러나, 이 단원에서는 다루어지지 않고, 등비수열의 합에서 다루어집니다.

지불 방법과 지불 금액의 수

천 원짜리 지폐 2장, 오백원짜리 동전 3개, 100원짜리 동전 3개의 일부 또는 전부를 사용하여 돈을 지불할 때, 지불하는 방법의 수는 몇 가지일까요?

이것의 위의 양의 약수의 개수와 비슷합니다. 즉, 천원짜리 지폐의 경우 내지 않는 경우를 포함해서 (2+1)개의 가짓수가 있으므로, 나머지 동전에서도 같은 규칙을 사용하면,

• (2+1)×(3+1)×(3+1)–1 입니다.

여기서 마지막에 1을 빼주는 것은 아무것도 선택하지 않으면, 지불하지 않는 경우이기 때문입니다. 양의 약수와 차이가 나는 부분입니다.

한편, 지불할 수 있는 금액의 수는 몇 가지일까요? 이런 경우는 두 가지로 나누어서 생각할 수 있습니다. 천 원짜리 지폐 2장, 오백 원짜리 동전 1개, 100원짜리 동전 3개 였다면, 앞에서 구한 방법과 같은 방법으로 경우의 수를 구할 수 있습니다.

• (2+1)×(1+1)×(3+1)–1

그러나, 원래처럼, 천 원짜리 지폐 2장, 오백 원짜리 동전 3개, 100원짜리 동전 3개로 지불할 수 있는 금액의 수는 몇 가지일까요? 여기서는 중복이 생깁니다. 예를 들어, 오백원짜리 2개와 천원짜리 1개는 같은 지불 방법에서는 차이가 나지만, 지불 금액에서는 동일하기 때문입니다. 물론, 이런 겹치는 경우가 생기면, 작은 단위로 바꾸어서 적용할 수 있습니다. 즉, 천원짜리 지폐 2장을 오백원짜리로 바꾸어서, 오백원짜리 동전 7개, 100원짜리 동전 3개로 지불할 수 있는 금액의 수로 바꾸어 줄 수 있습니다.

• (7+1)×(3+1)–1

어쨌든, 대부분의 경우의 수에서 어려운 문제는 규칙이 없는 것을 구하는 경우입니다. 이런 경우에는 수형도를 그려서 개별적으로 구별되는 경우를 하나씩 세어야 합니다.

위의 지불 금액의 경우도 생각을 해보면,

• 100, 200, 300, 500, 600, 700, 800 여기까지가 백 원 단위에서 만들 수 있는 가지입니다.
• 1000, 위의 7가지가 그대로, 1100 등으로 만들어집니다.
• 2000, 위의 7가지가 그대로, 2100 등으로 만들어집니다.
• 3000, 위의 7가지가 그대로, 3100 등으로 만들어집니다.

결국 31가지로 만들어집니다.

만약 오백 원 동전이 2개밖에 없었다면, 마지막줄이

• 3000, 3100, 3200, 3000까지 만들어집니다.

이 경우는 27가지가 만들어집니다.

응용예제

응용예제1

수학여행에 가서 3일 동안 먹을 저녁 식단표를 짜려합니다. 밥, 반찬, 국으로 식단을 짜려하는데, 국의 종류는 된장찌개, 김치찌개, 콘스프, 반찬은 제육볶음, 오징어볶음, 돈까스, 밥은 현미밥, 흰쌀밥, 스파게티가 있는데, 이들 중 제육볶음과 오징어볶음은 콘스프와 같이 나오지 않고, 스파게티는 돈까스와 나와야 한다고 할 때, 만들어질 수 있는 식단표의 경우의 수는? (단, 각 메뉴는 꼭 한 번씩만 나옵니다.)

응용예제2

서로 다른 6개의 색깔로 그림과 같이 나누어져 있는 영역을 서로 구별되도록 색칠을 하려고 한다. 같은 색깔은 여러 번 색칠할 수 있을 때, 가능한 경우의 수는? 

응용예제3

그림과 같은 모양의 종이에 서로 다른 3가지 색을 사용하여 색칠하려고 한다. 이웃한 사각형에는 서로 다른 색을 칠하고, 맨 위의 사각형과 맨 아래의 사각형에 서로 다른 색을 칠한다고 할 때, 8개의 사각형에 색을 칠하는 방법의 수는?