Combination 계산 - Combination gyesan

목차:

조합 계산기 사용시 주의할 점

조합 계산은 팩토리얼(factorial, 계승)을 포함합니다. n!에서 n이 조금만 커져도 n! 값은 기하급수적으로 커집니다.

예를 들어, 100!의 정확한 값은 다음과 같습니다.

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

조합 계산기는 자바스크립트를 기반으로 하고 있는데요, 자바스크립트는 이처럼 큰 수를 제대로 계산하지 못합니다. 메모리 문제도 있고요.

해서, n에 해당하는 수는 170(중복 조합의 경우 n과 r을 더한 수치로 171)이 한계라는 점 참고하시기 바랍니다.

참고: 171! 이상의 팩토리얼 실제 수치를 확인하려면 팩토리얼 계산기를 이용하세요.

조합 이란?

조합은 ‘서로 다른 n개에서 r개를 선택’한다는 점에서 순열과 같지만 순서를 고려하지 않는다는 점에서 순열과 차이가 있습니다.

조합은 영어의 combination에서 C를 따서 서로 다른 n개에서 순서를 생각하지 않고 r개를 뽑는 선택의 경우의 수를 \( _{n}C_{r} \)와 같이 표시합니다.

조합 계산법

조합 계산은 순열 계산의 연장선에서 생각할 수 있습니다.

즉, 조합은 순서를 고려하지 않으므로, 순서를 고려한 순열을 선택한 r개를 일렬로 나열하는 순열로 나눈 것이라고 생각할 수 있습니다. 예를 들어, 서로 다른 5개의 카드에서 3개의 카드를 뽑는 조합은 5P3을 3P3으로 나눈 값과 같습니다.

왜냐하면 5P3은 3개를 뽑아서 3개를 일렬로 나열한 것이니 3개를 일렬로 나열하는 부분을 없애주면 조합이 되는데, 서로 곱하는 것을 없애려면 나누어 주면 되기 때문입니다.

예를 들어, A, B, C, D, E 라는 5개의 카드가 들어 있는 주머니에서 3개를 선택하는 조합을 계산하는 다음과 같이 계산하면 됩니다.

$$ _{5}C_{3} = \frac{_{5}P_{3}}{_{3}P_{3}} = 10 $$

조합 공식

조합 공식은 보통 아래의 공식을 많이 씁니다.

$$_{n}C_{r} = \frac{n!}{r!(n-r)!} $$

그런데, 위 공식은 아래 공식에서 도출된 것입니다. 즉, nPr 을 rPr 로 나누어 주면 위의 공식이 도출됩니다.

따라서 조합 공식은 아래의 것을 이용해도 됩니다.

$$ _{n}C_{r} = \frac{_{n}P_{r}}{_{r}P_{r}} $$

한편, \( _{r}P_{r} \)은 r!과 같으므로 아래와 같이 생각해도 됩니다.

$$ _{n}C_{r} = \frac{_{n}P_{r}}{r!} $$

중복 조합이란?

순열과 중복 순열의 차이는 반복을 허용하지 않느냐 아니면 허용하느냐의 차이인 것처럼 중복 조합도 조합이긴 하되 반복해서 선택될 수 있도록 하는 선택 방법이라고 할 수 있습니다. 중복 조합 공식은 다음과 같습니다.

$$ _{n}H_{r} = _{n+r-1}C_{r} = \frac{(n+r-1)!}{r!(n-1)!} $$

중복 조합의 공식이 도출된 과정을 이해하려면 약간의 스킬이 필요한데요, 이에 대해서는 중복 조합 idea를 참고 하시기 바랍니다.

순열 계산기도 이용해 보세요.

조합 계산기

Combinatorial calculator solves combinatorial problems involving selecting a group of items. You can select the total number of items N and the number of items that is selected M, choose if the order of selection matters and if an item could be selected more when once and press compute button. Combinatorial calculator will compute the number of ways M could be selected from N given the inputs. Please also take a look at examples of the combinatorial problems below.

구문 규칙 표시

조합 예시

예시 2: 달걀이 20개 들어있는 바구니에서 달걀을 꺼내 그릇에 놓았다. 6개의 달걀이 있는 그릇은 얼마나 있을까?

예시 3: 50개의 공이 들어있는 바구니에서 7개를 꺼내어 꺼낸 순서대로 탁자 위에 올려놓는다. 공을 올려놓는 서로 다른 경우의 수는?

예시 4: 5명의 학생들이 6개의 수업에 등록하는 방법은 몇가지 입니까? (1보다 많은 학생이 각 수업에 등록 할 수 있습니다.)

예시 5: 5c, 10c, 25c의 동전들 중 10개의 동전을 뽑는 경우는 몇 가지 인가요? (동전은 중복하여 뽑을 수 있습니다.)

순서가 있는 것에서 없는 것으로

경우의 수를 세는 방법 가운데 바탕이 되는 것은 순열과 조합이다. 그 가운데에서 순열이 밑바탕이다. 먼저 `1,2,3,4,5`로 만들 수 있는 다섯자리 자연수는 몇 개일까? $5!$이다. 이 가운데 셋을 뽑아 만들 수 있는 자연수는 아래와 같이 `5×4×3`이다. 이를 기호로 $\displaystyle{{}_5 P_3}$이라고 적는다.

이것은 다섯자리 자연수 일의 자리와 십의 자리 수를 모두 `0`으로 바꾼 것과 같으므로 $\displaystyle{\frac{5!}{2!}}$이다. 이와 같이 순서가 있는 것을 순서가 사라지도록 만들려면 같아지는 개수로 나누는 것이다.

