1.3 경우의 수

어떤 확률실험의 사상과 관련된 실현치들의 수를 샐 때 유용한 방법을 나열한다.

 

곱의 원리(Multiplication principle)

 실험 𝐸_1에서 𝑛_1개의 실현치가 발생되고, 그러한 각각의 실현치에 대해 실험 𝐸_2로 부터 𝑛_2개의 가능한 실현치들이 발생되면 𝐸_1과 𝐸_2를 차례대로 시행하는 복합실험 𝐸_1 𝐸_2는 𝑛_1 * 𝑛_2개의 발생 가능한 실현치들을 갖는다.

 위의 원리는 각각의 실험이 순차적으로 발생했을때, 그 경우의 수를 따지는 것이다. 만약 그 순서라는게 중요하지 않다면 실현치들의 곱으로 나타내어지지 않을 것이다. 이제 이를 응용해 다양한 상황에서의 경우의 수를 따져보자.

 

순열(Permutation)

 𝑛개의 "서로 다른" 개체에 대한 𝑛! 가지의 배열 각각을 순열이라고 한다. 여기서 𝑛𝑃𝑟 개의 배열 각각을 n개의 개체 중 r개를 선택하여 배열한 순열이라 부른다. 즉, 순열은 r개의 순서쌍 하나이다.

 모든 것은 개체(객체)로 이루어져 있음을 잊지 말자. - OOP

 𝑛개의 개체를 포함하고 있는 집합으로부터 "순서를 고려"하여 𝑟 개의 개체를 추출할 때, 선택된 𝑟개의 개체 집합을 크기 𝑟인 순서표본(ordered sample of size 𝑟)이라고 한다. 즉, ordered sample of size 𝑟은 r 개의 원소를 가지는 순서쌍"들"의 집합이다. 위와 다른점은 이는 "집합"이라는 개념 아래에서 순열을 만들어 그 순열을 가지고 있는 집합이라는 점이다.

 이때 개체를 추출하는 방식이 추출하고 다시 그 개체를 돌려 놓으면서 추출하는 방식을 복원추출(sampling with replacement)라고 한다. 그 반대로 다시 돌려 놓지 않으면 비복원추출(sampling without replacement)라고 한다.

 순서를 고려하면서 비복원추출이라면 그 경우는 다음과 같고, 이를 중복순열(permutation with repetition) 이라고 부른다.

조합(Combination)

 𝑛𝐶𝑟 = (n r)^T 개의 "비순서" 부분집합 각각을 𝑛개의 개체중 𝑟개를 선택하는 조합이라고 한다. 즉, 조합 또한 r개의 순서쌍 하나이다(구별가능한 순열이라고도 부른다). 그렇다면 비순서표본 또한 다음과 같이 정의가 가능하지 않을까?

 𝑛개의 개체를 포함하고 있는 집합으로부터 순서를 고려하지 않고 𝑟개의 개체를 추출할 때, 선택된 𝑟개의 개체 집합을 크기 𝑟인 비순서표본(unordered sample of size 𝑟)이라고 한다.

보통 (n r)^T는 이항계수(binomial coefficient)라고 불리는데, 이항전개에서 유래된다.

 조합을 배열로 볼 수도 있는데, 예를 들어 a, a, a, a, b, b, b 7자리를 배열해야 한다고 하자. 7자리의 번호를 각각 부여하고, 각각을 개체에게 할당해주는 것으로 보자. 그러면 7𝐶4의 경우의 수가 나온다(b는 자동으로 할당).

 

다항계수(multinomial coefficient)

 위를 확장시켜보자. 𝑛개의 개체를 갖고 있는 집합에서 그 중 𝑛_1, 𝑛_2, ... 𝑛_𝑠 개의 각기 다른 종류가 섞여 있다고 하자. (𝑛_1 + 𝑛_2 + ... + 𝑛_𝑠 = 𝑛). 이때 𝑛개의 구별되는 배열의 가지수는 다음과 같다.

 문자만 다를 뿐 같은 연산이다.

 

