중복순열

■ 중복순열

 

1. 중복순열

(1) 서로 다른 n개에서 중복을 허락하여 r개를 택하는 순열을 중복순열이라 한다. 이 중복순열의 수를 로 나타낸다.

(2) 중복순열의 수 : 서로 다른 n개에서 r개를 택하는 중복순열의 수는

 

2. X에서 Y로의 함수의 개수

두 집합 X, Y에 대하여 n(X) = r, n(Y) = m일 때,

(1) X에서 Y로의 함수의 개수는

⇒ (중복순열의 개수)

 

(2) X에서 Y로의 일대일함수의 개수는

⇒ (순열의 개수)

 

3. 같은 것이 있는 순열

n개 중에서 같은 것이 각각 p개, q개, …, r개씩 있을 때, n개를 모두 일렬로 나열하는 방법의 수는

(단, )

 

※ 최단 경로 문제

⇒ 같은 것이 있는 순열 문제로 생각한다.

 

예) 그림과 같이 A에서 B까지 가는 최단 경로는

풀이) 순서와 상관없이 오른쪽으로 3번, 위쪽으로 2번 가야 한다.

오른쪽으로 1칸 가는 거을 a, 위쪽으로 1칸 가는 것을 b라 하면 가는 길은 모두 a, a, a, b, b의 순열의 수이다.

따라서 같은 문자가 있는 순열의 개수를 구하면 최단 경로의 수를 구할 수 있다.

ababa에 해당되는 경로는 다음과 같다.

즉, 

 

순열 원순열의 수