А я, в своюю очередь понял, как задачу можно решить, используя стандартный курс теорвера.
Привожу два решения.
С задачей разобрались.
Привожу два решения:
1 - стандартное.
m черных, n белых.
по Ох откладываем m
по Оу n
из (О,О) дойти в (m,n) и есть вытащить все шарики
двигаемся на клетку вправо (0) = вытаскиваем черный, вверх (1) = белый
длина последовательности из 0 и 1 - m+n, каждая последовательность описывает процесс вытаскивания шариков
всего таких последовательностей N=C(m+n, n)
нас устраивают все варианты, проходящие через точки, где абсцисса=ординате. т.е. все точки R(r,r).
их K=C(2r, r)*C(m+n-2r, m-r)
а r может изменяться от 1 до m
P= сумма по r=1 to m (K/N) = (C(2r,r)*C(m+n-2r,m-r))/C(m+n,n)
2 - мое решение, которое сразу пришло мне в голову..
Вынимаем первый шар:
он либо черный с вероятностью M/(M+N), либо белый - с вероятностью N/(M+N)
Если случай 1 - это хорошо: черных меньше и обязательно наступит момент, когда число вынутых белых и черных шаров сравняется.
Если случай 2: здесь все не так просто.
Здесь одна страничка, про то, что такое числа Каталана. Главное - понять принцип, как оно считается через геометрическую интерпретацию, потому что, что здесь я буду использовать такой же принцип подсчета, поэтому текст ниже читать только после просмотра скриншотов, иначе не будут понятны обозначения и принцип.
Итак, ситуация такая:
мы находимся в точке (1,1) и нам нужно прийти к точке (N+M, N-M).
Число возможных способов так сделать: C (N+M-1, N-1) - число шагов - (N+M-1) и за них мы вытащим ровно (N-1) белый шар.
Из этого числа нам нужно вычесть все случаи, когда ломаная попадет на прямую y=0 (белых и черных шаров будет поровну).
Используя тот же фокус с отражением ломаной относительно прямой (y=0) - здесь все такие нехорошие прямые будут попадать в точку (N+M, M-N). Число способов туда добраться - C (N+M-1, N).
Число хороших случаев: C (N+M-1, N-1) - C (N+M-1, N) = (N-M)/N * C(N+M-1,M)>
Самое сложное позади.
Теперь собираем это все в одно целое:
1 - (N/(N+M))*[(N-M)/N * C(N+M-1,N-1)]/C (N+M-1, N-1) = 1 - (N-M)/(N+M) = 2M/(N+M)
Посмотри на мое решение. Фокус с отражением ломаной для стандартного решения не подойдет, как мне кажется.