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

🐍 Console Python

>>> 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 somme
k == 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 enlever 1 à 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.

###

∞/∞

def nbpy-undsommes(n):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undsommes(3) == 3bksl-nlassert nbpy-undsommes(5) == 7bksl-nlbksl-nldef nbpy-undsommes(n):bksl-nl def nbpy-undkpy-undsommes(n, k):bksl-nl if n < k:bksl-nl return 0bksl-nl elif k == 1:bksl-nl return 1bksl-nl else:bksl-nl return nbpy-undkpy-undsommes(n - 1, k - 1) + nbpy-undkpy-undsommes(n - k, k)bksl-nl bksl-nl return sum(nbpy-undkpy-undsommes(n, k) for k in range(1, 1 + n))bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undsommes(3) == 3bksl-nlassert nbpy-undsommes(5) == 7bksl-nlbksl-nl

C'est la version correspondant à l'énoncé.

En effet, pour dénombrer nb_k_sommes(n, k), on fera deux cas :

📋 Texte

- Les sommes dont le plus petit terme est `1`.
    - Il reste `k - 1` termes, pour une somme de `n -1`.
    - il y a donc `nb_k_sommes(n - 1, k - 1)` telles partitions.
- Les sommes dont tous les termes sont supérieurs à `1`. On enleve `1` à chaque terme, ce qui donne une somme égale à `n - k` en `k` parties. Réciproquement, chaque partition de `n - k`  en `k` termes correspond à une partition de `n` en `k` termes où chacun est plus grand que 1. Il y en a `nb_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)

📋 Texte

# # # #
# #
#

On peut aussi basculer cette représentation en \(7 = 4 + 2 +1\)

📋 Texte

# # #
# #
#
#

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 tout k 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 de n dont le plus grand terme est k-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 de n - k dont le terme maximal est k (celui de l'ancienne deuxième colonne).

On retrouve très exactement la même récurrence.

Amélioration de la vitesse⚓︎

Très clairement, il y a de nombreux appels récursifs identiques, voici plusieurs méthodes pour éviter de recalculer plusieurs fois la même chose.

Ici, dès \(n\) environ égal à \(50\), cela devient très lent... Améliorons le code !

Avec un dictionnaire⚓︎

C'est le plus simple à réaliser. On parle de mémoïsation.

🐍 Script Python

partition_mem = dict()

def nb_sommes(n):
    def nb_k_sommes(n, k):
        if (n, k) not in partition_mem:
            if n < k:
                resultat = 0
            elif k == 1:
                resultat = 1
            else:
                resultat = nb_k_sommes(n - 1, k - 1) + nb_k_sommes(n - k, k)
            partition_mem[(n, k)] = resultat
        return partition_mem[(n, k)]

    return sum(nb_k_sommes(n, k) for k in range(1, 1 + n))

C'est un principe général de fonctionnement :

Si l'antécédent n'est pas une clé du dictionnaire, on calcule son image, on l'associe alors à l'antécédent via le dictionnaire.
Ensuite, dans tous les cas, l'antécédent est une clé, on peut renvoyer le résultat.

Avantage : c'est très efficace ! Problème : l'empreinte mémoire peut vite devenir problématique.

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 !

🐍 Script Python

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.