대수경에 조합론 문제 이렇게 어렵게 나온 건 처음인듯

조합론 잘 몰라도 최대한 이해 잘 되게 써 봤는데, 그러다보니 글이 좀 긴 편임


ㅡㅡㅡㅡㅡㅡ


우선 순열 f에 대해 f(i)=j, f(j)=i, i<j를 만족하는 (i, j) 순서쌍을 '교환쌍'이라 하고, f(i)=i인 i를 '고정점'이라 하자.

그럼 조건 만족하는 임의의 순열은 1~n을 다음 조건 만족하게 교환쌍&고정점들로 분할한 것과 일대일대응이 됨;

i<j<k<l을 만족하는 두 교환쌍 (i, l), (j, k)는 존재하지 않는다.


일단 조건 만족하는 수열에서 교환쌍&고정점들 찾으면 위 조건 만족함은 자명하고, 역으로 위 조건 만족하는 교환쌍&고정점 분할 가지고 순열 만들면 그게 조건 만족하는 순열인 것도 증명됨.

(이건 엄밀히 증명하자면 걍 pi(a)>pi(b)>pi(c)>pi(d)인 a<b<c<d 있다 가정하고 a가 무언가랑 교환쌍 이루는 경우, 고정점인 경우 케이스 나눠 노가다 분석 해보면 항상 모순 터져서 증명됨. 별로 복잡하진 않음.)


암튼 이렇게 얻은 [n]={1, ..., n}의 교환쌍&고정점 분할에 대해, k\in [n]이 고정점이면 (1, 0) 벡터를, 어떤 교환쌍의 앞쪽 수면 (1, 1) 벡터를, 어떤 교환쌍의 뒤쪽 수면 (1, -1) 벡터를 부여하는 식으로 이 세가지 벡터 중 하나로 각 성분이 구성된 길이 n인 수열을 만들자.


그러면 (0, 0)에서 시작해 이 수열의 벡터들 따라 이동 시 최종적으로 (n, 0)에 도달하고, 그 과정에서 한번도 y<0 쪽으로는 내려가지 않음. 

역으로 (0, 0)에서 (n, 0)까지, y=>0 영역 내에서 매번 (1, -1), (1, 0), (1, 1)중 한 벡터 택해 이동하는 식으로 가는 임의의 경로는 반드시 어떤 [n]의 교환쌍&고정점 분할에 대응됨.

(사용한 (1, 1) 벡터와 (1, -1) 벡터 개수가 같으니 (1, 1)들을 앞에서부터 1, 2, ...로 번호 매기고 (1, -1)들을 앞에서부터 1, 2, ...로 번호 매긴 다음 각 k에 대해 k번째 (1, 1)과 k번째 (1, -1)들 짝지어 교환쌍들 만들고, 나머진 전부 고정점으로 두면 됨.)


이때 위에서 말한 종류의 경로를 Motzkin Path, 저런 Path의 총 개수를 Motzkin Number M_n이라 하는데, 위의 증명이 결국 M_n=a_n임을 보이는 bijection 증명이 됨. 이 Motzkin Number는 Catalan Number 비슷한 수라 비슷한 꼴의 점화식도 만족하는데, 물론 그걸 써도 되기는 하지만 아래의 또 다른 점화식을 쓰는 게 더 쉬움.


M_n=(2n+1)M_{n-1}/(n+2)+(3n-3)M_{n-2}/(n+2)


위 식과 M_1=1, M_2=2라는 초깃값들 쓰면 n=>3일 때3^n/n^2<M_n<3^n이 증명되고, 그럼 3/n^(2/n)<M_n^(1/n)<3이라서 극한이 3임이 증명됨.


ㅡㅡㅡㅡㅡㅡㅡ


물론 나도 현장에선 못 풀고 집 와서도 a_n 관련된 점화식까지 찾긴 했는데 그게 도무지 쉽게 정리가 안 됐음. 구글링좀 해보니 Motzkin Number랑 똑같다길래 둘 사이에 뭔 bijection이 있나 좀 고민해 보니 허무하게 쉽게 풀리더라... 물론 내 풀이가 맞다면

어쨌든 Motzkin Path 방향으로 생각 안해봤음 못 풀었을듯


공식 풀이는 저런 Motzkin Number 개념과 점화식까진 안 쓰고 적당히 쉬운 lower/upper bound 잡아서 푸는 것일 것 같긴 한데, 아직 그 방향으론 생각 안해봄