순열 permutation

순열 permutation

 

n개의 서로 다른 것 중에서 r개(nr)를 택하여 어떤 순서에 따라 일렬로 배열하는 것. 이를테면 서로 다른 3개의 문자 a, b, c중에서 2개씩 택하여 일렬로 늘어놓는 방법은 ab, ac, ba, bc, ca, cb의 6가지이다.

일반적으로 n개의 서로 다른 것 중에서 r개를 취해 일렬로 늘어놓는 방법을 각기 n개에서 r개 취한 순열이라 하고 이 순열의 수 (늘어놓는 방법의 개수)를 라고 표시하며 다음과 같이 계산한다.

이 공식에 의하면 위의 보기는 =3·2=6으로 계산된다.

〔중복순열〕 n개의 서로 다른 것 중에서 r개를 택하는 순열에서 중복을 허락하는 것. 예를 들어 네 개의 숫자 1, 2, 3, 4 중에서 중복을 허락하고, 세 숫자를 취하여 3자리 정수를 만드는 방법은 첫째 100의 자리에는 1, 2, 3, 4 중 어느 숫자라도 올 수 있으므로 네 가지, 다음의 10의 자리에는 100의 자리에 쓴 숫자도 올 수 있으므로 1, 2, 3, 4의 네 가지, 또 1의 자리도 마찬가지로 네 가지이다.

따라서 세 자리 정수의 개수는 4×4×4=64가지이다.

일반적으로 n개의 서로 다른 것 중에서 중복을 허락하여 r개를 택하는 중복 순열의 수는 라고 쓰며 다음과 같이 계산한다.

n개 중에 같은것이 몇 개 포함되어 있는 경우를 생각한다.

n개 중에 같은 것이 각각 p, q, r, …개 있다면 이들을 전부 합하여 n=p+q+r+…개를 일렬로 늘어놓는 방법의 수는

이다.

이를테면 a, a, a, b, b, c, c, d의 8개의 문자를 모두 사용하여 만들 수 있는 순열의 수는 a가 3개, b가 2개, c가 2개, d가 1개이므로 다음과 같이 계산된다.