문제는 https://gall.dcinside.com/mgallery/board/view/?id=math&no=3878 참고.


정답은 594.


이 게시물에서는 이 문제의 (고교과정 밖의) 해결방법에 대해서, 고등학생들도 이해할수 있는 수준으로 논하고자 한다.


장점은

- 노가다를 거칠 필요 없이 단 한두줄의 계산으로 594라는 결론을 얻을 수 있다는 점과,

- 이렇게 4x4 table을 반 잘라놓은 모양의 young tableau (4,3,2,1) 뿐만 아니라, m x m table을 반 잘라놓은 모양의 young tableau (m,m-1,..,1)에 1,2,..,n을 채워넣을때, row나 column이 증가하면 원소도 weakly increasing하게끔 할 때 경우의 수 또한 셀수 있는, 확장 가능성이 큰 방법이다.


단점은, 계수조합론을 모르는 고등학생이 이러한 방법대로 풀기는 어렵다는 점.


이 문제는 계수조합론에서 밥먹듯 다뤄지는 카탈란 수, Dyck path 등의 개념과 관련이 있다.

위 본문의 시험지에서 주어진 그림에서 발췌한, 아래 그림을 보자.


viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73cee83fa11d02831a8a865d070dfb053de17d9bb368b24fd428c3183c85bf5174e9ef480e13d541c1115fd2a80b31f16c5fd


Dyck path of order n이란, (0,0)에서 출발하여 매 step마다 오른쪽이나 위쪽으로 한칸씩 이동하여 (n,n)까지 도달하는 path들 중에서, 항상 y좌표가 x좌표 이상이 되도록 보존되는 path를 의미한다.


위의 두 그림에서 1, 2, 3을 채우는 방식은 아래 그림을 참고하자.


viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73cee83fa11d02831a8a865d070dfb053de17d9bb368b24fd428c3183880bae7a499dfd85e654504ef73a219e4e8068dc3eaec26caef0

위 그림은 (0,0)에서 (5,5)까지 가는 서로 겹칠수는 있되 교차하지 않는 2개의 Dyck path of order 5를 보여준다. (검은색, 파란색)

위 그림을 보면, 먼저 검은색 Dyck path (of order 5)의 윗부분에 1을 채우고,

파란색 Dyck path (of order 5)의 윗부분 중에서 안 채워진 부분에 2를 채우고,

나머지 안채워진 부분에 3을 채우면 원하는 조건대로 row나 column order대로 숫자가 항상 (weakly) increasing하도록 배치된다.


이렇게 서로 겹칠수는 있되 교차하지 않는, (0,0)에서 (5,5)까지 가는 dyck path 2개의 쌍의 개수가 결국 우리가 원하는 문제가 된다.

그럼 이 경우의 수를 어떻게 셀까? 계수조합론에서는 이런 경우를 세는데 적합한 다음의 정리 (Lindstrom-Gessel-Viennot 보조정리) 가 있다.


https://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma

(** 해당 내용은 위 사이트나 Richard Stanley의 Enumerative Combinatorics Vol. 1의 Theorem 2.7.1 참고.)


Lemma (Lindström–Gessel–Viennot '73, '85).

(1) Cycle이 없는 directed graph D와

(2) 어떤 2개의 서로소인 D의 vertex subset A={a_1,..,a_n}와 B={b_1,..,b_n}이 주어져있고,

(3) N_{i,j}를 a_i에서 b_j까지 가는 D 내의 path들의 개수라고 할 때,


A의 한 점에서 출발하여 B의 한 점에 도착하는, **vertex를 공유하지 않는** n개의 path들을 P_1 , P_2 , ... , P_n이라 하자.

편의상 어떤 permutation f : {1,2,..,n} -> {1,2,..,n}이 존재하여, P_i는 a_i에서 출발하여 b_{f(i)}에 도착하는 path라고 가정할 수 있다.

이러한 path (P_1, ... , P_n)의 sign을 f의 sign으로 정의하자.


A의 한 점에서 출발하여 B의 한 점에 도착하는, vertex를 공유하지 않는 n개의 path들의 sign들의 합은 det(N_{i,j}) 이다. (1≤i,j≤n)



이 보조정리의 증명은, 위키피디아에도 나와있듯 이해하는데 그렇게 어렵지 않으므로 참고.

다만 우리가 고려하는 Dyck path는 교차하지 않을 뿐이지 서로 겹칠수 (vertex를 공유할 수) 있기 때문에, 바로 위 보조정리를 적용할수는 없다.

따라서 맨 위에 있는 path 하나를 위로 한칸 끌어올려서, 다음 그림과 같이 서로 겹치지 않게끔 만드는 변형이 필요하다.



viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73cee83fa11d02831a8a865d070dfb053de17d9bb368b24fd428c3183880bae7a499dfd85e654504ef73a28c94e826b8c3effc26caef0

위 그림은 2개의 서로 겹치지만 교차하지는 않는 Dyck path를 xy평면을 45도 눕혀서 표현한 그림이다.

위 그림과 같이, 좌측의 검은색으로 그래진 2개의 겹칠수 있되 교차하지 않는 Dyck path of order 4가 있다면

