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

Samorezishe · Сообщение **Samorezishe** » 26 апр 2015, 16:04

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

ARRY · Сообщение **ARRY** » 26 апр 2015, 16:55

Очевидно, что каждый путь содержит ровно $$25$$

отрезков, причем $$13$$

из них расположены параллельно оси $$x$$

, а

– параллельно оси $$y$$

. Сопоставим каждому пути последовательность букв $$x$$

и

таким образом, что при прохождении горизонтального отрезка пути включаем в последовательность букву $$x$$

, а при прохождении вертикального – букву $$y$$

. Каждая последовательность содержит $$25$$

букв –

букв

и

букв

. Теперь надо вычислить количество таких последовательностей. Последовательность однозначно задается набором из $$12$$

мест, на которых в ней стоят буквы $$x$$

. Либо набором из $$13$$

мест, на которых стоят буквы $$y$$

. Двенадцать мест из $$25$$

можно выбрать $C^{12}_{25}$ cпособами. Поэтому число возможных последовательностей, а значит, и число возможных путей, равно $C^{12}_{25}=5200300$ .

Anik · Сообщение **Anik** » 27 апр 2015, 03:25

Чего-то здесь не то. Слишком большое количество путей.

ARRY · Сообщение **ARRY** » 27 апр 2015, 03:38

Anik писал(а):Source of the post Чего-то здесь не то. Слишком большое количество путей.

Anik, а сколько их должно быть по-Вашему?

Anik · Сообщение **Anik** » 27 апр 2015, 03:49

Я ещё не считал, но подозреваю, что меньше, чем у вас.
Придётся мне подсчитать. Потом напишу что получилось.

Anik · Сообщение **Anik** » 27 апр 2015, 05:59

Вы правы! Извините что вмешался. Комбинаторику я подзабыл.
Меня смутили два момента. Первый, что $C^{12}_{25}=C^{13}_{25}$ , я думал что это не так. И второе:

Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми.

Я под элементами понимал x и y. А вообще, все 25 элементов подразумеваются различными, Поэтому в комбинации. например: xxx подразумеваются различные элементы, обозначенные одной буквой x, тогда порядок следования трёх элементов действительно не важен. Нам остаётся узнать, каким образом двенадцать "различных элементов x, порядок следования которых не важен", можно разместить в 25 местах. Может быть я кого-то этим запутал, но я понял так.

Anik · Сообщение **Anik** » 27 апр 2015, 06:07

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

yourdomain.com