Из колоды 52 карт наугад вытягивают 6 карт...

[Yadryara]

mihaild в сообщении #1515361 писал(а):

У нас есть $52$ различных карты, мы хотим посчитать число неупорядоченных наборов из $6$ карт с нужной стоимостью, так?

Вроде бы так. Если опять-таки принять, что теперь уже стоимость = сумма очков всех 6-ти карт.

mihaild в сообщении #1515361 писал(а):

$B(n, m, k) = B(n - 1, m, k) + B(n - 1, m - 1, k - x_n)$, где $x_n$ - стоимость $n$-й карты.

Почему бы не снабдить эту формулу численным примером?

Попробую проверить:

$B(52, 10, 21) = B(51, 10, 21) + B(51, 9, 21 - x_{52})$ ??

Или так:

$B(52, 6, 21) = B(51, 6, 21) + B(51, 5, 21 - x_{52})$ ??

[kotenok gav]

Yadryara в сообщении #1515360 писал(а):

О какой формуле речь и как её применить к данной задаче?

О моей формуле $A(m, n)=A(m-1, n)+A(m, n-m)$, где, скажем, $A(3, 7)=1$, поскольку есть только один вариант $(2, 2, 3)$.

[Yadryara]

kotenok gav в сообщении #1515369 писал(а):

О моей формуле $A(m, n)=A(m-1, n)+A(m, n-m)$, где, скажем, $A(3, 7)=1$, поскольку есть только один вариант $(2, 2, 3)$.

О как! Так Вы посмотрите на название темы. Нам нужно использовать 6 карт. Ровно 6.

А Вы 3 карты используете?

[mihaild]

Yadryara в сообщении #1515368 писал(а):

$B(52, 10, 21) = B(51, 10, 21) + B(51, 9, 21 - x_{52})$ ?

Ну да.
Мы либо берем 52-ю карту (и таких способов это $B(51, 9, 21 - x_{52})$), либо не берем (и таких способов $B(51, 10, 21)$).

Естественно еще база нужна: $B(0, 0, 0) = 1$, $B(0, m, k) = 0$ при $m \neq 0$ или $k \neq 0$.

[kotenok gav]

Хорошо, вот модификация для случая ровно $k$ карт (я учитывал любое $k$): $A(m, n, k)=A(m-1, n, k)+A(m, n-m, k-1)$.

-- 23 апр 2021, 20:22 --

И это вроде бы то же, о чём говорит mihaild.

[Yadryara]

mihaild, $B(51, 10, 21)= 4624$ ?

kotenok gav в сообщении #1515372 писал(а):

Хорошо, вот модификация для случая ровно $k$ карт (я учитывал любое $k$): $A(m, n, k)=A(m-1, n, k)+A(m, n-m, k-1)$.

И это вроде бы то же, о чём говорит mihaild.

И никто из Вас двоих так и не привёл численного примера с 6 картами!

Нам ведь нужно не "вроде бы то же", а чтобы результат совпал.

[kotenok gav]

$A(m, 12, 6)=1$ для любого $m$, так как есть только один вариант $(2, 2, 2, 2, 2, 2)$.
$A(4, 20, 6)=3$, так как есть только варианты $(2, 2, 4, 4, 4, 4)$, $(2, 3, 3, 4, 4, 4)$, $(3, 3, 3, 3, 4, 4)$ (если я не ошибся).

[Yadryara]

kotenok gav в сообщении #1515376 писал(а):

$A(m, 12, 6)=1$ для любого $m$, так как есть только один вариант $(2, 2, 2, 2, 2, 2)$.

Нет, конечно! Ни одного варианта набрать сумму 12 нет. Минимальная сумма 14, как и писал ТС. У нас 4 масти и в колоде 4 двойки, а не 6, как в Вашем примере.

kotenok gav в сообщении #1515376 писал(а):

$A(4, 20, 6)=3$

А по моим подсчётам $A(4, 20, 6)=108$

