Комбинаторное решение алгоритмической задачи

[Ironclad]

Добрый день. Задача из курса по алгоритмам, конкретно - из раздела Рекурсия. Но я попытался решить её комбинаторно и не преуспел. Собственно, задача:

Цитата:

На расстоянии $n$ шагов от магазина стоит человек. Каждую секунду он выбирает, куда сделать шаг: к магазину или в противоположном направлении. Напишите программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно $k$ шагов и оказавшись в магазине только после выполнения последнего шага.
На вход подаются через пробел два целых числа $n$ – расстояние до магазина в шагах и $k$ – требуемое количество шагов, которые должен сделать человек: $1 \leqslant n \leqslant k \leqslant 16$
На выход следует подать только одно число - количество способов попадания в магазин.

Человек стоит на расстоянии $n$ шагов, а сделать должен $k$ шагов. При $n = k$ шагов всё ясно, количество способов равно $1$. Рассмотрим остальные случаи: $n < k$.
Шаги можно делать по прямой в двух направлениях: к магазину (пусть это будет "вправо") и от магазина (соответственно, "влево"). Всего шагов должно быть $k$, из них $\frac{k - n}{2}$ шагов влево и, соответственно, $n + \frac{k - n}{2} = \frac{n+k}{2}$ шагов вправо.
Насколько я понимаю, необходимо каким-то образом распределить $\frac{k - n}{2}$ шагов влево среди $k$ шагов.
В данном случае размещаем подмножество однородных элементов (шагов влево), порядок которых не важен. Это, как я подумал, сочетания без повторений: $C^{\frac{k - n}{2}}_k$.
Но явно ошибся / чего-то не учёл, хотя не могу понять, чего. Задача не решается, хотя кажется несложной, к моему стыду.

[TOTAL]

Ironclad в сообщении #1602774 писал(а):

Но явно ошибся / чего-то не учёл, хотя не могу понять, чего.

Докажите, что ошиблись.

[Ironclad]

TOTAL в сообщении #1602786 писал(а):

Ironclad в сообщении #1602774 писал(а):

Но явно ошибся / чего-то не учёл, хотя не могу понять, чего.

Докажите, что ошиблись.

Не могу получить верные ответы. Например, при $n = 4$, $k = 8$ должно быть 14 способов попадания в магазин.
У меня же выходит 28:
$C^{\frac{k-n}{2}}_k = C^2_8 = \frac{8!}{6!2!} = 28$
Аналогично с другими значениями.

[TOTAL]

Ironclad в сообщении #1602875 писал(а):

Не могу получить верные ответы. Например, при $n = 4$, $k = 8$ должно быть 14 способов попадания в магазин.
У меня же выходит 28:
$C^{\frac{k-n}{2}}_k = C^2_8 = \frac{8!}{6!2!} = 28$
Аналогично с другими значениями.

Получили слишком много способов, т.к. в комбинаторных рассуждениях не учли требование из условия о том, что ....

[Ironclad]

TOTAL в сообщении #1602897 писал(а):

Получили слишком много способов, т.к. в комбинаторных рассуждениях не учли требование из условия о том, что ....

В этом-то и проблема: не могу понять, что не учёл, всё вроде бы довольно просто...
Всего есть $k$ шагов, среди которых надо распределить $\frac{k - n}{2}$. Либо оставшиеся $\frac{k + n}{2}$, что в случае с сочетаниями из $k$ - одно и то же.

[TOTAL]

Ironclad в сообщении #1602942 писал(а):

В этом-то и проблема: не могу понять, что не учёл, всё вроде бы довольно просто...

Нужен не любой маршрут с конечной точкой в магазине, а нужен маршрут без беготни мимо магазина с возвратами и повторными входами.

[Ironclad]

TOTAL в сообщении #1602945 писал(а):

Нужен не любой маршрут с конечной точкой в магазине, а нужен маршрут без беготни мимо магазина с возвратами и повторными входами.

