조합 예제 : 카드 9장을 뽑는 법

36개의 카드를 사용하는 게임 카드는 4벌이고 ,다이아몬드, 하트, 클럽과 스페이드인데요 스페이스가 아니라 스페이드 입니다 각각 1에서 9까지 숫자가 매겨져 있습니다. 손을 뽑고 9장의 카드 묶음인 손은 다양하게 정렬될수있어요 9개의 손은 몇개가 가능할까요? 그닥 신경쓰이지 않지만 36장의 유일한 카드들이 있어요, 알다시피 각각의 무늬마다 9개의 숫자들이 있고, 총 4가지 무늬가 있어요 4 x 9 는 36. 하지만 그냥 1에서 36까지의 카드가 있다고 생각합시다. 그리고 우리는 그 중 9개를 고르겠습니다 그럼 우선 우리는, 제 손에 9개의 빈 칸이 있는게 됩니다 그렇죠? 1, 2, 3, 4, 5, 6, 7, 8, 9. 맞죠? 손을 구성하기 위해 9장의 카드를 뽑을건데요 그러면 첫 번째 카드에 대해서 몇 가지 가능성을 갖고 있을까요? 네, 36가지 카드가 있으므로 첫 번째 슬롯에 대해서는 36가지가 가능하죠. 하지만 그 다음엔 그 카드는 제 손의 일부가 되었습니다. 이제 2번째 칸에 대해서는 몇 개나 남아 있을까요? 음, 이미 하나를 뽑았고, 그러니까 이제는 35개 중에서 하나를 뽑아야 합니다. 그 다음에 3번째 칸에 대해서는 34, 이런 식으로 계속 가는거에요 33개 중 하나, 그 다음엔 32, 31, 30, 29, 그리고 28. 그러니까 답은 36 x 35 x 34 x 33 x 32 x 31 x 30 x 29 x 28 가지 손이 가능하다고 생각 할 수있습니다 순서를 고려한다면 이것은 정답이 되죠 만약 15가 쓰여진 카드를 여기에 갖고 있다면. 만약... 여기 써 볼게요, 만약 내가 스페이드 9를 여기에, 그리고 많은 카드들이 있죠. 그리고 만약 내가... 이게 하나의 손이 되고요, 그리고 또 다른 손이 있습니다. 그러니까 카드 1, 2, 3, 4 5, 6, 7, 8. 나는 8개의 다른 카드들을 갖고 있죠. 혹은 다른 손은 다음과 같이 내가 8개의 카드를 갖고, 1, 2, 3, 4, 5, 6, 7, 8, 그리고 여기에 스페이드 9 을 가질 수도 있죠. 만약 우리가 이 두 가지를 서로 다른것으로 본다면 정확히 똑같은 카드들을 갖고 있지만, 배열순서가 다르기때문에 , 방금 전에 계산한 것은 맞습니다. , 왜냐하면 그것은 순서에 기반하고 있으니까요. 하지만 문제에서 카드들은 player가 원하는 대로 재배열될 수 있다고 했으니, 순서는 고려하지 않는 것입니다. 그러니까 중복해서 헤아린 것이죠. 우리는 같은 숫자의 카드들이 배열될 수 있는 모든 경우들을 센 것입니다. 중복를 피하기 위해 이 결과를 9개의 카드가 재배열될 수 있는 경우의 수로 나눠줘야 합니다. 즉 이 결과를 9장의 카드가 재배열될 수 있는 경우의 수로 나눠줘야한다는거죠 그러면 9장의 카드가 재배열되는 경우의 수는 몇 가지일까요? 9장의 카드가 있고, 그 중 하나를 뽑아서 첫 번째 칸에 두려 한다면, 그렇습닌다 , 첫 번째 칸에 뭔가를 두는 데 9가지 방법이 있겠죠. 그러면 두 번째 칸에 대해서는 카드를 놓는 8가지 방법이 있을 거고요. 왜냐하면 하나를 뽑아 첫 번째 칸에 두었으니 8개만 남았겠죠 그 다음엔 7, 그리고 6, 5, 4, 3, 2, 1. 마지막 칸에 대해서는 단 1장의 카드만 남아있을 거예요. 그러니까 여기 이 숫자, 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1, 혹은 9.. 여러분은 9에서 시작해서 9보다 작은 모든 숫자들을 곱한것입니다. 모든, 9보다 작은 자연수라고 말할수있습니다. 이것을 우리는 9 팩토리얼 라 부르고, 느낌표를 써서 9 ! 로 씁니다 그러니까 만약 우리가 모든 가능한 방법에 대해 생각한다면, 손을 구성하기 위한 모든 조합의 숫자를요, 이것은 우리가 순서를 고려한 경우의 수가 될 것입니다, 하지만 우리는 내부적으로 재배열할 수 있는 경우의 수로 나누어 중복되지 않게 해야해요 이것이 답이 될 것이고, 이것이 정답입니다. 이제 이것은 아주아주 엄청나게 큰 숫자입니다. 이 숫자가 얼마나 큰지 알아보죠. 36... 약간 왼쪽으로 이동할게요, 36 x 35 x 34 x 33 x 32 x 31 x 30 x 29 x 28. 이렇게 할 수 있겠죠. 괄호를 써서... 나누기 괄호... 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1. 자, 다행히도 계산기로 이 숫자를 연산할수있어요 그 결과는 94,143,280입니다. 읽을수 있게 옆으로 치워둘게요,. 여기 이 숫자는 94,143,280입니다. 그러니까 이게 이 문제에 대한 답이죠. 9장의 카드로 손을 구성하는 방법 수는 94,143,280가지가 있습니다. 지금까지 우리는 그냥 계산을 했는데 왜 그렇게 되는지 이유도 생각해 봤고요. 이것과 실질적으로 똑같은 일을 하는 공식이 있습니다. 그리고 사람들이 이 공식을 표현하는 방식은, 보시다시피 우리는 36가지 물건을 갖고 있고 그 중 9개를 골라야 합니다, 그렇죠? 그리고 우리는 순서에 대해 별로 신경쓰지 않아서 그래서 때론 그것을 nCk (n choose k)라고 씁니다. 적어 볼게요. 우리가 그럼 여기서 뭘 한 걸까요? 우리는 36개를 갖고 있습니다. 우리는 9개를 골랐죠. 그러니까 여기 있는 분자는 36! 이었고, 그런데 36!은 27, 26, 25... 계속 내려가겠죠. 쭉 진행됩니다. 하지만 우리는 36으로부터 9만큼 떨어진 곳에서 멈췄습니다. 따라서 이건 36! 이니까, 여기 이 부분은, 저 부분은 단순히 36! 이 아닙니다. 그것은 36! 을 (36-9) ! 로 나눈 것입니다. 36 - 9 가 뭐죠? 27입니다. 그러므로 27!, 이것에 대해 생각해 봅시다, 36!은 36 x 36 x ...계속 가다가... x 28 x 27, 이렇게 1까지 가겠죠. 이게 36! 입니다. 그러면 36 - 9 의 계승(factorial)은 뭘까요? 27! 이네요. 만약 27! 로 나눈다면, 27!은 27 x 26 x ... 1까지 곱한 것입니다. 이 둘은 정확히 같습니다. 이것은 27 x 26.. 그러니까 이것들은 소거됩니다. 그러니까 만약 36! 을 (36-9)! 로 나누면 36! 중 가장 큰 9개의 항의 곱만 남게 될 테고 그게 여기 있는 것입니다. 자 되었습니다 그리고 우리는 이것을 9!로 나눴습니다. 그리고 우리는 이것을 9!로 나눴습니다. 그리고 이것은 36 choose 9 라고 불립니다. 그리고 가끔 이 공식을 다음과 같이 쓴 것을 보게 될 거예요, n C k (n choose k). 이 공식은 다음과 같이 씁니다: n! 나누기 (n-k)!, 그리고 분모에 하나 더 k! 까지. 이것이 당신이 n개의 물건을 갖고 있는데 순서를 생각하지 않고 n개 중 k개를 고를 때 선택가능한 모든 경우의 수를 세는 일반적인 공식입니다. 오로지 중요한것은 선택된 k개가 무엇이냐 하는 것이죠, 그 k 개를 어떤 순서로 뽑았느냐는 중요하지 않습니다. 그것이 여태 우리가 알아본것이죠