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

[melnikoff]

arseniiv в сообщении #1514074 писал(а):

Ещё мы можем применить динамическое программирование, считая число способов получить $n$ очков картами с ценностями от 2 до $m$, назовём это $A(m, n)$, используя очевидные рекуррентные соотношения.

Что-то я не могу увидеть эти очевидные соотношения...

[kotenok gav]

$A(m, n)=A(m-1, n)+A(m, n-m)$.

[melnikoff]

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

$A(m, n)=A(m-1, n)+A(m, n-m)$.

Сомневаюсь, что это верно.
У вас первое слагаемое – это кол-во всех сочетаний, дающих по $n$ очков, когда самая весомая карта не больше $m-1$.
Тогда второе слагаемое должно быть кол-вом всех сочетаний, дающих по $n$ очков, когда самая весомая карта равна $m$. Но у вас второе слагаемое выражает что-то непонятное.

[arseniiv]

melnikoff в сообщении #1515313 писал(а):

Что-то я не могу увидеть эти очевидные соотношения...

Да, я забыл, что надо ещё добавить параметр $c$ — количество карт в наборе. Общая формула, не включающая граничные случаи, будет

$$A(m, n, c) = \sum_{k = 0}^c C^k_c A(m - 1, n - k m, c - k).$$

Или я имел в виду что-то другое, но уже не помню что.

UPD: Ай, там не учтены условия того, что карт каждого вида не бесконечно много, а то вообще производящие функции бы стоило взять.

UPD 2: Хотя что я волнуюсь, просто возьмём сумму по $k \in 0..4$ вместо $k \in 0..c$!

[Yadryara]

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

$A(m, n)=A(m-1, n)+A(m, n-m)$.

Ну то есть, например, $A(7, 21)=A(6, 21)+A(7, 14)$ ?

Но $3168 + 6 \neq 4128$

[Geen]

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

Ну то есть, например

А если наоборот?

[Yadryara]

Geen, не понял вопроса.

На всякий случай:

$A( 2, 14) = 0$
$A( 3, 14) = 6$
$A( 4, 14) = 6$

$A( 2, 15) = 0$
$A( 3, 15) = 16$
$A( 4, 15) = 32$
$A( 5, 15) = 32$

$A( 2, 16) = 0$
$A( 3, 16) = 6$
$A( 4, 16) = 108$
$A( 5, 16) = 124$
$A( 6, 16) = 124$

$A( 2, 17) = 0$
$A( 3, 17) = 0$
$A( 4, 17) = 192$
$A( 5, 17) = 304$
$A( 6, 17) = 320$
$A( 7, 17) = 320$

$A( 2, 18) = 0$
$A( 3, 18) = 0$
$A( 4, 18) = 248$
$A( 5, 18) = 606$
$A( 6, 18) = 718$
$A( 7, 18) = 734$
$A( 8, 18) = 734$

$A( 2, 19) = 0$
$A( 3, 19) = 0$
$A( 4, 19) = 192$
$A( 5, 19) = 976$
$A( 6, 19) = 1344$
$A( 7, 19) = 1456$
$A( 8, 19) = 1472$
$A( 9, 19) = 1472$

$A( 2, 20) = 0$
$A( 3, 20) = 0$
$A( 4, 20) = 108$
$A( 5, 20) = 1252$
$A( 6, 20) = 2202$
$A( 7, 20) = 2570$
$A( 8, 20) = 2682$
$A( 9, 20) = 2698$
$A(10, 20) = 2698$

$A( 2, 21) = 0$
$A( 3, 21) = 0$
$A( 4, 21) = 32$
$A( 5, 21) = 1408$
$A( 6, 21) = 3168$
$A( 7, 21) = 4128$
$A( 8, 21) = 4496$
$A( 9, 21) = 4608$
$A(10, 21) = 4624$
$A(11, 21) = 4624$

-- 23.04.2021, 03:12 --

arseniiv в сообщении #1515325 писал(а):

Общая формула, не включающая граничные случаи, будет

$$A(m, n, c) = \sum_{k = 0}^c C^k_c A(m - 1, n - k m, c - k).$$

UPD: Ай, там не учтены условия того, что карт каждого вида не бесконечно много, а то вообще производящие функции бы стоило взять.

UPD 2: Хотя что я волнуюсь, просто возьмём сумму по $k \in 0..4$ вместо $k \in 0..c$!

Покажите, пожалуйста, как эта формула работает на численном примере.

Например, для $A(7, 21, 4)$ целых $4$ слагаемых из $5$ равны $0$.

$3168 + 0 + 0 + 0 + 0 \neq 4128$

А где-нибудь учтено, что карт ровно $6$ ?

[Yadryara]

arseniiv в сообщении #1515325 писал(а):

Общая формула, не включающая граничные случаи, будет

$$A(m, n, c) = \sum_{k = 0}^c C^k_c A(m - 1, n - k m, c - k).$$

