n차원 그 이상의 카탈란수

카탈란수 하면 2xn 블록을 차례대로 쌓는거랑 동치다. 이해를 쉽게 틀을 45도 정도로 회전하고 중력의 영향에 의해 블록을 쌓는다 생각하면 된다. 또한 다른 예시로 n*n을 조건에 맞게 이동하는 것과 같다.(위아니면 오른쪽인데 위로 가는건 총 오른쪽으로 간 횟수보다 많으면 안된다.)

여기까지는 수학에 관심이 깊은 사람이면 알만하다. 근데 대부분 그 이상을 모를 것이다. n*n*n을 x,y,z로 이동 가능한데, 총이동 거리가 x>=y>=z가 되게 이동하는 경우의 수라 확장하고, 3차원 카탈란수라 이름 지을 수 있다. 사실 카탈란수는 이런 기하적인 예시와 전혀 관련이 없고 이항계수에서 유래되었기에 3차원 카탈란수라 이름 짓기에는 오류가 생기는데 팩트가 사람들은 아마 이런 기하적 예시로 카탈란 수를 기억하기 때문에 3차원이라 말하는 것이 가장 이해하기 쉽고 타당할 것이라 생각했다. 

 쨋든 이런거에도 공식이 있다. length hook의 법칙이었나 해서 칸수의 팩토리얼읠 각 영 다이어그램으로 나타냈을때 훅의 길이로 전부 나누면 되는데 궁금하면 찾아보고 그냥 공식이 존재한다라는 사실만 알자. 이런식으로 n*n에서 블록을 쌓는 방법도 이 공식을 이용하면 금방 구할 수 있고, 그 드래그 하는 칸에 따라 값을 알려주는 사이트도 찾아보니 있었다. 

 여기서 난 궁금증이 생겼다.'이걸 만약 n*n*n으로 블록을 쌓으면 어떻게 되지?' 이 질문이 재밌는게 n차 카탈란 수를 2차원에서의 블록 쌓기로 대응했는데, 이거 자체를 3차원으로 해버리면.. 뭐라 명명해야할지 감이 안잡힌다. 하나의 수로 나타낼 수 없기 때문에 이제 뭐 순서쌍으로 나타낼 수 있다. 그럼 이전 카탈란 수는 (2,2,n)가 되고 n차 카탈란 수는 (2,n,n)이 된다. 여기서 (3,~,~)에 대한 연구를 해보겠다는 소리이다.

 

def backtrack(added, remaining):

    """백트래킹으로 가능한 모든 추가 순서를 탐색"""

    global count

    if not remaining:  # 모든 벡터를 추가했을 경우

        count += 1

        return

    for v in sorted(remaining):  # 남은 벡터 중 하나를 추가 시도

        x, y, z = v

        if (x == 0 or (x-1, y, z) in added) and \

           (y == 0 or (x, y-1, z) in added) and \

           (z == 0 or (x, y, z-1) in added):

            added.add(v)

            remaining.remove(v)

            backtrack(added, remaining)

            remaining.add(v)  # 백트래킹 (원상복구)

            added.remove(v)

# 입력 처리

n = int(input().strip())  # 첫 줄에서 점 개수 입력받기

vector_set = set()

for _ in range(n):

    vector_set.add(tuple(map(int, input().split())))

# 백트래킹 수행

count = 0

backtrack({(0,0,0)}, vector_set - {(0,0,0)})

# 결과 출력

print(count)

 

2*2*2인 블록을 채우는 경우는 해보면 48가지가 나오는데 저 코드로 해보니 값이 잘 나온다. 그 밖의 값도 테스트 하니까 잘 나왔다. 

 근데 3*3*3 인 경우를 테스트 해보려하니 20분 동안 계산만 하길래 일단 보류로 냅뒀다.

아무리 회전시켜서 같은 경우 배제하면서 수형도 그리며 노가다 해도  아 잠만 원래 하루 정도면 되겠지라 생각했는데 다시 생각해보니 잘 모르겠다 하하 쨋든 27!보다는 작은 경우의 수가 나올것이다ㅋㅋ

 더 좋은 알고리즘이야 만들면 되겠지만 너무 브루트 포스처럼 노가다 성격이라 수학적 공식말고는 비슷비슷 할 것같다.

 

같은 방법으로 (n,n,n) 카탈란 수도 코드로 구현할 수 있긴 하지만 테스트는 더 의미없게 큰 수치가 될것이다.

 

 

 이제 수학적으로 분석해보려 한다. 설마 hock-lengeth으로 될까라는 마음으로 해봤는데 역시나 아니었고 다른 공식을 만들어야 하는데... hock-length도 못 만든 내가 이걸 할 수 있을까 쨋든 누군가 증명해주면 좋겠다.

 

 

 

마지막으로 망상을 좀 더해보자면, (n,n,n)까지는 뭐 된다 치는데 그 다음을 어떻게 기하학적으로 직관적인 예시를 만들 수 있을까 고민이다. 심지어 어떻게 수학적으로 확장시킬지도 까마득 하다. 일단 그 n차원 좌표를 이동하는 것을 평면에다가 박스 쌓는걸로 확 줄인거부터가 말도안되는 아이디어라 아마 이런식으로 요소를 축소시키면 될 것 같은데 그걸 모르겠다.분명(n,n,n,n)처럼 계속 요소를 추가할 수 있는데 일단 가능성만 열어두고 머리 아프니까 공상 그만하려 한다.