얼마나 많은 함수를 만들 수 있는가? How many functions can we make?

이전 포스트에서 함수에 대해서 설명했다.

다시 상기하면,

정의역이 되는 집합이 있고 대응시킬 집합인 공역이 있다.

그 집합의 모든 원소들이 대응되며,

각 원소는 단 하나의 공역의 원소에 대응되어야 한다.

 

정의역, 공역이 아래와 같이 있을 때,

 

f

A           B

a           x

b           y

c           z

d            

 

만들어 낼 수 있는 함수는 몇 개가 있을까?

우선, a는 x,y,z 중 하나를 고를 수 있다.

나머지 b, c, d 도 마찬가지이다.

a에 대응되던 원소에 다른 원소가 대응되어도 함수가 되기 때문이다.

정의역인 A의 원소가 공역인 B의 원소에 하나만 가면 된다.

그러니까 A의 각 원소는 고를 수 있는 경우가 3 가지 인 것이다.

4개 원소가 동시에 대응되어야 함수가 되므로,

정의역에 대응되는 공역의 순서 조합을

( p, q, r, s )

이렇게 나타낼 수 있다.

p,q,r,s는 B의 원소여야 하므로,

공역의 순서 조합 집합은

{ (p,q,r,s) ㅣ p∈B ∧ q∈B ∧ r∈B ∧ s∈B }

이런 식으로 나타낼 수 있고,

이 집합은 B x B x B x B 로 나타낼 수 있다.

 

여기서 합집합의 크기와 곱집합의 크기에 대해 잠시 알아보자

합집합은 A∪B 의 개수가 n(A) + n(B) 일 때가 있는데,

A∩B 가 공집합일 때이다.

 

이 사실로 곱집합의 갯수를 알아보자.

(a,b)가 A x B 의 원소라고 하면,

순서쌍의 원소 하나만 달라져도 다른 원소이니,

임의의 두 순서쌍의 교집합은 공집합이다.

A에 속한 모든 원소와 B에 속한 b로 순서쌍을 만들면,

A의 원소 수와 같게 된다.

예를 들어, A={ u, v, w } 라고 하면,

순서쌍은 ( u, b ), ( v, b), ( w, b ) 이렇게 되지 않는가?

순서쌍의 수는 3개로 A의 수와 같다.

이런 순서쌍을 B의 모든 원소로 만든다면,

n(A)를 B의 원소 수 만큼 더한 결과가 된다.

따라서, n( A x B) = n(A) x n(B) 가 된다.

 

그러면 앞에서 언급한 B x B x B x B 의 개수를 알 수 있다.

곱셈의 교환, 결합 법칙이 성립하므로,

n( B x B x B x B ) = ( n(B) )^4

이 됨을 알 수 있다.

위에서 A = { a, b, c, d } 였으므로,

n(A) = 4

f : A -> B 를 만들 수 있는 수는 ( n(B) )^( n(A)) 가 된다.

위에서 A가 4개라서 순서 조합이 4칸이었는데,

A의 갯수 마다 칸 수가 달라지므로, 일반적으로도 성립한다.

 

함수는 저만큼 만들 수 있는데,

일대일 함수는 얼마나 만들 수 있을까?

일대일 함수라면, f : A -> B 일 때,

n(B) >= n(A) 가 될 것이다.

일대일 함수는 정의역의 원소가 다르면,

대응되는 원소가 다르므로,

A의 원소를 순서대로 골랐을 때,

처음 원소가 골랐던 공역의 원소를

다른 정의역의 원소가 고르지 못한다.

공역 순서 조합을

( x, y, z, ..., w )

이렇게 만들 수 있는데,

들어갈 수 있는 갯수가 하나씩 줄어들게 되고,

일대일 함수의 수는 n(A)=a, n(B)=b 라고 할 때,

b * ( b-1) * ... * ( b-(a-1))

이렇게 될 것이다.

0부터 a-1까지 자연수는 a 개이고,

위의 순서 조합 칸 수는 A의 원소 갯수만큼이므로,

a개가 된다.

이런 수를 간단하게 

b P a

이렇게 표시한다.

(첨자 표시를 못해서 P를 크게 만들었다.)

 

일대일 대응일 때는 b=a 이므로,

a P a

이렇게 된다.

이런 경우는 특별히 a! 로 표기한다.

b! = b * ( b-1 ) * ... * ( b-(a-1)) * ( b-a ) * ... * 3 * 2 *1

이 된다.

b P a = b!/(b-a)! 이 된다.

 

f : A ->B 인 함수의 개수는

n(A) = a , n(B)=b 일 때,

b^a 이고,

b>=a 일 경우는, 일대일 함수가 가능하므로,

일대일 함수의 개수는

b P a = b!/(b-a)! 이다.

수를 센 과정을 보면,

서로 다른 b개 중에 a개 고른 것과 같은 과정이다.

확률 쪽 분야에서 경우의 수 같은 거 얘기할 때 자주 쓰이는 연산 방식이다.