Page 99 - 책(종합)

. 3 이웃할 때와 이웃하지 않을 때의 순열의 수
) 1 이웃할 때의 순열의 수
예를 들어 사람 1 , 2 , 3 , 4 의 4 명이 일렬로 설 때, 1 , 2 가 서로 이웃하여 서는 경우를 나열하면
12 34 , 12 43 , 31 24 , 41 23 , 34 12 , 43 12 ,
21 34 , 21 43 , 32 14 , 42 13 , 34 21 , 43 21

의 !3 # ! 2 = 6 # 2 = 12 가지이다.
이와 같은 경우의 수는 다음과 같이 구할 수 있다.
1단계 이웃하는 것을 하나로 묶어 한 묶음으로 생각하여 배열한다.
유형
2단계 한 묶음 안의 수를 배열한다. 05
따라서 (이웃한 것을 한 묶음으로 묶어 구한 순열의 수) # 한 묶음 안의 순열의 수)
(
경
) 2 이웃하지 않을 때의 순열의 수 우
의
예를 들어 여학생 3 명, 남학생 4 명이 일렬로 설 때, 여학생끼리는 남 남 남 남
수
서로 이웃하지 않게 서는 경우를 나열하면 남학생 4 명이 일렬로 서는 와
방법은 !4 가지이고, 이 각각에 대하여 남학생과 남학생 사이 3 개의 자리와 여 여 여 순
열
맨 앞과 맨 뒤의 전체 5 개의 자리 중에서 3 개의 자리에 여학생 3 명이 서는 방법은 P 3 이다.
5
그러므로 구하는 가짓수는 !4 # 5 P 3 = 24 # 60 = 1440 가지이다.
이와 같은 경우의 수는 다음과 같이 구할 수 있다.
1단계 이웃해도 되는 것을 먼저 배열한다.

2단계 이웃하면 안 되는 것을 양 끝 또는 사이에 배열한다.
(
따라서 (이웃해도 되는 것의 순열의 수) # 이웃하면 안 되는 것을 양 끝이나 사이에 배열한 순열의 수)
4. [적어도 ~\의 조건이 있는 순열의 수와 교대로 나열하는 순열의 수
) 1 [ 적어도 ~ \ 의 조건이 있는 순열의 수

[ 적어도 ~인 경우 \ 의 사건은 [ ~인 경우 \ 가 한 개 이상만 있으면 되므로 경우의 수를 구할 때에는
전체 경우의 수에서 [ 모두 ~가 아닌 \ 경우의 수를 빼면 된다.
따라서 (적어도 ~가 있는 경우의 수) = (전체 경우의 수) - (모두 ~가 아닌 경우의 수)이다.
) 2 교대로 배열하는 순열의 수
1단계 두 개의 대상 중 하나를 일렬로 나열한다.
2단계 나머지 대상을 1단계 의 사이사이와 맨 앞과 맨 뒤에 교대가 되도록 일렬로 나열한다.

5. 순열을 이용한 일대일함수의 개수
,
,
,
,
,
예를 들어 두 집합 X = " , 12 34, , Y = " , ab cd e, 에 대하여 X f Y
집합 X 에서 집합 Y 로의 일대일함수의 개수는 1 a
,
,
,
집합 Y 의 원소 ,ab cd e 에서 서로 다른 4 개를 뽑아 2 b c
3
1 $ , 2 $ , 3 $ , 4 $ 의 d
4 e
안에 나열하는 경우의 수와 같으므로
구하는 함수의 개수는 P 4 = 120 개이다.
5
f
즉, P 4 = 120 은 X 에서 Y 로의 일대일함수의 개수와 같다. X Y
5
따라서 두 집합 X = " , x 1 , x 2 , x 3 g , x r, , Y = " , y 1 , y 2 , y 3 g , y n, 에 대하여 x 1 y 1
x 2 y 2
집합 X 에서 집합 Y 로의 일대일함수의 개수는 P r 이다. x 3 y 3
n
h h
r
특히, n = 일 경우에는 집합 X 에서 집합 Y 로의 x r y n
일대일함수의 개수는 P n = ! n 이다.
n
x 2 에 대하여 x 1 ! ] f x 2g일 때, 함수 f 를 일대일함수라 한다.
참고 X 의 임의의 두 원소 ,x 1 x 2 이면 f x 1 ! ]g
091