Bonjour,
Je dois montrer la récurrence verticale :
S(n+1,k)= somme( (n i) S(n-i,k-1) ) pour i allant de 0 à n
Et où (n i) est le coefficient binomial de i parmi (désolée je ne sais pas comment l’écrire sur le forum)
Je ne sais vraiment pas comment m’y prendre. Quelqu’un aurait une indication ?
Merci !!
Bonjour,
Peux-tu rappeler la définition de S(n,k) ?
Il vaut mieux avoir bien présent à l'esprit la définition de départ.
C’est le nombre de partition en k partie d’un ensemble à n éléments
Très bien.
Il s'agit donc de compter le nombre de partitions en k parties d'un ensemble à n+1 éléments.
Et on voit, à droite de l'égalité, les nombres de partitions en k-1 parties d'ensembles à n-i éléments.
Ça peut donner l'idée d'une démonstration combinatoire. On se donne un ensemble E à n+1 éléments. On choisit un élément a dans E.
Donnons nous une partition de E en k parties ... vois-tu comment continuer ?
On peut prendre une partie A qui contiendrait l’élément n+1 seulement. Les autres parties constitueraient une partition en k-1 parties de n élément.
Ou bien prendre une partie A qui contiendrait l’élément n+1 et avec un cardinal supérieur ou égal à 2. Les autres parties constituent une partition en k-1 parties d’un ensemble à n-|A|
?
Ce n'est pas encore au point, mais continue dans cette voie, et reviens avec un raisonnement bien solide.
