곱 규칙 (조합론)
1. 개요
곱 규칙은 k개의 단계로 구성된 과정을 거치는 경우의 수를 계산하는 조합론적 원리이다. 각 단계의 경우의 수를 모두 곱하여 전체 경우의 수를 구한다. 예를 들어, {A, B, C} 중 하나를 선택하고 {X, Y} 중 하나를 선택하는 경우의 수는 3 × 2 = 6가지이다. 집합론에서 곱 규칙은 기수의 곱셈을 정의하는 데 사용되며, 집합의 데카르트 곱의 농도를 계산하는 데 활용된다. 합의 규칙과 함께 기본적인 조합론적 계산 원리 중 하나이다.
| 유형 | 조합론 |
|---|---|
| 분야 | 수학 |
| 다른 이름 | 곱의 법칙 |
| 영어 이름 | Rule of product |
| 일본어 이름 | 数え上げの積の法則 (Kazoeage no Seki no Hōsoku) |
| 관련 개념 | 합의 법칙 |
| 정의 | 두 사건이 독립적으로 일어날 때, 전체 경우의 수는 각 사건의 경우의 수를 곱한 것과 같다. |
|---|---|
| 공식 | 'a' 사건의 경우의 수가 m이고, 'b' 사건의 경우의 수가 n일 때, 'a'와 'b' 사건이 동시에 일어나는 경우의 수는 m * n이다. (수식: ) |
| 예시 | 셔츠 3벌과 바지 2벌이 있을 때, 셔츠와 바지를 조합하여 입을 수 있는 총 가지 수는 3 * 2 = 6가지이다. |
| 사용 예시 | 다양한 항목에서 선택하는 경우의 수를 계산하는 데 사용된다. (예: 메뉴 선택, 비밀번호 설정 등) |
2. 정의
어떤 과정이 k개의 단계로 구성되었다고 하자. 첫째 단계의 경우의 수는 n₁이며, 둘째 단계의 경우의 수는 n₂이며, ..., k째 단계의 경우의 수는 nₖ라고 하자. 곱 규칙에 따르면, 이들을 차례대로 거치는 과정의 경우의 수는 다음과 같다.
:n₁ × n₂ × ⋯ × nₖ
3. 예시
A영어, B영어, C영어 중 하나와 X영어, Y영어 중 하나를 선택하는 것은 AX영어, AY영어, BX영어, BY영어, CX영어, CY영어 중 하나를 선택하는 것과 같다. 이 예에서 곱의 법칙은 3 × 2 = 6으로 나타낼 수 있다.
여기서 집합 A영어, B영어, C영어와 X영어, Y영어는 서로소 집합이지만, 반드시 그럴 필요는 없다. 예를 들어 A영어, B영어, C영어에서 하나를 선택하고 다시 같은 집합에서 하나를 선택하면, A영어, B영어, C영어의 원소로 구성된 순서쌍을 선택하는 것이 되므로 3 × 3 = 9가지 경우가 된다.
다른 예로, 피자를 주문할 때 도우 종류를 얇은 것 또는 두꺼운 것 2가지 중에서, 토핑을 치즈, 페퍼로니, 소시지 3가지 중에서 선택할 수 있다면, 곱의 법칙에 따라 피자 주문 방법은 2 × 3 = 6가지가 가능하다.
4. 응용
집합론에서 곱의 법칙은 기수의 곱을 정의하는 데 사용된다. 집합의 농도에 관해 다음이 성립한다.
:
여기서 는 데카르트 곱 연산이다. 이러한 각 집합은 유한 집합일 필요가 없으며, 이러한 인수의 수가 유한 개일 필요도 없다.
곱셈 규칙을 확장하여, n개의 서로 다른 유형의 객체(예: 사탕)가 있고, k개의 객체(예: 사람)가 있다고 가정해 보자. 이때 사람들이 사탕을 받을 수 있는 서로 다른 방법의 수는 다음과 같이 계산할 수 있다.
각 사람은 사용 가능한 n개의 사탕 중 어느 것이든 받을 수 있으며, k명의 사람이 있으므로, 이 작업을 수행하는 방법은 이다.