[kotenok gav]

Yadryara в сообщении #1515377 писал(а):

У нас 4 масти и в колоде 4 двойки, а не 6, как в Вашем примере.

Этого моя формула не учитывает, да.

[mihaild]

Yadryara в сообщении #1515375 писал(а):

mihaild, $B(51, 10, 21)= 4624$ ?

Точно нет. Как вы это получили?

Yadryara в сообщении #1515375 писал(а):

И никто из Вас двоих так и не привёл численного примера с 6 картами!

А что вам привести? Дерево вычислений? Оно довольно большое, но можете проверить https://gist.github.com/01d7933413a7c43 ... e21878847d (или с вырезанными суммами вида $0 + 0$ https://gist.github.com/bafc661bebf1c42 ... 97d5942b37).

[Yadryara]

kotenok gav в сообщении #1515378 писал(а):

Этого моя формула не учитывает, да.

Ну то есть Вы сами признаете, что для данной задачи она не подходит. По крайней мере, в таком виде.

Вот видите, стоило от размахивания формулами перейти к конкретным примерам и это сразу стало ясно.

$20(224444) \to \binom{4}{2}\binom{4}{4}=6\cdot1=6$

$20(233444) \to \binom{4}{1}\binom{4}{2}\binom{4}{3}=4\cdot6\cdot4=96$

$20(333344) \to \binom{4}{4}\binom{4}{2}=1\cdot6=6$

$6 + 96 +6 = 108$

$A(4, 20, 6, 4)=108$

Возражения ?

-- 23.04.2021, 14:50 --

mihaild в сообщении #1515381 писал(а):

Yadryara в сообщении #1515375 писал(а):

mihaild, $B(51, 10, 21)= 4624$ ?

Точно нет. Как вы это получили?

Довольно долго рассказывать, но попозже расскажу. Раньше меня его получил ТС, а позже svv, так что число это, скорее всего, верное. См. тему внимательно.

$B(52, 10, 21) = A(10, 21, 6, 4)= 4624$

Или $B(52, 10, 21) \neq A(10, 21, 6, 4)$ ?

Запись $A(10, 21, 6, 4)=4624$ означает, что существует $4624$ способа набрать $21$ очко, используя ровно $6$ карт 4-х мастей от 2-ки до 10-ки включительно.

[mihaild]

Yadryara в сообщении #1515382 писал(а):

Или $B(52, 10, 21) \neq A(10, 21, 6, 4)$ ?

Нет. $B(52, 10, 21)$ - это число способов набрать $21$ очко, используя $10$ карт от двойки до туза. Таких способов, естественно, $0$, т.к. $10$ карт дают минимум $28$ очков.

Если уж совсем формально подходить, то надо писать $B(52, 10, 21, [2, 2, 2, 2, 3, 3, 3, 3, \ldots, 14, 14, 14, 14])$ - указывать колоду и порядок карт.

[Yadryara]

mihaild, всё нормально. Смотрите цитату, я тот пост поправлял:

Yadryara в сообщении #1515368 писал(а):

$B(52, 10, 21) = B(51, 10, 21) + B(51, 9, 21 - x_{52})$ ??

Или так:

$B(52, 6, 21) = B(51, 6, 21) + B(51, 5, 21 - x_{52})$ ??

Получается, что как раз второе моё прочтение верно, а не первое, как Вы сказали.

Таким образом, у Вас получилось то же самое число.

$B(52, 6, 21) = A(10, 21, 6, 4)= 4624$

Оно там у Вас в самой первой строчке по первой ссылке. Правда, у Вас там вторая строка налезла на первую.

Так что Ваша формула, видимо, работает.

[Yadryara]

mihaild в сообщении #1515381 писал(а):

Как вы это получили?

Рассказываю, как и было обещано. Всё-таки 25 строк вычислений, а не 14242, как по Вашей 1-й ссылке. $10_{10}=A_{16}$.

