Tip:
Highlight text to annotate it
X
36개의 유일한 카드들을 사용하는 카드 게임:
카드는 4벌이고 (다이아몬드, 하트, 클럽, 그리고 스페이드), space가 아니고 spade입니다,
각각 1에서 9까지 숫자가 매겨져 있습니다.
손 (Hand)을 뽑습니다.
손 (Hand)은 9장짜리 카드 묶음이며,
순서는 player 마음대로 배열할 수 있습니다.
됐죠.
얼마나 다양한 9장짜리 손(hand)을 구성할 수 있을까요?
자, 생각해 봅시다.
36장의 유일한 카드들이 있어요, 그리고 저는 신경쓰지 않을 거지만
알다시피 각각의 무늬마다 9개의 숫자들이 있고, 총 4가지 무늬가 있죠
4 x 9 는 36.
하지만 그냥 1에서 36까지의 카드가 있다고 생각합시다.
그리고 우리는 그 중 9개를 고를 거예요.
그럼 우선 우리는, 제 손(hand)에 9개의 빈 칸이 있다고 할 수 있습니다
그렇죠?
1, 2, 3, 4, 5, 6, 7, 8, 9.
맞죠?
내 손(hand)을 구성하기 위해 9장의 카드를 뽑을 겁니다.
그러면 첫 번째 카드에 대해서 나는
몇 가지 가능성을 갖고 있을까요?
네, 36가지 카드가 있으므로 첫 번째 슬롯에 대해서는
36가지 가능성이 있죠.
하지만 그 다음엔 그 카드는 제 손(hand)의 일부가 되었습니다.
이제 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 가지 손(hand)이 가능하다고 생각할지도 모르겠습니다.
만약 순서까지 고려한다면 이것은 정답일 것입니다.
만약 내가 15가 쓰여진 카드를 여기에 갖고 있다면...
만약... 여기 써 볼게요, 만약 내가 스페이드 9를 여기에,
그리고 많은 카드들이 있죠.
그리고 만약 내가... 이게 하나의 손(hand)이 되고요,
그리고 또 다른 손(hand)이 있습니다.
그러니까 카드 1, 2, 3, 4
5, 6, 7, 8.
나는 8개의 다른 카드들을 갖고 있죠.
혹은 다른 손(hand)은 다음과 같이 내가 8개의 카드를 갖고,
1, 2, 3, 4, 5, 6, 7, 8, 그리고 여기에 스페이드 9 을 가질 수도 있죠.
만약 우리가 이 두 가지를 서로 다른 손(hand)으로 여긴다면
왜냐하면 우리는 정확히 똑같은 카드들을 갖고 있지만,
그것들이 배열된 순서가 다르고, 그러면 제가 방금 전에 계산한 것은
말이 됩니다, 왜냐하면 그것은 순서에 기반하고 있으니까요.
하지만 문제에서 카드들은 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 팩토리얼 (factorial)이라 부르고,
느낌표를 써서 9 ! 로 표현합니다.
그러니까 만약 우리가 모든 가능한 방법에 대해 생각한다면,
손(hand)을 구성하기 위한 모든 조합의 숫자를요,
이것은 우리가 순서를 고려할 때의 경우의 수가 될 것입니다,
하지만 우리는 내부적으로 재배열할 수 있는 경우의 수로 나누어
중복해서 세지 않도록 해야 합니다.
이것이 답이 될 것이고,
이것이 정답입니다.
이제 이것은 엄청, 엄청나게 큰 숫자입니다.
이 숫자가 얼마나 큰지 알아보죠.
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장의 카드로 손(hand)을 구성하는 방법 수는
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 개를 어떤 순서로 뽑았느냐는 중요하지 않습니다.
그러니까 그게 우리가 여기서 한 일이죠.