Problème sur les partitions d'entiers

Finalement ça ne m'a pas pris beaucoup de temps.

En Python 3, code pour fabriquer le dictionnaire D (et compter le nombre de partitions non vides) :

def Dicpart(m,n) :
    D={}
    Last=[[0,m,m]]
    fin=0
    for i in range(n) :
        NewLast=[]
        for record in Last :
            num=record[0] ; manque=record[1] ; der=record[2]
            l=min(manque,der)
            if l>0 : D[num]=fin+1
            NewLast+=[[fin+i+1,manque-i-1,i+1] for i in range(l)]
            fin=fin+l
        Last=NewLast
    return D,fin

On applique sur un cas déjà vu :

Dicpart(4,3)

({0: 1, 1: 5, 2: 6, 3: 8, 5: 9, 6: 10}, 10)

Maintenant on peut définir le N :

m=10 ; n=7 
D,nb=Dicpart(m,n)

def Num(k) : 
    if k==[] : return 0
    else : return D[Num(k[:-1])]+k[-1]-1
    # C'est la formule (4.1)

Voyons voir :

print("nb de partitions non vides",nb)
k=[3,2,2,1,1]
print("Numéro de",k,":",Num(k))

nb de partitions non vides : 131
Numéro de [3, 2, 2, 1, 1] : 102

Vérifions que le dernier est bien celui qu'on pense

k=[4,1,1,1,1,1,1]
print("Numéro de",k,":",Num(k))

Numéro de [4, 1, 1, 1, 1, 1, 1] : 131

Tu as dû mal lire. C'est bien exactement ce que j'ai, y compris l'entrée 0:1 qui dit que le premier fils de la partition vide [] (n° 0) est [1] (n°1).
Ma procédure Dicpart retourne un couple formé du dictionnaire lui-même et du nombre de partitions non vides.
Par contre, je ne comprends pas ce qu'est le [1] que tu as au début.