Окей, теперь до меня дошло, что последний шаг не может быть назад. Значит, мы располагаем отрицательные шаги на $k - 1$ шагов. Осталось только понять, сколько должно быть шагов назад. На предпоследнем шаге все шаги назад тоже должны быть исчерпаны, иначе шагов не хватит. Значит, на $k - 1$ шагов приходится $\frac{k-n-2}{2}$ шагов назад? Но так тоже не выходит...
Пардон за непонятливость.

[TOTAL]

Ironclad в сообщении #1602954 писал(а):

Окей, теперь до меня дошло, что последний шаг не может быть назад.

Уже отсюда следует, что число вариантов уменьшилось до $C^{\frac{k-n}{2}}_{k-1}$. Т.е. на предпоследнем шаге он стоит перед магазином.

Но и здесь ещё остались лишние варианты, которые надо убрать. Ведь на предыдущем $(k-2)$-ом шаге он мог находиться в магазине. А на $(k-3)$-ом шаге мог находиться даже дальше магазина. И так далее. Все эти варианты надо отнять. Вплоть до варианта, в котором он мог забежать на самое большое расстояние после магазина.

[Ironclad]

TOTAL в сообщении #1602957 писал(а):

Но и здесь ещё остались лишние варианты, которые надо убрать. Ведь на предыдущем $(k-2)$-ом шаге он мог находиться в магазине. А на $(k-3)$-ом шаге мог находиться даже дальше магазина. И так далее. Все эти варианты надо отнять. Вплоть до варианта, в котором он мог забежать на самое большое расстояние после магазина.

(Оффтоп)

Спасибо Вам за терпение.

При поступательном движении к магазину (без поворотов назад) в точке 1 "запас хода" ещё $k - n + 1$ шагов. Из них может быть ${\frac{k-n}{2}}$ шагов влево и, соответственно, надо вычесть ещё $C^{\frac{k-n}{2}}_{k-n+1}$ вариантов...

[B@R5uk]

Наглядно можно себе представить ситуацию так. Если шаги к магазину обозначать белыми шариками, а от магазина — чёрными, и выкладывать их слева на право в порядке выполнения шагов, то в этой последовательности шариков, вне зависимости от того, где сделать её обрыв, число белых слева от обрыва минус число чёрных не должно превышать или равняться расстоянию до магазина из точки старта. То есть после выкладывания $n-1$ шарика на каждом шаге будет отбрасывание лишних по сравнению с "Це из эН по Ка" вариантов.

Так что формула будет непростой. Но интуиция подсказывает, что её можно записать в рекуррентном виде.

[Ironclad]

B@R5uk в сообщении #1603197 писал(а):

То есть после выкладывания $n-1$ шарика на каждом шаге будет отбрасывание лишних по сравнению с "Це из эН по Ка" вариантов.

Но не совсем понятно, как их отбрасывать, учитывая, что число оствшихся способов зависит от того, какой именно шарик выран. То есть в $C^k_n$ число $n$ на каждом шаге будет уменьшаться, а вот число $k$ уменьшится лишь в том случае, если был выбран чёрный шарик.

(Оффтоп)

Здесь $n$, $k$ могут вызвать путаницу, так как в задаче мы, наоборот, выбираем из $k$ шариков.

[B@R5uk]

Ну вот вы нашли число способов при $k=n$, теперь найдите при $k=n+1$, $k=n+2$ и так далее. Посмотрите что получится, может можно будет угадать общую формулу.

[TOTAL]

Рекуррентную формулу получить несложно. Обозначим $X_{n+2s}^n$ - искомое число способов впервые попасть в магазин, удалённый на $n$ шагов, за $k=n+2s$ шагов.

$$X_{n+2s}^n = C_{n+2s}^s - \sum_{i=1}^s{X_{n+2s-2i}^nC_{2i}^i}$$

Если впервые попали в магазин раньше, то потом бегали взад-вперёд всевозможными способами. Такие варианты отнимаются.

[Ironclad]

TOTAL, B@R5uk
Большое спасибо за помощь.