모두 늘어놓는 순열(팩토리얼)

모두 늘어놓는 순열은 순열의 특별한 경우이다. 원소가 n개인 집합에서 서로 다른 n개의 나열이 몇 가지인지 구한다.

공식

먼저 순열을 복습하자. 숫자의 집합 {1, 2, 3, 4, 5}에서 같은 숫자를 두 번 쓰지 않고 세 자리 수를 몇 개 만들 수 있을까? 이것은 순열의 전형적인 예이고, 익숙한 공식으로 풀 수 있다.

$${}_5{\mathrm{P}}_3=\frac{5!}{(5-3)!}=60.$$

다섯 자리 수는 몇 개 만들 수 있을까?

$${}_5{\mathrm{P}}_5=\frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120.$$

원소가 다섯 개인 집합에서 서로 다른 다섯 개의 나열의 수를 구하면 결과가 5!이라는 것을 알 수 있다. 이를 일반화하면, 원소가 n개인 집합에서는 서로 다른 n개의 나열을 모두 n!가지 만들 수 있다. 여기서 모두 늘어놓는 순열이라는 개념이 나온다.

모두 늘어놓는 순열이란

크기가 n인 집합 M이 있을 때, 모두 늘어놓는 순열은 집합 M의 원소로 만든 n개의 나열 가운데 같은 원소가 두 번 나오지 않는 것이다. 예를 들어 집합 M = {a, b, c, d}가 있으면 (a, b, d, c)나 (d, b, a, c)가 모두 늘어놓는 순열이다. 서로 다른 순열의 수는 다음과 같다.

$${}_n{\mathrm{P}}_n=n!$$

풀이가 있는 예제

1. 책 여섯 권을 어떤 순서로 책꽂이에 꽂으려고 한다. 서로 다른 순서는 모두 몇 가지일까? 책이 여섯 권이고 언제나 모든 책을 늘어놓으므로 결과는 6! = 720이다.

2. 앞 예제의 한국어 책 6권에 라틴어로 쓴 책 4권이 더해졌다. 한국어 책끼리, 라틴어 책끼리 모두 붙여 두려고 할 때, 책 10권을 책꽂이에 꽂는 방법은 몇 가지일까?

   책을 꽂는 방법에는 어떤 것이 있을까? 먼저 한국어 책 여섯 권을 꽂고 그다음 라틴어 책 네 권을 꽂거나, 거꾸로 먼저 라틴어 책 네 권을 꽂고 그다음 한국어 책 여섯 권을 꽂을 수 있다. 이때 한국어 책을 꽂는 방법은 6!가지, 라틴어 책을 꽂는 방법은 4!가지이다. 곱의 법칙을 써서 이 결과를 곱한다. 6! · 4! = 17,280이다. 책을 꽂는 순서가 두 가지(한국어 책 다음 라틴어 책, 또는 그 반대)이므로 이 수에 다시 2를 곱한다. 최종 결과는 17,280 · 2 = 34,560이다.