UPD: Ай, там не учтены условия того, что карт каждого вида не бесконечно много, а то вообще производящие функции бы стоило взять.

UPD 2: Хотя что я волнуюсь, просто возьмём сумму по $k \in 0..4$ вместо $k \in 0..c$!

Покажите, пожалуйста, как эта формула работает на численном примере.

Например, для $A(7, 21, 4)$ целых $4$ слагаемых из $5$ равны $0$.

$3168 + 0 + 0 + 0 + 0 \neq 4128$

А где-нибудь в Вашей формуле учтено, что карт ровно $6$ ?

[kotenok gav]

melnikoff в сообщении #1515319 писал(а):

Тогда второе слагаемое должно быть кол-вом всех сочетаний, дающих по $n$ очков, когда самая весомая карта равна $m$. Но у вас второе слагаемое выражает что-то непонятное.

Это и выражает: сумма ценностей остальных карт должна быть равна $n-m$. Я здесь не учитывал перестановки ценностей карт, но их легко учесть.

[Yadryara]

kotenok gav, ну ежели легко учесть, то где же рабочая формула?? Можно в личку.

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

melnikoff в сообщении #1515319 писал(а):

Тогда второе слагаемое должно быть кол-вом всех сочетаний, дающих по $n$ очков, когда самая весомая карта равна $m$. Но у вас второе слагаемое выражает что-то непонятное.

Это и выражает: сумма ценностей остальных карт должна быть равна $n-m$. Я здесь не учитывал перестановки ценностей карт, но их легко учесть.

У Вас написано $A(m, n-m)$, а это не то, что имел в виду уважаемый melnikoff. Болд и крупный шрифт мои.

То есть это другое число, которое можно обозначить, например, $T(m,n)$.

$A(m,n)=A(m-1,n) + T(m,n)$

Некоторые значения $T(m,n)$:


$T( 3, 14) = 6$
$T( 4, 14) = 0$

$T( 3, 15) = 16$
$T( 4, 15) = 16$
$T( 5, 15) = 0$

$T( 3, 16) = 6$
$T( 4, 16) = 102$
$T( 5, 16) = 16$
$T( 6, 16) = 0$

$T( 4, 17) = 192$
$T( 5, 17) = 112$
$T( 6, 17) = 16$
$T( 7, 17) = 0$

$T( 4, 18) = 248$
$T( 5, 18) = 358$
$T( 6, 18) = 112$
$T( 7, 18) = 16$
$T( 8, 18) = 0$

$T( 4, 19) = 192$
$T( 5, 19) = 784$
$T( 6, 19) = 368$
$T( 7, 19) = 112$
$T( 8, 19) = 16$
$T( 9, 19) = 0$

$T( 4, 20) = 108$
$T( 5, 20) = 1144$
$T( 6, 20) = 950$
$T( 7, 20) = 368$
$T( 8, 20) = 112$
$T( 9, 20) = 16$
$T(10, 20) = 0$

$T( 4, 21) = 32$
$T( 5, 21) = 1376$
$T( 6, 21) = 1760$
$T( 7, 21) = 960$
$T( 8, 21) = 368$
$T( 9, 21) = 112$
$T(10, 21) = 16$
$T(11, 21) = 0$

[kotenok gav]

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

У Вас написано $A(m, n-m)$, а это не то, что имел в виду уважаемый melnikoff.

Ценность самой весомой карты равна $m$. Значит, ценности остальных карт не больше $m$ (а, или ценности не могут повторяться?) и их суммарная ценность $n-m$.

[Yadryara]

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

Ценность самой весомой карты равна $m$.

Тут неплохо бы договориться о терминологии. У каждой карты есть достоинство и масть. У Вас ценность = достоинство?

Где же Ваша формула, всё-таки?

[kotenok gav]

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

У каждой карты есть достоинство и масть. У Вас достоинство=ценность?

Да.

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

Где же Ваша формула всё-таки?

Снимаю своё заявление, что перестановки легко учесть (именно из-за повторений). Но формула, не учитывающая перестановки, всё равно должна быть верной.

[Yadryara]

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

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

Что это значит?

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

Как, например, получить, что $A(10,21)=4624$ или, что $A(11,22)=7522$ ?

[mihaild]

Ничего не понял в обсуждении выше, кажется либо я идиот, либо что-то излишне запутанное.
У нас есть $52$ различных карты, мы хотим посчитать число неупорядоченных наборов из $6$ карт с нужной стоимостью, так?
Очевидная рекуррентная формула тут выписывается на "число способов, которым из первых $n$ карт можно выбрать $m$ карт с суммой $k$ очков": $B(n, m, k) = B(n - 1, m, k) + B(n - 1, m - 1, k - x_n)$, где $x_n$ - стоимость $n$-й карты. Что может быть оптимизируется для случая, если карт каждого достоинства много, но тут не нужно.