[이전문서] N×N×N 큐브의 경우의 수 유도 - N×N×N 큐브

이 포스트는 약 8년쯤 전에 모 클럽에 큐브 관련 연구글로 올렸던 글이다. 지금 보면 부끄러울 정도로 경험과 직관에 의존해서 썼던 글이긴 하지만, 다시 보니까 그래도 한가지에 참 열정적으로 빠져있었구나 하는 생각이 든다. 우연히 클럽을 다시 들어갔다가 이 글을 발견하여 이쪽 블로그로 옮겨본다.

---

이제 드디어 일반적인 큐브의 경우에 있어서의 경우의 수를 구하게 됩니다. 아래부터는 약간의 수학적 계산이 포함되기는 하지만, 고 2 정도의 수학 수준이면 내용을 이해 하는데는 아무런 문제가 없을것으로 보이네요.

우선 머리속으로 6×6×6 큐브와 7×7×7 큐브를 생각해 봅시다. 일단 두 큐브 모두 여덟개의 코너 조각은 공통으로 가지고 있습니다. 일반적인 N×N×N 큐브도 마찬가지죠.

$$ 7! \times 3^6 $$

그 다음에 3×3×3 큐브가 가지고 있었던 엣지 조각과 센터 조각의 경우는 어떨까요? 7×7×7 큐브의 경우는 두가지 모두를 가지고 있지만, 6×6×6 큐브와 같은 경우는, 엣지 조각과 센터 조각을 가지고 있지 않습니다. 일반적으로 큐브를 홀수차 큐브와 짝수차 큐브로 구분지었을때, 홀수차 큐브에서만 나타나는 특징입니다.

$$ \left( 24 \times 12! \times 2^{10} \right)^{n \; \text{mod}2} $$

이제 마지막으로 4×4×4 큐브에서부터 관찰 가능했던, 엣지 조각들과 센터 조각들 (3×3×3 큐브의 엣지 조각, 센터 조각과는 다른 개념입니다. 달리 표현할만한 말이 없어서 헷갈림에도 부득이하게 같은 용어를 사용했어요;;) 의 경우 큐브의 크기가 커질수록 이 조각들의 개수도 점점 커져 나가는것을 볼 수 있습니다. 따라서 실제로 N×N×N 큐브의 경우의 수를 구하는 문제는 결국, N×N×N 큐브의 엣지 조각과 코너 조각의 개수를 따지는 문제로 귀결되겠군요.

우선 4×4×4 큐브와 5×5×5 큐브를 구하면서 이용했던 엣지 조각과 센터 조각의 경우의 수를 구하는 공식입니다.

$$ \frac{(24!)^{P}}{(4!)^{Q}} $$

4×4×4 큐브에서는 P 값은 3, Q 값은 6이었고, 5×5×5 큐브의 경우 P 값이 3, Q 값은 12였었죠? 위 식에서 우리는 이제 P 값과 Q 값을 찾아 내야 합니다. 일단 규칙을 찾아 보기 위해서 N이 커져감에 따라 P 값과 Q 값이 어떻게 변화해 나가는지 살펴 봅시다.

    N : 4 5 6 7 8 9 10 11 12

    P : 2 3 6 8 12 15 20 24 30

    Q : 6 12 24 36 54 72 96 120 156

위의 표를 보시면 아시겠지만, 규칙이 보이질 않습니다. (실제로 P 값의 경우, 공차가 1 3 2 4 3 5 4 6 이런식으로 증가하고, Q 값의 경우, 공차는 6 12 12 18 18 24 24 로 증가하여 규칙은 있지만, 두가지 모두 식으로 표현해낼 방법이 없습니다;;) 그렇다면, P 값을 홀수차와 짝수차로 구분해서 나타내 보기로 하죠. 우선 계산의 편의성을 위해서 4부터 시작하는 N 값들을 1부터 시작하는 수열이라고 보도록 합시다.

    N 값이 2m-1 일때, P : 2 6 12 20 30...

    N 값이 2m 일때, P : 3 8 15 24...