위쪽의 검은색 Dyck path를 한칸 위로 상승하고 (x와 y좌표를 각각 하나씩 더해서 상승), 시작점과 끝점에 꼬리를 붙이면 Dyck path of order 5가 된다.

그러면 2개의 서로 겹치지 않는 Dyck path of order 5와 Dyck path of order 4가 만들어지게 된다.


이제 두 시작점 (-1,-1)과 (0,0)을 a_1 , a_2, 두 끝점 (4,4)와 (5,5)를 b_1 , b_2라 하자.

방향그래프 D를 다음과 같이 정의하자.

- 충분히 큰 자연수 N에 대해서, D의 vertex set은 -N≤x≤y≤N을 범위 내의 격자점 (x,y)들로 구성되어있고,

- D의 edge set은 -N≤x≤y<N 범위 내에서 ((x,y), (x+1,y))와 ((x,y),(x,y+1)) 형태의 pair들의 모임으로 정의해줄 수 있다.


그렇다면,

- 위 그림의 우측의 두 Dyck path는, 서로 vertex를 공유하지 않는 D에서 a_1에서 b_2로 가는 Dyck path (of order 5)와 a_2에서 b_1로 가는 Dyck path (of order 4)가 된다.

- 그리고 A에 있는 vertex를 시작점으로 갖고 B에 있는 vertex를 끝점으로 갖는 서로 vertex를 공유하지 않는 2개의 path는, 항상 a_1에서 출발한 녀석은 b_2에서 끝나야하고 a_2에서 출발한 녀석은 b_1에서 끝나야 한다. (만약 두 path가 a_1 -> b_1 , a_2 -> b_2의 path로 이루어져 있다면 겹칠수밖에 없다.)

결국 두 path가 겹치지 않으려면 f(1)=2, f(2)=1이므로, sign은 항상 -1이 된다.


이제 Lindstrom-Gessel-Viennot 보조정리를 적용할 수 있다. 본래 문제에 적용을 한다면, a_1=(-1,-1) , a_2=(0,0) , b_1=(5,5) , b_2=(6,6)이라 두면,

N_{1,1} = Dyck path of order 6의 갯수 = C_6 (6th Catalan number)

N_{1,2} = Dyck path of order 7의 개수 = C_7 (7th Catalan number)

N_{2,1} = Dyck path of order 5의 개수 = C_5 (5th Catalan number)
N_{2,2} = Dyck path of order 6의 개수 = C_6 (6th Catalan number)


(* 카탈란 수에 대한 내용은 https://en.wikipedia.org/wiki/Catalan_number 참고.)


따라서 우리가 원하는 값은 sign (= -1) * det(N_{i,j}) = (-1) * (C_6^2 - C_5 * C_7)

인데, C_5 = 42, C_6 = 132, C_7 = 429니까, 42 * 429 - 132^2 = 18018 - 17424 = 594가 원하는 답이 된다.



이 아이디어를 그대로 확장하면 다음 결론을 내릴수 있다.


따름정리.

이를 확장하여 m x m을 반 잘라놓은 young tableau (m,m-1,..,1)에 1,2,3,...,n을 채워넣되, row나 column이 증가하면 값도 weakly increasing하도록 하는 경우의 수는 정확히 det(C)이다.

(C는 (n-1)x(n-1) 행렬으로, (i,j)번째 entry가 C_{m+i+j-1}인 행렬, C_{m+i+j-1}은 m+i+j-1번째 Catalan 수)


e.g)

예를 들어서 위의 594라는 답은 n=3, m=4를 대입하면

C_5 C_6

C_6 C_7

으로 구성된 행렬의 determinant를 구하는 것이고, 594를 얻을수 있다.



개인적인 생각.

여기서는 Lindström–Gessel–Viennot를 사용했지만, 개인적인 생각에는 bijective한 깔끔한 증명법이 존재할 것 같다.

일단 한두시간 생각해본 결과, 생각보다 잘 모르겠고, 이러한 Dyck path들의 lattice 위의 고정된 길이의 chain의 경우의 수와 관련된 문헌조사를 해도 쉽게 구할 수 있는 방법을 논한 논문을 발견하지 못했다.



References.

관련된 내용에 더 관심이 있으면, 다음 논문을 참고하면 된다.

Ferrari L, Munarini E. Enumeration of chains and saturated chains in Dyck lattices. Advances in Applied Mathematics. 2015.

https://www.sciencedirect.com/science/article/pii/S0196885814001080


관련된 책.

Richard Stanley, Enumerative combinatorics Vol 1 & 2, Cambridge Studies in Advanced Mathematics.

(Lindstrom-Gessel-Viennot 정리는 1권의 Theorem 2.7.1)


아래는 관련된 내용의 wikipedia.

Young tableau : https://en.wikipedia.org/wiki/Young_tableau

Catalan number : https://en.wikipedia.org/wiki/Catalan_number

Lindström–Gessel–Viennot lemma : https://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma

Schur polynomial : https://en.wikipedia.org/wiki/Schur_polynomial