Guest
Новичок
|
    
Поалуйста, помогите решить задачу по комбинаторике:
Город имеет вид прямоугольника, разделенного улицами на квадраты. Таких квадратов в направлении с Севера На Юг n , а в направлении с Востока на Запад k. Сколько имеется кратчайших дорог от одной из вершин прямоугольника до противоположной?
Заранее благодарен
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 29 марта 2005 19:06 | IP
|
|
dm
Удален
|
C_(k+n)^k.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 29 марта 2005 19:12 | IP
|
|
Guest
Новичок
|
Не могли бы вы немного решение привести...А то я что-то не сображу...
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 29 марта 2005 20:21 | IP
|
|
dm
Удален
|
Любой такой путь можно зашифровать последовательностью из нулей и единиц длины k+n, в которой будет k единиц и n нулей.
Например, пусть единица означает, что мы сейчас идем по горизонтальному отрезку, а ноль - что по вертикальному. Количество таких кратчайших путей равно количеству таких последовательностей.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 30 марта 2005 0:55 | IP
|
|
|
Форум
СРОЧНО ПОМОГИТЕ(КОМБИНАТОРИКА)
