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.

###

Lancer# testsbksl-nlbksl-nlassert nbpy-undsommes(3) == 3bksl-nlassert nbpy-undsommes(5) == 7bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlassert nbpy-undsommes(1) == 1bksl-nlassert nbpy-undsommes(2) == 2bksl-nlassert nbpy-undsommes(4) == 5bksl-nlassert nbpy-undsommes(10) == 42bksl-nlassert nbpy-undsommes(42) == 53174bksl-nlbksl-nldef OFFpy-undnbpy-undsommes(n):bksl-nl def OFFpy-undnbpy-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 OFFpy-undnbpy-undkpy-undsommes(n - 1, k - 1) + OFFpy-undnbpy-undkpy-undsommes(n - k, k)bksl-nl bksl-nl return sum(OFFpy-undnbpy-undkpy-undsommes(n, k) for k in range(1, 1 + n))bksl-nlbksl-nlfor n in range(1, 43):bksl-nl attendu = OFFpy-undnbpy-undsommes(n)bksl-nl assert nbpy-undsommes(n) == attendu, f"Erreur avec n = {n}"bksl-nlbksl-nl Valider ∞/∞ TéléchargerTéléverser RechargerSauvegarder

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-nlNone

A

Z