The Basic Principle of Counting
The Basic Principle of Counting. If an experiment consisting of two phases is such that there are nn possible outcomes of phase 1 and, for each of these nn outcomes, there are mm possible outcomes of phase 2, then there are nmnm possible outcomes of the experiment.
'곱의 법칙'으로 흔히들 배우는 내용이다. 첫 번째에서 nn개의 케이스가 나오고, 각 케이스에 대해서 두 번째에는 mm개의 케이스가 존재한다면 총 nmnm개의 케이스가 존재한다는 내용이다. 모든 케이스를 하나씩 카운트해주면 총 mnmn개가 존재하므로 당연히 성립하는 정리다. 일반화도 가능한데, rr번의 시행에서 각각 ni(1≤i≤r)ni(1≤i≤r)개의 케이스가 존재한다면 총 경우의 수는 n1⋯nrn1⋯nr개이다.
Permutation
Permutation. We define n!n!, for n>0n>0, by n=n(n−1)⋅3⋅2⋅1n=n(n−1)⋅3⋅2⋅1 and say that n!n! (read as "nn factorial") represents possible linear orderings of nn items. It is convenient to define 0!=10!=1.
nn개의 대상을 일렬로 나열하는 경우의 수는 n⋯2⋅1n⋯2⋅1개 존재하며, 이를 n!n!로 정의하고 nn factorial(팩토리얼)이라고 읽는다. 이때 nn개의 대상이 모두 다를 필요는 없는데, nn개 중 중복되는 대상이 존재할 경우 중복되는 대상의 개수만큼 팩토리얼을 취하여 나눠주면 된다. 예컨대 중복되는 대상이 존재하여서 서로 다른 대상이 총 rr개 존재하면 (즉 n1+⋯+nr=nn1+⋯+nr=n) 총 경우의 수는 다음과 같다. n!n1!⋯nr!n!n1!⋯nr! 한국 교육과정에서는 '같은 것이 있는 순열'로 배운다.
Combination
Combination. We define (nr)(nr), for 0≤r≤n0≤r≤n, by (nr)=n!(n−r)!r! and say that (nr) (read as "n choose r") represents the number of possible combinations of n objects taken r at a time. It is convenient to define (nr) equal to 0 when either r>n or r<0.
n개의 대상 중 r개를 한 번에 뽑는 경우의 수, 정도로 받아들일 수 있다. 이는 크기가 n인 집합에서 크기가 r인 부분집합의 개수와도 같다.
Pascal's Identity
Pascal's Identity. (nr)=(n−1r−1)+(n−1r) where 1≤r≤n
위 정리가 성립함은 직관적으로도 알 수 있다. n개 중 r개를 뽑는 경우의 수를 생각할 때, 특정한 원소 하나를 생각하자. 그럼 이 원소를 포함할 때와 포함하지 않을 때로 나눌 수 있고, 이는 각각 n−1개에서 r−1개를 뽑는 (무조건 특정 원소를 포함하는 경우) 경우의 수와 n−1개에서 r개를 뽑는 경우의 수에 대응된다.
The Binomial Theorem
The Binomial Theorem. (x+y)n=n∑k=0(nk)xkyn−k
위 정리가 성립함은 Combination의 정의상 당연하게 알 수 있다. 형식적인 증명은 induction으로 할 수 있다. 위 정리와 연결지어서 combination을 binomial coefficient (이항 계수) 라고 부르기도 한다.
Multinomial Coefficient
Multinomial Coefficient. We define (nn1,⋯,nr) by (nn1,⋯,nr)=n!n1!⋯nr! where n1+⋯+nr=n and say that (nn1,⋯,nr) represents the number of possible divisions of n distinct objects into r distinct groups of respective sizes n1,⋯,nr.
n개 중 r개만 뽑는 게 아니라, 다시 말해 크기가 r인 1개의 영역으로만 나누는 것이 아니라 각각 크기가 ni(1≤i≤r)인 r개의 영역으로 나누는 상황을 생각할 수도 있다. 이 경우의 수의 계산은 combination으로 할 수 있는데, n개 중 먼저 n1개를 뽑고 다음으로 n−n1개 중 n2개를 뽑고, 이런 식으로 nr개까지 모두 뽑는 경우의 수를 전부 곱하면 위 정의와 같이 계산됨을 알 수 있다. Binomial coefficient와 같은 방식으로 위 수를 multinomial coefficient (다항 계수) 라고 부르며, 마찬가지로 multinomial theorem이 성립함을 알 수 있다.
The Multinomial Theorem
The Multinomial Theorem. (x1+⋯+xr)n=∑n1,...,nrn1+⋯+nr=n(nn1,⋯,nr)xn11⋯xnrr