Nombre de partitions d'un entier⚓︎
On dira qu'une somme doit comporter au moins un terme, et que l'ordre ne compte pas, ainsi
- Il y a \(3\) façons d'écrire \(3\) comme une somme.
- \(3 = 1 + 2\)
- \(3 = 1 + 1 + 1\)
- \(3 = 3\)
- Il y a \(7\) façons d'écrire \(5\) comme une somme.
- \(5 = 5\)
- \(5 = 4 + 1\)
- \(5 = 3 + 2\)
- \(5 = 3 + 1 + 1\)
- \(5 = 2 + 2 + 1\)
- \(5 = 2 + 1 + 1 + 1\)
- \(5 = 1 + 1 + 1 + 1 + 1\)
Écrire une fonction nb_sommes
qui prend un paramètre entier 0 < n <= 42
et qui renvoie le nombre de façons d'écrire n
comme une somme, sans compter l'ordre.
Exemples
>>> nb_sommes(3)
3
>>> nb_sommes(5)
7
Indice 1
- Toujours commencer par dénombrer à la main les premiers cas.
- Bien ranger les cas ; faire des figures.
- Ajouter dès que possible des tests, avant d'écrire la fonction.
Indice 2
Il est recommandé de construire une fonction auxiliaire telle que nb_k_sommes(n, k)
renvoie le nombre de façons d'écrire n
comme une somme de k
termes.
Ainsi, nb_sommes(n)
sera la somme pour k
allant de 1
à n
de nb_k_sommes(n, k)
.
On remarquera que
k > n
ne donne aucune sommek == 1
donne une unique somme
On ajoutera des tests à cette fonction !
Indice 3
Pour dénombrer nb_k_sommes(n, k)
, on fera deux cas :
- Les sommes dont le plus petit terme est
1
. Combien de termes restants, et pour quelle somme ? Un calcul récursif est alors possible. - Les sommes dont tous les termes sont supérieurs à
1
. On pourra enlever1
à chaque terme, ce qui donne une somme égale à ??? en ??? parties. Et réciproquement. Ce qui permet de dénombrer ce cas de manière récursive également.
Indice 4
Il faudra utiliser de la mémoïsation pour que le code soit assez rapide.
def nbpy-undsommes(n):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undsommes(3) == 3bksl-nlassert nbpy-undsommes(5) == 7bksl-nlbksl-nlmemo = dict()bksl-nlbksl-nlbksl-nldef nbpy-undkpy-undsommes(n, k):bksl-nl if (n, k) not in memo:bksl-nl if n < k:bksl-nl y = 0bksl-nl elif k == 1:bksl-nl y = 1bksl-nl else:bksl-nl y = nbpy-undkpy-undsommes(n - 1, k - 1) + nbpy-undkpy-undsommes(n - k, k)bksl-nl memo[(n, k)] = ybksl-nl else:bksl-nl return memo[(n, k)]bksl-nlbksl-nlbksl-nldef nbpy-undsommes(n):bksl-nl return sum(nbpy-undkpy-undsommes(n, k) for k in range(1, 1 + n))bksl-nlbksl-nl
A
C'est la version correspondant à l'énoncé.
En effet, pour dénombrer nb_k_sommes(n, k)
, on fera deux cas :
- Les sommes dont le plus petit terme est
1
.- Il reste
k - 1
termes, pour une somme den -1
. - il y a donc
nb_k_sommes(n - 1, k - 1)
telles partitions.
- Il reste
- Les sommes dont tous les termes sont supérieurs à
1
. On enlève1
à chaque terme, ce qui donne une somme égale àn - k
enk
parties. Réciproquement, chaque partition den - k
enk
termes correspond à une partition den
enk
termes où chacun est plus grand que 1. Il y en anb_k_sommes(n - k, k)
Variante avec une autre méthode⚓︎
En représentant les sommes de \(n\) en \(k\) termes, avec un diagramme de Ferres, comme avec la somme \(7 = 3 + 2 + 1+ 1\) (somme en 4 parties)
# # # #
# #
#
On peut aussi basculer cette représentation en \(7 = 4 + 2 +1\)
# # #
# #
#
#
Et dire qu'il s'agit d'une somme où le plus grand terme est 4.
Théorème : Le nombre de partitions de \(n\) en \(k\) parties est égal au nombre de partitions de \(n\) dont la plus grande partie est égale à \(k\).
Montrons comment établir la même relation de récurrence avec cet angle de vue.
Les partitions de \(n\) peuvent aussi se dénombrer comme
- Les sommes de
n
en termes dont le plus grand terme est égal àk
, et ce, pour toutk
inférieur ou égal àn
. - Comment calculer le nombre de sommes de
n
en termes dont le plus grand terme est égal àk
de manière générale ?- Si
n < k
, il n'y a aucune façon. - Si
k = 1
, il n'y a qu'une seule façon : que des 1. - Sinon, les sommes se partagent en deux catégories :
k
est seul en tant que maximum, on lui enlève 1, on obtient une partition den
dont le plus grand terme estk-1
(et réciproquement).k
n'est pas le seul en tant que maximum, on enlève cette première colonne, on obtient une partition den - k
dont le terme maximal estk
(celui de l'ancienne deuxième colonne).
- Si
On retrouve très exactement la même récurrence.
Mémoïsation avec le cache LRU⚓︎
Cette section est uniquement pour les experts.
On peut utiliser un décorateur de fonction ! Il en existe pour automatiser la mémoïsation et ne conserver qu'une certaine quantité d'antécédents ; les plus récemment utilisés.
Avantages : c'est plus facile à écrire, c'est automatique, c'est très efficace. Problème : Ne pas utiliser un jour d'examen, sauf si vous êtes capable d'expliquer parfaitement le fonctionnement !
from functools import lru_cache
@lru_cache
def nb_sommes(n):
@lru_cache
def nb_k_sommes(n, k):
if n < k:
return 0
elif k == 1:
return 1
else:
return nb_k_sommes(n - 1, k - 1) + nb_k_sommes(n - k, k)
return sum(nb_k_sommes(n, k) for k in range(1, 1 + n))
Remarque : à partir de Python 3.9, le décorateur cache
remplace avantageusement le décorateur lru_cache
pour les situations (comme ici) où on ne met pas de limite à la zone tampon pour mémoriser les images.
Z