Aller au contenu

Énumération des arbres à n+1 nœuds et k feuilles⚓︎

On admettra que le nombre d'arbres ordonnés à \(n+1\) nœuds et \(k\) feuilles est égal à \(N(n, k)\), un nombre de Narayana dont on donnera la formule plus bas.

Les arbres à 4+1 nœuds et 2 feuilles

Il y en a \(N(4, 2) = 6\).

Écrire une fonction telle que narayana(n, k) renvoie le nombre d'arbres ayant n+1 nœuds et k feuilles. On utilisera un dictionnaire pour mémoriser les résultats intermédiaires.

Formules :

\[N(n, k) = \frac1n \binom{n}{k} \binom{n}{k-1}\]
\[\binom{n}{k} = \frac{n!}{k!(n-k)!}\]
\[n! = 1×2×3×...×(n-1)×n\quad\text{, et } 0! = 1\]

On n'utilisera pas le module math pour cet exercice.

Exemples
🐍 Console Python
>>> narayana(4, 3)
6
>>> narayana(5, 3)
20
###
# testsbksl-nlbksl-nlassert narayana(4, 3) == 6bksl-nlassert narayana(5, 3) == 20bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlNARAYANA = [bksl-nl [],bksl-nl [1],bksl-nl [1, 1],bksl-nl [1, 3, 1],bksl-nl [1, 6, 6, 1],bksl-nl [1, 10, 20, 10, 1],bksl-nl [1, 15, 50, 50, 15, 1],bksl-nl [1, 21, 105, 175, 105, 21, 1],bksl-nl [1, 28, 196, 490, 490, 196, 28, 1],bksl-nl [1, 36, 336, 1176, 1764, 1176, 336, 36, 1],bksl-nl [1, 45, 540, 2520, 5292, 5292, 2520, 540, 45, 1],bksl-nl [1, 55, 825, 4950, 13860, 19404, 13860, 4950, 825, 55, 1],bksl-nl]bksl-nlbksl-nlfor n, ligne in enumerate(NARAYANA):bksl-nl for k in range(1, n):bksl-nl assert narayana(n, k) == NARAYANA[n][k-1]bksl-nlbksl-nl ∞/∞

factorial = [1]bksl-nlbksl-nldef narayana(n, k):bksl-nl i = len(factorial)bksl-nl while n >= i:bksl-nl fpy-undi = factorial[...] py-str ...bksl-nl factorial.append(...)bksl-nl i = ...bksl-nl return ...bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert narayana(4, 3) == 6bksl-nlassert narayana(5, 3) == 20bksl-nlbksl-nlbksl-nlfactorial = [1]bksl-nlbksl-nldef narayana(n, k):bksl-nl i = len(factorial)bksl-nl while n >= i:bksl-nl fpy-undi = factorial[i - 1] py-str ibksl-nl factorial.append(fpy-undi)bksl-nl i += 1bksl-nl return (bksl-nl (factorial[n] // factorial[k] // factorial[n - k])bksl-nl py-str (factorial[n] // factorial[k - 1] // factorial[n - k + 1])bksl-nl // nbksl-nl )bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert narayana(4, 3) == 6bksl-nlassert narayana(5, 3) == 20bksl-nlbksl-nl

A

Z

Arbres à 5+1 nœuds et 3 feuilles

Il y en a \(N(5, 3) = 20\)