|
Тема |
Комбинаторика броене на пътища |
|
Автор |
Dijkstra (сектант) |
|
Публикувано | 17.04.14 19:40 |
|
|
Таблица с размер 1х(m+n). На първите n места имаме монети. Местим всички монети на последните n места с n*m премествания като можем да местим само надясно и само ако дясното квадратче е празно. S(n,m) е броя на всички различни начини да завършим преместването. Трябва да се докаже че
S(n,m) = [ (n-1)$ * (m-1)$ *(m*n)!] / [(n+m-1)$]
Където x$ = 1!*2!*3!*****x! произведение на факториали.
....
Принципно идеята ми за решение беше индукция с база S(1,m) и S(n,1) за произволни n и m, и в индукционната стъпка да докажа някак си за S(n,m+1) и S(n+1,m) но нещо не успявам.
Предложения?
Редактирано от Dijkstra на 17.04.14 19:41.
|
| |
|
|
|