$21(22223A) \to \binom{4}{4}\binom{4}{1}\binom{4}{1}=1\cdot4\cdot4=16$

$21(222249) \to \binom{4}{4}\binom{4}{1}\binom{4}{1}=1\cdot4\cdot4=16$

$21(222258) \to \binom{4}{4}\binom{4}{1}\binom{4}{1}=1\cdot4\cdot4=16$

$21(222267) \to \binom{4}{4}\binom{4}{1}\binom{4}{1}=1\cdot4\cdot4=16$

$21(222339) \to \binom{4}{3}\binom{4}{2}\binom{4}{1}=4\cdot6\cdot4=96$

$21(222348) \to \binom{4}{3}\binom{4}{1}\binom{4}{1}\binom{4}{1}=4\cdot4\cdot4\cdot4=256$

$21(222357) \to \binom{4}{3}\binom{4}{1}\binom{4}{1}\binom{4}{1}=4\cdot4\cdot4\cdot4=256$

$21(222366) \to \binom{4}{3}\binom{4}{1}\binom{4}{2}=4\cdot4\cdot6=96$

$21(222447) \to \binom{4}{3}\binom{4}{2}\binom{4}{1}=4\cdot6\cdot4=96$

$21(222456) \to \binom{4}{3}\binom{4}{1}\binom{4}{1}\binom{4}{1}=4\cdot4\cdot4\cdot4=256$

$21(222555) \to \binom{4}{3}\binom{4}{3}=4\cdot4=16$

$21(223338) \to \binom{4}{2}\binom{4}{3}\binom{4}{1}=6\cdot4\cdot4=96$

$21(223347) \to \binom{4}{2}\binom{4}{2}\binom{4}{1}\binom{4}{1}=6\cdot6\cdot4\cdot4=576$

$21(223356) \to \binom{4}{2}\binom{4}{2}\binom{4}{1}\binom{4}{1}=6\cdot6\cdot4\cdot4=576$

$21(223446) \to \binom{4}{2}\binom{4}{1}\binom{4}{2}\binom{4}{1}=6\cdot4\cdot6\cdot4=576$

$21(223455) \to \binom{4}{2}\binom{4}{1}\binom{4}{1}\binom{4}{2}=6\cdot4\cdot4\cdot6=576$

$21(224445) \to \binom{4}{2}\binom{4}{3}\binom{4}{1}=6\cdot4\cdot4=96$

$21(233337) \to \binom{4}{1}\binom{4}{4}\binom{4}{1}=4\cdot1\cdot4=16$

$21(233346) \to \binom{4}{1}\binom{4}{3}\binom{4}{1}\binom{4}{1}=4\cdot4\cdot4\cdot4=256$

$21(233355) \to \binom{4}{1}\binom{4}{3}\binom{4}{2}=4\cdot4\cdot6=96$

$21(233445) \to \binom{4}{1}\binom{4}{2}\binom{4}{2}\binom{4}{1}=4\cdot6\cdot6\cdot4=576$

$21(234444) \to \binom{4}{1}\binom{4}{1}\binom{4}{4}=4\cdot4\cdot1=16$

$21(333345) \to \binom{4}{4}\binom{4}{1}\binom{4}{1}=1\cdot4\cdot4=16$

$21(333444) \to \binom{4}{3}\binom{4}{3}=4\cdot4=16$


$16\cdot9 + 96\cdot6 + 256\cdot4 + 576\cdot5 = 4624$


$A(10, 21, 6, 4)=4624$

[mihaild]

Yadryara в сообщении #1515405 писал(а):

Рассказываю

Вопрос был конкретно про

Yadryara в сообщении #1515375 писал(а):

$B(51, 10, 21)= 4624$

, а не стартовую задачу.

Yadryara в сообщении #1515405 писал(а):

Всё-таки 25 строк вычислений, а не 14242

Зато думать надо - разбиения прикидывать.
И кстати на больших колодах перебор разбиений будет медленнее, т.к. их экспоненциально много.