2019년 11월 8일

최은진의 노베부터 시작하는 확통 20 – 09강 순열과 조합, 자연수와 집합의 분할 비교

개념 정리
1. 다른/같은 종류 대상을 다른/같은 종류의 자리에 나누어 담기

  다른종류의 사탕 5개 같은종류의 사탕5개
다른종류의 봉지3개 빈봉지

허용

중복순열! (곱의법칙)
^3\pi_5 = 3^5

 빈봉지

허용

중복조합!
^3H_5

a+b+c = 5(a,b,c>=0)

허용안함

S(5,3) * 3!도 가능
(중복순열로 생각)
우선 빈봉지를 뽑아서 나열: ^3\pi_5 – 3\ast^2\pi_5 + 3
즉, 모든 빈봉지를 허용하는 경우에 빈봉지의 경우를 빼줌. x3의 경우는
a,b,c를 빈봉지라 하면
abc => (a가 빈봉지)
bca
cab
이렇게 3가지.
여기서 a가 빈봉지인데 b나 c가 또 빈봉지일 경우도 있으므로, 3을 더해줘야함.

허용안함

^3H_2 즉, a+b+c = 5(a,b,c >= 1)

 

  다른종류의 사탕 5개 같은종류의 사탕5개
같은종류의 봉지3개 빈봉지

허용

S(5,3) + S(5,2) + S(5,1) = 41

 빈봉지

허용

P(5,3) + P(5,2)+P(5,1)
(자연수의 분할)

허용안함

S(5,3) (집합의 분할)
3+1+1
2+2+1
$latex ^5C_3 \ast ^2C_1 \ast \frac{1}{2!} + ^5C_\2 \ast ^3C_2 \ast \frac{1}{2!}

허용안함

P(5,3) = 3+1+1, 2+2+1 (2가지)
  • 서로 다른 대상, 서로 다른 자리: 중복순열
  • 서로 같은 대상, 서로 다른 자리: 중복조합
  • 서로 다른 대상, 서로 같은 자리: 집합의 분할
  • 서로 같은 대상, 서로 같은 자리: 자연수의 분할

문제: 두 집합 X={1,2,3,4}, Y={1,2,3,4,5,6,7}에 대하여 다음 조건을 만족하는 함수 f:x -> y의 개수를 구하여라
(1) 함수: x->y로 x는 무조건 가야함. -> 중복순열 (7^4)
(2) i!=j이면 f(i) != f(j) -> 1:1함수! 7x6x5x4 7P4
(3) i<j이면 f(i) < f(j) -> 단순히 7C4로 가능. 뽑기만 하면 됨! (조합) Y에서 4개를 뽑아다가 X에다가 순서대로 주면 됨.

문제: 두 집합 X={1,2,3,4,5}와 Y={a,b,c}에 대하여 X에서 Y로의 함수 중에서 치역이 Y인 함수의 개수를 구하시오.
치역=공역 즉, Y에 대응을 해야한다. X의 값을 3묶음으로 해야함. 즉, 분할 한 이후, 분배도 해야함.
5 = 3+1+1 -> 5C3 * 2C1 * 1/2!
= 2+2+1 -> 5C2 * 3C2 * 1/2!
여기에 3묶음 분배인 3!를 곱해줘야함.
즉, (5C3 * 2C1 * 1/2! + 5C2 * 3C2 * 1/2!) * 3! = 150

문제: 집합 X={1,2,3,4}에서 집합 Y={4,5,6,7}로의 함수 f중 다음 조건을 만족하는 함수의 개수를 구하시오.
(가) f(2) = 5
(나) 집합 X의 임의의 두 원소 i,j에 대하여 i<j이면 f(i) <= f(j)
X의 2를 고정시키고, 나머지를 따져본다.