Experiment(실험)
확률과 통계학에서의 실험은 데이터를 생성해내는 모든 과정을 실험이라고 얘기한다. 예를들어 동전 던지기 or 주사위 던지기 or 슈퍼마켓에서 고객들이 몇 명 오는지 새는 것 이런 어떠한 데이터를 생성해내는 모든 과정을 실험이라고 한다.
The Basic Principle of Counting
Combinatorial Analysis(조합 분석)의 기본이 되는 것은 Counting의 기본 원리에서부터 시작되기 때문에 Counting에 대한 기본 원리를 예제를 통해 알아보자.
1. 두 가지 실험을 수행한다고 가정해보자.
2. 첫 번째 실험은 m개의 가능한 결과가 있다.
3. 첫 번째 실험의 각 결과에 대해 두 번째 실험은 n개의 가능한 결과가 있다.
4. 그렇다면 두 실험의 가능한 결과는 몇 가지가 있는가?
위의 그림에서 알 수 있듯이 첫 번째 실험에서 m개가 나왔고 각 m개에 대해서 n개가 나왔기 때문에 총 개수는 m * n이 된다. 그래서 총 카운팅은 첫 번째 실험에서 나온 경우의 수와 두 번째 실험에 나온 경우의 수를 곱한 것이다. 앞의 예제에서 알 수 있듯이 Counting의 기본 원리는 곱셈의 법칙으로 이루어져 있다.
※ 수학적 개수 이론은 정식으로 조합론이라고 한다.
그래서 총 가능한 모든 경우의 수는 각각의 실험으로부터 나올 수 있는 결과가 n1부터 nk까지 있다면 그것을 다 곱한 수가 된다.
ex1) 주택 개발업자가 외관 스타일은 4가지의 선택권이 있고 바닥재가 3가지의 선택권이 있다면 총 경우의 수는?
=> 4 * 3 = 12
ex2) 각 학년(1학년:10명 , 2학년: 22명, 3학년:13명, 4학년:2명)에서 1명씩 4명의 학생으로 구성된 위원회의 경우의 수는?
=> 10 * 22 * 13 * 2 = 5,720
ex3) 컴퓨터 사용자 이름이 3개의 알파벳 뒤에 5개의 숫자로 구성된다고 가정하면 몇 개의 사용자 이름이 가능한가? 중복이 허용되지 않는 경우라면?
알파벳은 총 26개가 있다. 그리고 숫자는 0에서부터 9까지 총 10가지 경우의 수가 있다. 그러면 사용자 이름을 만들 수 있는 총 경우의 수는 첫 번째 알파벳 같은 경우에는 a~z까지 다 들어올 수 있기 때문에 26가지 두 번째도 중복을 허용한다고 하면 또 26가지 세 번째도 26가지 그리고 네 번째부터는 숫자가 들어와야 하니 10 이런식으로 가능한 경우의 수를 모두 곱해주면 된다.
=> 26 * 26 * 26 * 10 * 10 * 10 * 10 * 10 = 1,757,600,000
중복을 허용하지 않는다. 라는 말은 첫 번째 a가 나왔으면 두 번째에는 a가 나올 수 없는것이다. 처음에는 26가지가 모두 나올 수 있지만 두 번째는 첫 번째에서 나온 문자를 제외한 25가지가 나올 수 있고 세 번째는 첫 번째 두 번째에서 선택한 걸 제외한 24가지가 된다. 이런 식으로 숫자도 동일하게 계산해주고 모두 곱해주면 된다.
=> 26 * 25 * 24 * 10 * 9 * 8 * 7 * 6 = 471,744,000
Permutations(순열)
순열(Permutation)은 객체 집합의 일부 또는 전체를 배열하는 것이다. 따라서 사물의 순서가 고려된다. 다시 말해, 객체 집합을 배열하는 방법의 수는 객체들이 구별 가능(서로 다른)하다는 것을 전제로 하고 총 개수를 구하는 문제라고 생각하면 된다.
ex1) 문자 a, b, c의 서로 다른 순서 배열은 몇 가지가 가능한가?
=> 3 * 2 * 1 = 3!
※ 총 n개의 객체가 있다고 가정하고 순서를 고려해서 나열하는 방법은 총 n!개의 서로 다른 순열이 존재한다.
ex2) 문자 a, b, c의 순서를 고려하지 않은 배열은 몇 가지가 가능한가?
=> 1
ex3) 수학 4권, 화학 3권, 역사 2권, 국어 1권 총 10권의 서로 다른 주제의 책들이 존재할 때 과목별로 그룹 지어서 나열하면 총 경우의 수는 몇 개인가?
수학 책을 나열할 수 있는 경우의 수는 4!, 화학은 3!, 역사는 2!, 국어는 1! 이렇게 과목에 대해서 경우의 수를 구했지만 각 과목별로 그룹의 순서도 고려해야한다. 총 4과목이기 때문에 마지막에 4!까지 곱해줘야한다.
=> 4! * 4! * 3! * 2! * 1! = 6,912
ex4) 빨, 주, 노, 초, 파, 남 ,보 색깔을 가진 7개의 구슬 중 3개를 꺼내 일렬로 나열하는 방법의 수는?
=> 7! / (7-3)!
Nondistinguishable Permutations
지금까지는 서로 구별할 수 있는 경우를 고려하였다. 하지만 서로 구별할 수 없는 경우인 Nondistinguishable Permutations도 존재한다.
ex1) 10명의 농구 선수 중 1학년 1명, 2학년 2명, 3학년 3명, 4학년 4명이 있다. 학년별로만 구분되는 경우 이들을 줄지어 배열할 수 있는 방법은 몇 가지인가?
일단 10명의 선수를 나열하는 방법은 10!이다. 그런데 학년별로만 구분하고 그 학년안에서는 서로 구별하지 않는다고 했기 때문에 각 학년안에서 학생 경우의 수 값으로 나눠줘야 한다.
=> 10! / 1! * 2! * 3! * 4!
ex2) 7개의 구슬 중 빨간색 3개, 초록색 2개, 파란색 2개가 있을 때, 이 구슬을 일렬로 나열하는 방법의 수는?
7개의 구슬을 일렬로 나열하는 방법의 수는 7! 이다. 하지만 구슬들은 색깔들로만 구분되지 같은 색의 구슬들끼리 구별하
지 않으므로 중복되는 경우의 수를 나눠줘야한다.
=> 7! / 3! * 2! * 2!
그래서 이런 위의 예제들처럼 서로 구별할 수 없어서 중복되는 경우의 수를 나누어주는 것을 같은 것이 있는 순열, 동자순열(Permutation of multisets) 이라고 한다.
Combinations(조합)
서로 다른 n개에서 k개를 뽑는 방법의 수를 조합(combination)이라고 한다. 조합은 순서에 상관없이 뽑기만 하면 된다.
ex1) 5장의 포커 핸드는 몇 가지 가능한가?
총 카드의 개수는 52개고 52개 중에서 5개를 뽑아가지고 나열하는 총 경우의 수를 물어보는 것이다.
=> 52! / 47!*5!
ex2) 빨, 주, 노, 초, 파, 남, 보 7개의 구슬이 주머니 안에 들어가있다. 7개 구슬 중 3개를 순서에 상관없이 뽑는 경우의 수는?
7개 구슬 중 3개를 뽑아 나열하는 경우의 수는 7*6*5이다. 하지만 뽑은 3개의 순서는 중요하지 않으니 3으로 나누어준다.
=> 7*6*5 / 3!
ex3) 12명을 크기가 각각 3명, 4명, 5명인 3개의 위원회로 나누는 방법은 몇 가지인가?
12명 중에 처음 3명을 일단 뽑으면 9명이 남는다. 그래서 남은 9명 중에 4명을 뽑아야하고 남은 9명 중에 4명을 뽑으면 5명이 남으니깐 마지막엔 5명 중에 5명을 뽑는 경우의 수가 된다.
=> 12! / 3!*4!*5!
The Binomial Theorem(이항정리)
이항정리란, (a+b)^n (단, n은 음이 아닌 정수)의 꼴을 전개할 때 쓰이는 정리이다. 이항정리의 '이항'은 '두 개의 항(二項)'이라는 뜻이며, '항을 옮긴다'는 뜻이 아니다.
(x+y)^3을 이항정리를 사용하여 전개해보면 아래의 그림과 같다.
각 항들의 계수 1, 3, 3, 1 즉 이항계수는 어떤 특별한 법칙을 따르고있는데 이항계수를 삼각형 모양으로 배열한 파스칼의 삼각형(Pascal's triangle)을 보면 확인할 수 있다. 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. 먼저 첫 번째 줄에는 1을 쓴다. 그 후 그 다음 줄을 만들 때 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다. 예를 들어, 네 번째 줄의 숫자 1과 3을 더하여 다섯 번째 줄의 4가 만들어진다.
이 파스칼의 삼각형의 각 단에 있는 이 숫자들이 뭘 의미하냐면 이항 정리로부터 나온 전개식의 계수가 된다는 것이다. 좀 전에 (x+y)^3를 전개해보면 각 항들의 계수가 1, 3, 3, 1인것을 확인할 수 있었는데 이것은 네 번째 줄의 숫자들과 동일하다. 이것은 (x+y)^4, (x+y)^5 들도 동일하게 적용된다.
Multinomial Coefficients(다항계수)
이항정리는 항이 2개일 때 사용한다면, 다항정리는 항이 3개 이상일 때 사용한다.
ex1) $(a+b+c)^{4}$에서 $a^{2}$bc의 계수는?
$(a+b+c)^{4}$ = (a+b+c)(a+b+c)(a+b+c)(a+b+c)이다. 이때 $a^{2}$bc가 되는 경우를 생각해보면 (a,a,b,c), (a,b,a,c), (a,b,c,a), .... 즉, (a,a,b,c)를 나열한 같은 것을 포함한 순열의 수가 $a^{2}$bc의 계수가 된다. 즉, 4! / 2!*1!*1!이 $a^{2}$bc의 계수가 된다.
=> 4! / 2!*1!*1!
ex2) 작은 도시의 경찰서에는 10명의 경찰관이 있다. 경찰서의 정책은 5명의 경찰관이 거리에서 순찰을 하고, 2명의 경찰관이 경찰서에서 상근 근무를 하며, 3명의 경찰관이 경찰서에서 대기하는 것이다. 10명의 경찰관을 3개의 그룹으로 나누는 서로 다른 방법은 몇 가지인가?
=> 10! / 5!*2!*3!
참고자료
[1] 고려대학교 김성범 교수님의 Youtube강의 [핵심 확률/통계] Combinatorial Analysis
'🔣 Math > Probability' 카테고리의 다른 글
| [확률론] 2.사건(Events) (1) | 2024.09.13 |
|---|---|
| [확률론] 1.표본 공간(Sample Space) (0) | 2024.09.09 |
