Числа комбинаций в задаче о разорении игрока

[eugrita]

Изучение задачи о разорении игрока для игры с фиксированной ставкой и проигрышем (случайное блуждание) приводит к следующей подзадаче:
Есть числовая функция $m=m(k,n) $
где $k<n$ возвращающая натуральное m по следующему правилу:
$m$- это количество всевозможных последовательностей чисел $X_i=1,-1 $ где $i=1..n$ с фиксированным числом единиц, обладающих свойствами
$S_n=\sum_{i=1}^nX_i=k-1 $ (1)
$S_j=\sum_{i=1}^jX_i < k$, $\forall j<n$ (2)
Условие 1 автоматически определяет число единиц
$n_1=[\frac{n+k}{2}]$ если $n+k$ нечетно
$n_1=\frac{n+k}{2} - 1$ если $n+k$ четно
Пример $n=6,k=3,n_1=4$ всего комбинаций $ C_n^k=C_6^4=15$
-1 -1 1 1 1 1... 1 -1 -1 1 1 1... 1 1 -1 -1 1 1...1 1 1 -1 -1 1... 1 1 1 1 -1 1
-1 1 -1 1 1 1... 1 -1 1 -1 1 1... 1 1 -1 1 -1 1 ... 1 1 1 -1 1 -1
-1 1 1 -1 1 1... 1 -1 1 1 -1 1...1 1 -1 1 1 -1
-1 1 1 1 -1 1...1 -1 1 1 1 -1
-1 1 1 1 1 -1


Из них 6 не удовлетворяют условию $S_j<3$ получаем $m(3,6)=15-6=9$
Вопросы:
1)известна ли такая функция в комбинаторике или теории чисел и имеет название?
2) есть ли формула или правило для ее вычисления более простое чем программная генерация и перебор $ C_n^k$ комбинаций?

Cама эта задача по моему хороша для олимпиадного программирования школьников (МФТИ)

[Toucan]

eugrita в сообщении #611991 писал(а):

Из за сложности пришлось делать рис.

И тем не менее, если Вы хотите, чтобы Ваша задача обсуждалась на нашем форуме, наберите формулы как положено. Переехали в Карантин/

После того как исправите сообщение, сообщите об этом в теме Сообщение в карантине исправлено.

[Toucan]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[--mS--]

eugrita в сообщении #611991 писал(а):

-1 1 1 1 1 -1

Из них 6 не удовлетворяют условию $S_j<3$ получаем $m(3,6)=15-6=9$

Последняя выписанная цепочка (да и куча других выше) тоже не устраивает такому условию, поскольку в ней $S_5=3$.

[eugrita]

жирным шрифтом здесь как раз и выделены цепочки не удовлетворяющие условию и которые отсеиваются при счете m(k,n)
Вот результаты моих расчетов $m(k,n)$ при небольших $n$
$n=6,k=3,n_1=4,m(k,n)=9,C_n^{n_1}=15$
$n=7,k=3,n_1=4,m(k,n)=29,C_n^{n_1}=35$
$n=7,k=4,n_1=5,m(k,n)=20,C_n^{n_1}=21$
$n=8,k=5,n_1=6,m(k,n)=21,C_n^{n_1}=28$

В исходном тексте в конце неточность: вместо $C_n^{k}$ надо $C_n^{n_1}$

[sup]

У Вас здесь путаница.
Условие (1) (с равенством) возможно лишь в случае, когда четности $n$ и $k$ различны. А если одинаковы, то равенство невозможно. Кроме того, компьютерный подсчет у меня дал другие величины. И вообще, если не проврался, то в случае, когда четности $n$ и $k$ различны имеет место формула

$$m(k,n) = C_{n-1}^{\frac {n+1-k}{2}} - C_{n-1}^{\frac {n+1-k}{2}-2}$$

Например:

$$m(7,6) = C_{6}^{1} - C_{6}^{-1} = 6 - 0 = 6$$

$$m(7,4) = C_{6}^{2} - C_{6}^{0} = 15 - 1 = 14$$

$$m(7,2) = C_{6}^{3} - C_{6}^{1} = 20 - 6 = 14$$

$$m(6,3) = C_{5}^{2} - C_{5}^{0} = 10 - 1 = 9$$

Для одинаковых четностей должна быть аналогичная формула (если, конечно, исправить условие (1)).

[eugrita]

в моем примере какую последовательность ни возьми, сумма всех ее членов=2
$S_n=2=k-1=3-1$ значит условие(1) выполнено!!!
действительно если четности k и n одинаковы то равенство невозможно.
Но я и не говорил, что возможно хотя вынужден признать 3 строка таблицы - неверна - ее выкинуть

[sup]

eugrita в сообщении #611991 писал(а):

$S_n=\sum_{i=1}^nX_i=k-1 $ (1)

Вот Ваше условие. Если четности $n$ и $k$ одинаковы, то надо его как-то исправить, иначе задача некорректна и обсуждать, в таком случае, нечего.