[일반] 조합 문제 코딩해서 풀어봄

[기괴공학도(mecheng98)]

답은 594 나옴.

[기괴공학도(180.67)]

http://m.dcinside.com/board/math/3878

[익명(61.74)]

그냥 구할 수는 없는건가... 너무 노답인데;; - dc App

[익명(61.74)]

어떻게 이런 문제를 낸거지;; - dc App

[기괴공학도(180.67)]

PS 마이너 갤러리에 물어봤는데 왼쪽 줄 채운 다음에 계산하라고 했어요.

[Rafle(probaroque)]

손으로 풀었는데 회식 끝나고 업로드해볼까 생각 중.. 특별한 아이디어가 없이 케이스 나눈거라 좀 그렇네

[익명(180.67)]

올려주세요!!

[웨리(211.36)]

가장 아랫쪽 길이 2짜리를 간단하게 못풀겠다 저게 시험 문제인 고딩들도 있구나 ㅡㅡ - dc App

[익명(45.64)]

(0,0)에서 (5,5)로 가는 Dyck path of order 5들을 포함관계로 lattice를 형성했을때 (여기서 두 dyck path P1, P2에 대해서 P1≤P2는, P2가 P1 밑으로 겹치는 것을 허용하는 형태로 들어가는 경우를 의미) 길이가 2인 multichain의 개수를 세는 것과 동일함.

[익명(45.64)]

https://www.sciencedirect.com/science/article/pii/S0196885814001080
이 논문의 Proposition 3.1에서 k=1, n=5인 경우에 해당함. C_n은 n번째 catalan 수를 의미. 저 Proposition에 의하면 C_5*C_7 - C_6^2인데, C_5=42, C_6=132, C_7=429임을 염두에 두면 42*429 - 132^2 = 594.

[익명(45.64)]

아, 길이가 2라기보단 구성하는 원소의 개수가 2개인 multichain의 개수라고 하는게 더 정확하겠네.

[익명(45.64)]

어쨌든 확장도 가능한데, 저렇게 4x4 꼴 반 잘라놓은 young tableau가 아닌 m x m 꼴 반 잘라놓은 것에 1,2,3이 아닌 1,2,...,n을 저 규칙을 따르면서 채워넣는 경우에는, (0,0)에서 (m+1,m+1)으로 가는 Dyck path of order m+1들의 lattice에서 원소 개수가 n개인 multichain의 개수를 세는 문제와 동일하고, 마찬가지로 저 Proposition 3.1의 식을 이용하면 됨.

[익명(45.64)]

저 Proposition 3.1은 Lindstrom-Gessel-Viennot lemma를 그냥 갖다쓴것에 불과하니, 구글링해서 위키피디아 참고.