순열과 조합을 이용한 함수의 개수

두 자연수 m,n에 대하여 원소의 개수가 m인 집합 X에서

원소의 개수가 n인 집합 Y로의 함수 f의 개수는 다음과 같다.

원소의 개수가 5인 집합 X에서 원소의 개수가 2인 집합 Y로의 함수 f의 개수

 

1. 전체 함수의 개수

모든 정의역의 원소에 공역의 원소를 중복을 허락하여 하나씩 대응시키면 ㅎ마수가 정의된다. 

첫 번째 정의역의 원소를 대응시키는 경우의 수는 n, 

두 번째 정의역의 원소를 대응시키는 경우의 수도 n,

.

.

.

m번째 정의역의 원소를 대응시키는 경우의 수도 n이다. 

즉, 전체 함수의 개수는 공역의 원소 n개 중에서 중복을 허락하고 순서를 따져서 m번 택하는 중복순열의 수와 같다.

 

2. 일대일함수(일대일대응)의 개수

일대일함수는 정의역의 임의의 원소 x1, x2에 대하여

이다. 이때(m=n이면 일대일대응이 된다.)

그러므로 일대일함수의 개수는 공역의 n개 중에서 중복을 허락하지 않고 순서를 따져서 m번 택하는 

과 같다. 

 

3. 증가하는 함수/ 감소하는 함수의 개수

증가하는 함수는 정의역의 임의의 원소 x1, x2에 대하여

이다. 

그러므로 공역의 원소 중 정의역과 대응될 m개를 뽑기만 하면 증가하는 함수가 되도록 정의역의 원소와 대응시키는 방법은 정해진다. 

따라서 증가하는 함수의 개수는 공역의 원소 n개 중에서 중복을 허락하지 않고 순서도 따지지 않으면서 m번 택하는 조합의 수

과 같다.