으로 두 식 모두 각각 계차 수열이 됩니다. 이제 계차 수열을 구하는 식을 이용하여 두 식 모두 수열을 구해보면, 첫번째 식의 경우

$$ \begin{aligned} P(2n) & = 2 + \sum_{k=1}^{n-1}(2n+2) \\ & = 2 + 2 \times \frac{n(n-1)}{2} + 2(n-1) \\ & = n^2 + n \\ & = n(n+1) \end{aligned} $$

가 되고 두번째 식은,

$$ \begin{aligned} P(2n-1) & = 3 + \sum_{k=1}^{n-1}(2n+3) \\ & = 3 + 2 \times \frac{n(n-1)}{2} + 3(n-1) \\ & = n^2 + 2n \\ & = n(n+2) \end{aligned} $$

가 됩니다. 하지만 위 두식은 짝수차 항, 홀수차 항을 각각 나타내 준 것이므로, 위식을 전체항의 식으로 환산해 내기 위하여, 짝수항일때 N=2m, 홀수항일때 N=2m-1 임을 이용하여 다시 식을 바꾸어 주면

홀수차항일때 수열 P는,

$$ \begin{aligned} P(N) & = \frac{N+1}{2} \left( \frac{N+1}{2} + 1 \right) \\ & = \frac{N^2 + 4N + 3}{4} \end{aligned} $$

또한 짝수차항일때 수열 P는,

$$ \begin{aligned} P(N) & = \frac{N}{2} \left( \frac{N}{2} + 2 \right) \\ & = \frac{N^2 + 4N}{4} \end{aligned} $$ 

가 됨을 알 수 있습니다. 이제 위 두식을 단순 비교해 보도록 하겠습니다. 홀수차항일때의 수열 P는 짝수차항일때의 수열 P보다 3/4가 크죠? 따라서 홀수차항일때의 식에서 가우스 기호를 씌우게 되면, 홀수차항일때는 그대로 정수가 나오고, 짝수차항일때는 원하는 수보다 3/4가 크게 나오지만 가우스 기호에 의해 원하는 정수 값이 나오게 될것입니다.

$$ \begin{aligned} P(N) & = \left[ \frac{N^2 + 4N + 3}{4} \right] \\ & = \left[ \frac{(N+1)(N+3)}{4} \right] \end{aligned} $$

자.. 이제 마지막으로 한번만 더 변환을 해주면 됩니다. 아까전에 실제로는 4부터 시작하는 P 값들을 계산의 편의를 위해서 N이 1부터 시작하는 순열 P로 바꾸어 주었었죠? 따라서 N대신에 n-3을 대입해 주어야 합니다.

$$ P(n) = \left[ \frac{n(n-2)}{4} \right] $$

드디어 우리가 원하면 P 값을 구하는 공식을 찾았군요. 마찬가지 방법으로 Q 값을 구하는 공식을 찾아 보면 다음과 같습니다. (Q값들을 6으로 나누어준 후에 위의 과정을 그대로 밟아 나가면 P값보다 쉽게 공식을 찾아낼 수 있습니다.)

$$ Q(n) = 6 \times \left[ \frac{(n-2)^2}{4} \right] $$

이제 여태까지 구한 모든 식들을 종합해 봅시다.

$$ \lbrace 7! \times 3^6 \rbrace \times \lbrace (24 \times 12! \times 2^{10})^{n \; \text{mod}2} \rbrace \times \left\lbrace \frac{(24!)^{\left[ \frac{n(n-2)}{4}\,\, \right]}}{(4!)^{6 \left[ \frac{(n-2)^2}{4}\,\, \right]}} \right\rbrace $$

위 식을 다시 정리하면 다음과 같습니다.

 $$ \frac{(24 \cdot 2^{10} \cdot 12!)^{n \; \text{mod}2} \cdot 7! \cdot 3^6 \cdot (24!)^{\left[ \frac{n^2 - 2n}{4}\,\, \right]}}{(4!)^{6 \left[ \frac{(n-2)^2}{4}\,\, \right]}} $$

어디서 많이 보던 식이죠? ^^;;