4 0 0
3 0 1
3 1 0
2 0 2
2 1 1
2 2 0
1 0 3
1 1 2
1 2 1
1 3 0
0 0 4
0 1 3
0 2 2
0 3 1
0 4 0

Énumérer le nombre de colonnes entières

Comme il faut du temps pour calculer $ _n C _r $ en fonction de la manière dont la valeur est prise, il existe des cas où l'accélération peut être obtenue en énumérant le nombre de chaînes d'entiers. Ici, l'équation graduelle suivante est utilisée. $ P (n, m) $ est le nombre de colonnes entières de longueur $ n $ et somme $ m $.

P(n,m)= 
\begin{cases}
1 & (n,m=0)\\

P(n-1,m) & (m=0, 1 \leq n) \\
P(n-1,m)+P(n,m-1) & (1 \leq m, 1 \leq n) \\
0 & (otherwise) 
\end{cases}

Le nombre de colonnes entières dont la somme est exactement $ j $ jusqu'au $ i $ ème élément est le nombre de colonnes entières dont la somme est exactement $ j $ à l'élément $ i-1 $ ème (c'est-à-dire que l'élément $ i $ ème est (Quand $ 0 $) et le nombre de colonnes entières dont la somme est exactement $ j-1 $ jusqu'au $ i $ ème élément. Il peut être mis en œuvre comme suit.

P = []
cur = [0]*(m+1)
cur[0] = 1
for i in range(1, n+1):
    for j in range(1, m+1):
        cur[j] += cur[j-1]
    P.append(cur.copy())

Compréhension intuitive des formules graduelles

Énumération d'une chaîne entière de $ P (2,4) $

4 0 0
#Jusqu'ici c'est P(1,4)

0 4 0
3 1 0
2 2 0
1 3 0
#Jusqu'ici c'est P(2,4)

Maintenant, si vous soustrayez $ 1 $ de tous les seconds éléments d'une chaîne entière dont la longueur peut être représentée par exactement $ 2 $

0 3
3 0
2 1
1 2

Et nous obtenons une chaîne entière de $ P (2,3) $. Inversement, si vous ajoutez $ 1 $ à tous les deuxièmes éléments de $ P (2,3) $, le deuxième élément sera de 0 $ ou plus, donc la somme qui peut être représentée par exactement 2 $ de longueur est de 4 $ $. Vous obtenez une chaîne entière.

Lister le nombre de combinaisons

Recherchez le nombre de combinaisons uniques des chaînes d'entiers répertoriées précédemment, en excluant les mêmes combinaisons dans des ordres différents. $ C (n, m) $ est une combinaison de $ n $ entiers qui donne un total de $ m $, et est calculé par l'équation graduelle suivante.

C(n,m)= 
\begin{cases}
1 & (n,m=0)\\

C(n-1,m) & (m < n, 1 \leq n) \\
C(n-1,m)+C(n,m-n) & (n \leq m, 1 \leq n) \\
0 & (otherwise) 
\end{cases}

Le nombre de colonnes entières jusqu'au $ i $ ème élément dont la somme est exactement $ j $ est le nombre de colonnes entières dont la somme est exactement $ j $ à l'élément $ i-1 $ ème (c'est-à-dire que l'élément $ i $ ème est (Quand $ 0 $) et le nombre de colonnes entières dont la somme est exactement $ ji $ jusqu'au $ i $ ème élément. Il peut être mis en œuvre comme suit.

C = []
cur = [0]*(m+1)
cur[0] = 1
for i in range(1, n+1):
    for j in range(i, m+1):
        cur[j] += cur[j-i]
    C.append(cur.copy())

Compréhension intuitive des formules graduelles

Si vous énumérez $ C (3,4) $,

4 0 0
#Jusqu'ici c'est C(1,4)

2 2 0
3 1 0
#Jusqu'ici c'est C(2,4)

2 1 1
#Jusqu'ici c'est C(3,4)

Sera. Au fait, si vous utilisez * pour représenter une combinaison d'entiers dont la longueur est exactement de 2 $ et dont la somme est de 4 $.

2 * *
2 * *
0

3 * * *
1 *
0

Si vous transposez ceci et lisez-le

2 2
* *
* *

2 1 1
* * *
*

Par conséquent, une combinaison d'entiers d'une longueur d'exactement $ 2 $ et d'une somme de 4 $ $ peut être lue comme une combinaison d'entiers de n'importe quelle longueur avec une valeur maximale de 2 $ $ et une somme de 4 $ $. Ici, on peut voir que la combinaison d'entiers après translocation commence toujours par $ 2 $, et par la suite elle peut être représentée par la combinaison d'entiers de $ C (2,4-2) = C (2,2) $.

référence

Mathematics Girl ★ Jouez avec la formule graduelle du numéro de partition --incognita et cognita