nPr (순열) : n개의 카드 중에 r개를 뽑아 나열할 수 있는 경우의 수, 중복이 가능하다.
예) 10명의 인원에서 2명을 뽑아 반장, 부반장을 뽑을 수 있는 경우의 수.
수학공식 : nPr = n!/(n-r)!
n!/(n-r)!=n*(n-1)*(n-2)*...*(n-r+1) *(n-r)*(n-r-1)*.....
──────────────────────────
(n-r)*(n-r-1)*.....
nPr = n*(n-1)*(n-2)*...*(n-r+1)
nCr (조합) : n개의 카드 중에 r개를 뽑아 나열할 수 있는 경우의 수, 단 중복은 불가능하다.
예) 10명의 인원에서 2명씩 짝을 이룰 수 있는 경우의 수.
수학공식 : nCr=nPr/r!
nPr/r!=n*(n-1)*(n-2)*...*(n-r+1)
────────────────
r*(r-1)*(r-2)*.....*1
! (펙토리얼) : n개를 일렬로 줄 세워서 나올 수 있는 경우의 수.
예) 10명의 인원을 한줄로 세울 수 있는 경우의 수.
수학공식 : n! = n*(n-1)*(n-2)*...*(1)
아래는 C/C++ 소스코드입니다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int permutation(int m, int n);
int combination(int m, int n);
int factorial(int seed);
int main()
{
int m, n;
m = 10;
n = 2;
printf("%dP%d = %d\n", m, n, permutation(m, n));
printf("%dC%d = %d\n", m, n, combination(m, n));
return 0;
}
int combination(int m, int n)
{
return permutation(m, n)/factorial(n);
}
int permutation(int m, int n)
{
if(n == 1) return m;
else return m * permutation(m - 1, n - 1);
}
int factorial(int n)
{
if(n == 1) return 1;
else return n * factorial(n - 1);
}