9장) 경우의 수와 확률 - 순열

■ 팩토리얼(Factorial)이란?

이어지는 숫자 여러개를 곱하는 것.

$$ n! =n\times(n-1)\times(n-2)\times\cdots\times1$$

 

■ 순열(Permutattion)이란?

순서를 가지고 나열하는 것.

ex: 사람이나 사물을 한 줄로 세우는 등

◇ 순열을 팩토리얼로 나타낸다면

n개의 대상 중에서 k개만 한 줄로 세우는 경우의 수

$$_{n}\mathrm{P}_{k}=\frac{n!}{(n-k)!}$$

◇ k자리에 몇몇 특정 값을 넣는 경우

$$_{n}\mathrm{P}_{0}=\frac{n!}{n!}$$

$$_{n}\mathrm{P}_{1}=\frac{n!}{(n-1)!}=n$$

$$_{n}\mathrm{P}_{n-1}=\frac{n!}{1!}=n!$$

$$_{n}\mathrm{P}_{n}=\frac{n!}{0!}=n!$$

 

■ 여러가지 순열

◇ 줄을 세울 때 대상의 일부를 묶어서 하나로 간주해야 하는 경우

n개의 대상 중 r개를 하나의 묶음으로 치면 전체 대상의 수는 n-(r-1)이 되며, 이 순열의 수에 r개를 나열하는 경우의 수를 곱한다. 수식으로는 다음과 같다.

$$(n-r+1)!\times r!$$

◇ 중복순열: 한 번 포함된 대상이라도 중복해서 계속 줄을 세울 수 있다면?

$$n^{k}$$

◇ 원순열: 대상 중 서로 구별할 수 없이 같은 것들이 섞여 있다면?

까만 당구공(●) 2개와 흰색 당구공(○) 2개를 줄을 세운다고 가정.

같은 색의 공끼리는 구별이 가지 않음.

만약 까만 당구공과 하얀 당구공은 서로 구별이 된다고 가정하고, 

●●○○ 식의 배열에 번호를 붙인다면 아래와 같다.

 

●1●2○1○2     ●1●2○2○1     ●2●1○1○2     ●2●1○2○1 

 

구별되지 않는 공의 배열 한 가지에서 (●●를 나열하는 경우의 수)X(○○을 나열하는 경우의 수)를 곱한 네 가지 경우가 대응된다는 것.

즉, 구별 가능한 것으로 계산한 전체 순열의 수는 구별되지 않는 경우라면 1/{(●●를나열하는경우의수) X (○○을나열하는경우의수)} 로 줄어 $$4!\div 4 = 6$$ 이 될 것임을 예상할 수 있다. 

 

이것을 일반화한다면 다음과 같은 수식으로 나타낼 수 있다.

$$\frac{_{n}\mathrm{P}_{k}}{n}=\frac{n!}{n}=(n-1)!$$

 

예제: 빨간색 당구공 3개, 흰색 당구공 2개를 동그랗게 배치하는 경우의 수를 구하고, 실제 배치도를 그려서 확인하여라. 단, 색깔이 같은 공은 서로 구별할 수 없다고 한다.

풀이: 

$$\frac{5!}{(3!\times 2!)}=\frac{5\times 4\times 3\times 2\times 1}{(3\times 2\times 1\times 2\times 1)}=\frac{5\times 2}{1}=10$$