Formule de Cayley

[helldesv]

Bonjour,

A titre d'information, j'ai un exercice ou je dois démontrer la formule de Cayley : le nombre de graphes partiels d'un graphe complet a n sommets qui sont des arbres est n ^ (n - 2)

(Ca fait dix ans que je n'ai pas fait de maths, soyez indulgents ;) )

A pres un peu de combinatoire, je suis arrivé à la suite récurrente suivante, qui n'est malheureusement pas linéaire, du moins en apparence:

U(n) = Somme(1<=i<=n-1) [ i * (n - i) * c(n, i) * U(i) * U(n-i) ] / 2 * (n - 1)

ou c(n, i) est le nombre de combinaisons de i éléments dans n,
et Somme est l'opérateur Sigma.

J'ai bien remarqué que Somme(c(n, i) * U(i) * U(n-i)) ressemblait a un développement de type (a + b) ^ n. Ce qui m'arrangerait d'ailleurs, mais je sèche.

Est-ce que quelqu'un aurait une piste?

Merci.

[fatal_error]

salut,

je suppose que ta formule est correcte.
U(n)-U(n-1) = [ (n-1) * (1) * c(n, n-1) * U(n-1) * U(1) ] / 2 * (n - 1)
d'ou

sous résreve que le dernier facteur n-1 est au dénominateur ( oubli des parenthèses )

a partir de la,

soit :

...


Je sais pas si ca aboutit.

[helldesv]

Salut,

Merci beaucoup!
Je n'avais pas eu l'idée de former la soustraction de deux occurences consécutives.
Je vais continuer sur cette voie...

Merci encore.