중복조합(multiset coefficient)

 𝑛개의 개체를 포함하는 집합으로부터 순서를 고려하지 않고 𝑟개의 개체를 중복을 허용하여 추출할 때, 추출된 𝑟개의 순서쌍을 중복조합이라고 한다.

첫줄만 기억해도 문제 없다.

 

1.3-1 자물쇠 조합을 모른다고 하자. 정확한 조합은 4자리 숫자로 𝑑_1𝑑_2𝑑_3𝑑_4이며, 𝑖 = 1, 2, 3, 4에 대해 𝑑_𝑖는 1, 2, 3, 4, 5, 6, 7, 8 중에 한 숫자다. 이 자물쇠 조합의 가지수는?
𝑠𝑜𝑙'𝑛) 8개의 서로 다른 개체에 대해 "순서를 고려"하고, 뽑은 개체는 다시 돌려 놓는 복원 추출이다. 따라서 중복순열 이므로
8Π4 = 8^4 = 2^12 = 4096 가지이다.

1.3-2 미국의 어느 주에서 다음과 같은 경우에 발행 가능한 자동차 번호판의 가지수는?
a) 처음에 두 개의 문자와 다음에 네 자리 정수(첫머리에 0도 가능하며 문자들과 숫자들이 반복될 수 있음)로 이루어진 경우.
𝑠𝑜𝑙'𝑛) 곱의 법칙으로 6가지의 사건이 연달아 발생하는 상황으로 해석할 수 있다.
26 × 26 × 10 × 10 × 10 × 10 = 6760000 가지이다.

b) 처음에 세 개의 문자와 다음의 세 자리 정수로 이루어진 경우.
𝑠𝑜𝑙'𝑛) 위의 문제와 동일하게 사건의 실현치만 조금 달라질 뿐이다.
26 × 26 × 26 × 10 × 10 × 10 = 17576000 가지이다.

1.3-3 "HOPE"라는 단어 속에 있는 문자를 이용해 다음의 경우 만들 수 있는 5문자 암호의 개수는?
a) 문자들이 중복되지 않음.
𝑠𝑜𝑙'𝑛) {'H', 'O', 'P', 'E'}의 집합에서 순서를 고려하여 4개의 개체를 비복원 추출하는 것을 생각하면 된다.
따라서 4 𝑃 4 = 4! = 24가지 이다.

b) 문자들이 중복될 수 있음.
𝑠𝑜𝑙'𝑛) 이번엔 복원추출이다.
4 Π 4 = 4^4 = 256가지 이다.

1.3-4 0~9까지의 숫자를 한 자리씩 복원으로 추출하여 4자리 숫자를 구성하여 당첨 숫자를 결정하는 복권을 생각해보자. 당첨 복권의 숫자가 가지고 있는 숫자의 순열 중 하나이면 당첨이 된다고 하자. 가지고 있는 숫자가 다음과 같을 때 당첨될 확률은?
a) 6, 7, 8, 9
𝑠𝑜𝑙'𝑛) 당첨의 경우는 한가지 뿐이다. 그리고 만들 수 있는 숫자는 4개의 서로 다른 개체를 순서를 고려하여 배열하는 것이므로 4 𝑃 4 로 24가지이다. 따라서 확률은 1/24 이다.

b) 6, 7, 8, 8
𝑠𝑜𝑙'𝑛) multinomial coefficient이다.
4!/(1!1!2!) = 12 이다.

c) 7, 7, 8, 8
𝑠𝑜𝑙'𝑛) 4!/(2!2!) = 6

d) 7, 8, 8, 8
𝑠𝑜𝑙'𝑛) 4!/3! = 4