이를 일반화하면 $\displaystyle{{}_n P_r =\frac{n!}{(n-r)!}}$ 이다.

같은 것이 있는 순열에서 조합으로

`a a a b b `를 일렬로 나열하는 방법은 어떻게 셀까? 이는 모두가 다르다고 생각한 다음 같아지는 것들의 순서를 사라지게 하면 된다. 다시 말하면 `a_1 , a_2 ,a_3 ,b_1 ,b_2 `를 나열하는 경우의 수 `5!`을 $\displaystyle{ 3!\times2!}$으로 나누면 된다. $\displaystyle{ \frac{5!}{3!2!}}$인데 이것은 서로 다른 5개 가운데 3개를 뽑는 경우의 수와 같다. 이는 $\displaystyle{{}_5 P_3}$ 에서 뽑힌 세 수의 순서를 없앤 것과 같아진다.

순서가 사라진 순열을 조합(Combination)이라 하고 ${}_5 C_3$이라고 쓴다. $\displaystyle{ \frac{{}_5 P_3}{3!}=\frac{5!}{2! 3!}}$ 와 같이 셈한다. 이를 일반화하면 $\displaystyle{{}_n C_r= \frac{{}_n P_r}{r!}= \frac {n!}{r!(n-r)!}}$ 이다.

https://suhak.tistory.com/1234

원순열

이제 동그란 탁자에 둘러 앉는 경우의 수를 생각하자. 다섯 사람이 동그란 탁자에 둘러 앉는 방법은 `4!`이다.원이 $5$번 돌아가면 겹치는 순열 다섯을 하나로 보아야하기 때문이다.

예를 들면 $12345, 23451, 34512, 45123, 51234$는 다른 순열이지만 원으로 만들면 같은 순열이다. 따라서 $\frac{5!}{5}=4!$이다.

일반적으로 서로 다른 `n`개를 원탁에 늘어놓는 순열은 `(n-1)!`이다.

하지만 순열이 순환하는 순열이 있다면 이야기가 달라진다.
` a a b b `로 이루어진 순열은 모두 6개가 있다. 모두 적어보면 `a a b b`, `ab ba`, `b ba a`,` ba ab`,` abab`,` baba`이다. 이 가운데 앞에 있는 넷은 순환하지 않는 순열이므로 원으로 만들면 한 가지 순열이다. 뒤편 둘은 순환마디가 $2$인 순열이므로 마찬가지 한 가지 원순열이다.

보통 `n`개를 늘어놓은 원순열에서 순환하지 않으면 끊어서 선으로 만들때 `n`가지 순열이 나온다. 그러나 순환마디 길이가 `m`이라면 선으로 만들면 `m`가지 순열이 나온다.

따라서 보다 정확하게 원순열을 말하면 한줄로 늘어선 순열에서 순환하지 않는 것과 순환하는 것을 따로 세고 순환마디의 길이가 `m`일 때,

원순열의 개수 `=`순환하지 않는 개수$\displaystyle{ \times \frac{1}{n}+}$ 순환하는 개수$\displaystyle{ \times \frac{1}{m}}$ 이다.

이쯤되면 머리가 좀 아프기 시작한다. 다행스럽게도 고등학교에서 순환하는 것이 들어있는 것은 다루지 않는다.

목걸이순열

원순열을 목걸이라고 생각하면 뒤집을 수도 있으므로 또 달라진다. 여기에선 원순열과 목걸이순열 사이 관계를 알아보자. 대칭인 원순열과 비대칭인 원순열이 다르다. 대칭은 `1:1`로 비대칭은 `2:1` 로 대응된다. 따라서 목걸이 순열과 원순열 사이 관계를 정리하면 아래와 같다.

목걸이 순열의 수`=`대칭 원순열의 수`+`비대칭 원순열의 수$\displaystyle{ \times \frac{1}{2}}$

문제1.  $aabbc$로 이루어진 순열, 원순열, 목걸이 순열의 수를 구해보자.
1. 같은 것이 있는 순열이므로 $\displaystyle{ \frac{5!}{2!2!}=30}$이다.

2. 순환하는 순열은 없으므로 원순열은 $\displaystyle{ \frac{30}{5}=6}$이다.

3. 원순열 가운데 대칭인 것은 둘 $(5,6)$이 있으므로 목걸이 순열은 $\displaystyle{ 2+4\times\frac{1}{2}=4}$이다. 위 그림에서 $1$과 $2, 3$과 $4$는 같은 목걸이이다.

이제 원순열과 목걸이순열이 어우러진 문제를 풀어보자.

문제2. 그림과 같은 정육면체에 $123456$을 적어 넣는 방법은 모두 몇 가지일까?
꼭지점에 달아놓은 번호를 보고 아래와 같이 움직여 보자.
$1 \rightarrow 8, 2\rightarrow 7, 4\rightarrow 5, 3\rightarrow 6$ 처럼 뒤집는 경우 2가지
$1\rightarrow 2\rightarrow 3\rightarrow 4 , 5\rightarrow 6\rightarrow 7\rightarrow 8$처럼 돌리는 경우 4가지
$2\rightarrow 7\rightarrow 4, 1\rightarrow 6\rightarrow 8$ 처럼 `3,5`를 잡고 돌리는 경우 3가지
는 각각 하나씩으로 포개지므로 같아진다.
따라서 $\displaystyle{\frac{6!}{2\times 4\times3}=30}$이다.

$aabcde$를 써 넣는 방법은 몇 가지인가?
같은 것이 둘 있으므로 $\displaystyle{ \frac{30}{2}=15}$이다.

둘러보면 좋은 누리집
하나....maths is fun