순열과 조합의 수

순열permutations과 조합combination의 수 

 

예를 들어 공 10개를 나열하는 가짓수는? 

첫공은 10개 중의 하나.. 다음 공은 9개 중의 하나... 순서대로... 각 조합을 곱한 것이므로 다음 계산과 같습니다.

 

10x9x8x7x6x5x4x3x2x1 = 10! 가지

 

그런데 n개 중에서 일부 k개만 나열할 때의 가짓수는 순열 가짓수를 이용합니다.

즉, 다음과 같은 조건을 모두 포함하고 있으면 순열의 수를 이용합니다.

 

① 서로 다른 대상에서 뽑는 경우

② 중복을 허락하지 않고 뽑는 경우

③ 뽑은 것을 일렬로 배열하는 경우

 

순열 공식:  nPk =  n! / (n-k)!

 

1) 공 10개 중에서 4개를 나열하는 가짓수는? 

 

전체 가짓수 10!에서 남은 6개 공의 가짓수 6!를 나눠줍니다. 

 

10P4 = 10! / (10-4)! = 5040 가지

 

만약 어떤 순서와 상관없이 일정 개수로 묶고자 한다면 다음처럼 조합 계산을 합니다. 

 

조합 공식: nCk = n! / ((n-k)! x k!)

 

2) 5마리 고양이를 3마리로 묶을 수 있는 가짓수는? 

 

5C3 = 5! / ((5-3)!3!) 

     = 10 가지 

 

3) 만약 2번 문제를 3마리로 나열하는 방법을 물어본다면 순열로 계산해야 하니 주의합니다. 

 

5P3 = 5! / (5-3)! 

     = 60 가지

 

 

C 언어로 순열 구하여 출력하는 예제는 아래 글을 참고하세요.

 

http://blog.daum.net/sualchi/13720453

C 언어, 순열 자료 출력하기

 

<이상>