É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 :
On n'utilisera pas le module math
pour cet exercice.
Exemples
>>> narayana(4, 3)
6
>>> narayana(5, 3)
20
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\)