1.3-5 어떤 경기의 결승전에서 두 팀 중 먼저 4경기를 이긴 팀이 우승할 때, 결승전 경기 수가 다음과 같았을 때 승패에 있어서 얼마나 많은 경우가 있었겠는가?
a) 4 게임.
𝑠𝑜𝑙'𝑛) 이기는 경우를 "W", 지는 경우를 "L"라고 할 때, 가능한 사상의 경우는 𝑆 = { 𝑊, 𝐿 } 이고, 4게임만에 승부가 나려면 한쪽이 모두 지거나 이겨야 한다. 따라서 중복순열 (W, W, W, W), (L, L, L, L)이 되겠다. 2가지 경우이다.

b) 5 게임
𝑠𝑜𝑙'𝑛) 위의 경우에서 다른 종류 하나를 추가한 형태인데, 그것이 맨 끝일 수는 없다. 따라서 사이사이의 자리에 끼워 넣지만 마지막의 자리를 뺀 자리 중에서 1개를 택하는 경우이다. 즉 이는 4개의 번호가 있는 좌석 중에 한 종류의 한 개체를 넣는 것이므로 4 𝐶 1이다. 따라서 4+4 = 8 가지이다.

c) 6 게임
𝑠𝑜𝑙'𝑛) 이번엔 다르게 풀어보자. A종류의 개체 2개, B종류의 개체 4개가 있다고 하자. 순서를 고려하여 나열하는 경우는 6!/2!4! = 15일터이다. 이때, A종류와 B종류에 서로 다른 개체 W, L을 할당하는 것은 비복원의 순열과도 같다. 따라서 15*2 𝑃 1 = 30 이며, 이제 6게임 이전에 결판이 나는 경우를 빼면 되겠다. 6게임 이전에 먼저 결판이 나버리는 사상을 C라고 했을때 𝑛(C) = 𝑛(4게임에 결판이 경우) + 𝑛(5게임에 결판이나는 경우)라고 하는 것은 자명하다. 따라서 30 - 2 - 8 = 20 가지 이다.

d) 7 게임
𝑠𝑜𝑙'𝑛) 𝑤𝑖𝑡ℎ𝑜𝑢𝑡 𝑙𝑜𝑠𝑠 𝑜𝑓 𝑔𝑒𝑛𝑒𝑟𝑎𝑙𝑖𝑡𝑦, 2 × 7!/(3!4!) - 2 × 6!/(2!4!) = 40

1.3-6 한 카페에서 주문하는 대로 샌드위치를 만든다. 빵이 6가지, 고기가 4가지, 치즈가 4가지, 12가지의 소스가 있다고 했을 때, 다음과 같이 선택한다면 서로 다른 샌드위치를 얼마나 많이 만들 수 있는가?
a) 빵 1, 고기 1, 치즈 1, 𝑠𝑜𝑙'𝑛) 6𝐶1 × 4𝐶1 × 4𝐶1 = 96
b) 빵 1, 고기 1, 치즈 1, 0~12 양념
𝑠𝑜𝑙'𝑛) 96 × (12𝐶0 + 12𝐶1 + ... 12𝐶12) (∵ binomial coefficient)
= 96 × (1 + 1)^12 = 393216
c) 빵 1, 0~2 고기, 0~2 치즈, 0~12 양념
𝑠𝑜𝑙'𝑛) 6𝐶1 × (4𝐶0 + 4𝐶1 + 4𝐶2) × (1 + 4𝐻2) × (2^12)

1.3-7 52장의 잘 섞여진 카드로부터 5장의 카드를 임의로 비복원추출할 때, 다음의 확률을 구하여라
a) 4장이 같은 숫자인 경우
𝑠𝑜𝑙'𝑛) 5장 중 4장의 같은 숫자를 뽑을 경우는 A 부터 King 까지 13가지이고, 나머지 하나의 카드는 48개의 카드에서 뽑으면 된다. 순서는 고려하지 않으므로 굳이 배열을 하는 경우는 생각할 필요 없다. 따라서 13*48 이고, 총 경우는 52𝐶5이다. 따라서
𝑃(4장이 같은 숫자) = 𝑛(4장이 같은 숫자) / 𝑛(𝑆) = 624 / 2598960이다.

나머지 문제는 생략한다.