조합(combination)

2012. 11. 2. 21:27

순열(permutation) 에 r! 을 나눈것

nCn-r = nCr (n>=r)

ex)

n 명중에서 r명을 뽑는데 k 명을 반드시 한 경우의 수는?

집합 A= { 1,2,3,4,5 } 가 있을때 1,2 를 포함한 부분집합 개수는? 이라는 관점에서 보면

3,4,5 에 대한 부분집합개수 연산에 1,2 는 항상 포함되어 있는 것이니 1,2 를 제외 시켜놓고 3,4,5 에 대한 생각만 하면 된다

즉 n명중에서 반드시 k 명을 포함한 r 명이니 k명은 어느 r 그룹에나 다 포함된 것임으로 k 명에 대한 것을 빼주머 계산하면 된다

먼저 전체 n명에서 k 명만큼 제외하고

선택할 r 명에서는 항상 k 명만큼이 r 명에 들어간 수치이니 r 명에서 k 명을 뺀 나머지 수치에 대한 조합 연산을 하면 된다

n-k C r-k

정리하자면 k 명이 항상 포함되어 있어야 하니 전체 n 명과 선택할 r 명 에서 각각 k 명을 뺀다

왜냐하면 항상 포함되는 k 명을 n명에서 제외 시키는 것임으로 전채 r 에서도 동일하게 k 명이 빠져야 동일한 전체 수치가 적용 된다

조합으로 뽑은 경우의 수의 전체 개수의 나열 개수는?

nCr * r! = nPr

nCr = 조합 n!/ ((n-r)! *r! )

nPr = 순열 n!/(n-r)!

조합으로 나타낸다는 것은 1,2,3 또는 2,1,3 을 한개로 본 경우이다

( 순열에서 순서만 다르고 같은 숫자들의 개수로 나눈 것이 조합 )

n 개의 겹치지 않는 접이 있을때 만들 수 있는 선분의 수는?

=nC2

n 개의 겹치지 않는 점이 있을때 만들 수 있는 삼각형의 수는?

= nC3 - (3개의 점이 일직선 상에 있는 것의 수)

n다각형의 점들로 만들 수있는 선분은? 단 외곽선 제외

=nC2 - n

-n 은 다각형의 외곽 선의 개수

n 개의 직선을 가로로 긋고 m의 직선을 세로로 그었을때 생기는 평행 만들어지는 평행 사변형의 갯수는?

nC2 * mC2

평행 사변형은 가로선 두개와 세로선 두개로 만들어 짐으로 겹치지 않는 세로 , 가로 각 두개씩의 선의 경우의 서둘로

만들어 질 수 있다

nC2 가 가로에 대한 2개씩의 선을 뽑아오는 경우의 수라면 이때

mC2 에서 나온 한가지의 경우의 수만을 nC2 와 겹친다고 하면

nC2 *1 개 만큼 생성

mC2 에서 두가지의 경우의 수에 대해 고려한다면

nC2 * 2 개 만큼 생성

결론적으로

nC2 * mC2 개만큼 생성 된다

3DMP