[일반] 최단경로말고 그냥 경로 경우의수는 어떻게구하나요

[익명(121.173)]

m*n 분할면에서

좌측최상단 꼭짓점에서 시작해

우측최하단 꼭짓점까지 이동한다.

단 왔던길을 되돌아갈 수는 없다.

이때 경우의수가 어떻게 표현되나요?

[익명(110.35)]

상식적으로 생각해도 무한이많겠지

[익명(121.173)]

왔던길을 못되돌아가면 한정되지 않나요? 1*1평면은 2가지, 2*2평면은 12가지,..

[ㅅㄲㅁㅇ(as1392)]

eulerian이나 hamiltonian graph 찾아보셈

[익명(45.64)]

일반적으로 깔끔한 closed form이나 generating function은 안 알려져있음. 단순히 위와 오른쪽으로만 갈수 있는 경우에는 시작점부터 현재 지점까지 어떤 path로 왔건간에 미래에 영향을 안 미치는데, 이 경우에는 과거에 어떤 경로를 통해서 현재 지점까지 왔느냐가 영향을 미치기 때문에 이러한 dependency를 점화식에 반영하기도 굉장히 어렵고, 따라서 generating function을 설계하기도 어려움.

[익명(45.64)]

이러한 lattice 위에서의 self-avoiding walk에 관한 문제는 악명이 높은데, 내가 알기론 (0,0)에서 (m,n)까지 가는 이러한 self-avoiding walk의 구체적인 개수 뿐만 아니라 asymptotic formula도 안 알려져 있음. 심지어 lattice가 square인 경우조차 어떤 mu>0이 존재해서 (0,0)에서 (n,n)까지 가는 self-avoiding walk의 개수가 (1+o(1)) * mu^{n^2}라는 사실만 알려져있고, mu가 적당히 1.7 근방에 있는 어떤 상수라는것만 알지 mu에 대한 구체적인 값이나 closed form 또한 알려져있지 않음.

[익명(45.64)]

이렇게 self-avoiding walk 문제처럼 현재 지점까지 도달하는데 왔던 경로가 미래에도 영향을 미치는 요소 때문에 그래프 위에서 Hamiltonian path를 찾는 문제 (혹은 TSP) 들이 효율적인 알고리즘이 나오지 않는 이유이기도 하고, 대개 이런 류의 counting 문제들은 exact한 값을 얻기는 커녕 asymptotic formula를 구하는것도 미해결인 경우가 많고 꽤 괜찮은 연구거리가 되기도 함. 이러한 asymptotic formula를 구하는것 자체가 새로운 아이디어를 요구하거든.