Страница 1 из 1

Нахождение путей

Добавлено: 26 апр 2015, 16:04
Samorezishe
Здравствуйте, помогите решить: Вычислите количество путей из точки сетки с координатами (2, 3) в точку сетки с координатами (15, 15). Путь всегда идёт вверх и вправо.

Нахождение путей

Добавлено: 26 апр 2015, 16:55
ARRY
Очевидно, что каждый путь содержит ровно $$25$$ отрезков, причем $$13$$ из них расположены параллельно оси $$x$$, а $$12$$ – параллельно оси $$y$$. Сопоставим каждому пути последовательность букв $$x$$ и $$y$$ таким образом, что при  прохождении горизонтального отрезка пути включаем в последовательность букву $$x$$, а при прохождении вертикального – букву $$y$$. Каждая последовательность содержит $$25$$ букв – $$13$$ букв $$x$$ и $$12$$ букв $$y$$. Теперь надо вычислить количество таких последовательностей. Последовательность однозначно задается набором из $$12$$ мест, на которых в ней стоят буквы $$x$$. Либо набором из $$13$$ мест, на которых стоят буквы $$y$$. Двенадцать мест из $$25$$ можно выбрать $$C^{12}_{25}$$ cпособами. Поэтому число возможных последовательностей, а значит, и число возможных путей, равно $$C^{12}_{25}=5200300$$.

Нахождение путей

Добавлено: 27 апр 2015, 03:25
Anik
Чего-то здесь не то. Слишком большое количество путей.

Нахождение путей

Добавлено: 27 апр 2015, 03:38
ARRY
Anik писал(а):Source of the post Чего-то здесь не то. Слишком большое количество путей.
Anik, а сколько их должно быть по-Вашему?

Нахождение путей

Добавлено: 27 апр 2015, 03:49
Anik
Я ещё не считал, но подозреваю, что меньше, чем у вас.
Придётся мне подсчитать. Потом напишу что получилось.

Нахождение путей

Добавлено: 27 апр 2015, 05:59
Anik
Вы правы! Извините что вмешался. Комбинаторику я подзабыл.
Меня смутили два момента. Первый, что $$C^{12}_{25}=C^{13}_{25}$$ , я думал что это не так. И второе:
Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми.
Я под элементами понимал и y. А вообще, все 25 элементов подразумеваются различными, Поэтому в комбинации. например: xxx подразумеваются различные элементы, обозначенные одной буквой x, тогда порядок следования трёх элементов действительно не важен. Нам остаётся узнать, каким образом двенадцать "различных элементов x, порядок следования которых не важен", можно разместить в 25 местах. Может быть я кого-то этим запутал, но я понял так.

Нахождение путей

Добавлено: 27 апр 2015, 06:07
Anik
Куда-то делась кнопка редактирования.
Я там ошибся, не " двенадцать "различных элементов х..." (далее по тексту), а тринадцать!