Nombre de cycles Hamiltoniens

[invite6b7f553f]

Bonjour,
Si quelqu’un peut m’aider pour démontrer cette proposition :

Proposition : Le nombre de cycles Hamiltoniens dans un graphe complet non orienté Kn est égal à (n-1) ! /2 , où n est le nombre du sommets de ce graphe.

J’attends vos aides.
-----

[NicoEnac]

Bonjour,

Une petite récurrence sur le nombre de points dans un graphe serait bienvenue je pense.

[invite48a4cde4]

merci de médé à résoudre ce type de problème
poste la réponse à taglud@yahoo.fr
Problème 1
On appelle palindrome un nombre entier qui peut–être lu de gauche à droite ou de droite à gauche en donnant le même résultat. Exemple*: 1771 et 12321 sont des palindromes. Combien y a-t-il de palindromes dans l’ensemble N= *?
On désigne par an le nombre de chaînes de n caractères de l’alphabet qui ne contiennent pas le sous ensemble DM.
b1) Démontrer la relation de récurrence*: an=26an-1 – an-2
b2) Déterminer les conditions initiales et résoudre la relation de récurrence pour trouver la formule explicite de an.

***********
***********
Problème 2

Un nombre entier positif est appelé cubique s’il est divisible par la puissance 3 d’un nombre entier strictement
plus grand que 1. Par exemple, 108 est un nombre cubique car il est divisible par 3(puissance3)= 27, tandis que 175 n’est
pas un nombre cubique. Calculer le nombre des nombres cubiques dans l’ensemble (1, 2, 3, …, 1000) par le
principe du pigeonnier.

************
**************
Problème 3

1.1 (2 points)
Soit a1, a2, …a9 une permutation de 1, 2, 3, 4, 5, 6, 7, 8, 9.
a) Combien y a-t-il de permutations satisfaisant ai<ai+1 pour i=1, 2, 3, 4, 5, 6, 7, 8 ?
b) Combien y a-t-il de permutations satisfaisant ai<ai+1 pour i=1, 2, 3, 4, 6, 7, 8 et a5>a6 ?

1.2 (2 points)
On appelle suite trinaire de longueur n une suite de n chiffres appartenant à
l’ensemble {0,1,2}. Démontrer que le nombre de suites trinaires de longueur n
contenant un nombre pair de 0 est (3n + 1)/2.


**************
**************
Problème 5
Soit an le nombre de chaînes binaires de longueur n qui ne contiennent pas 110 comme sous-chaîne.
5a) (2 points) Calculer a1, a2
5b) (3 points) Montrer que an satisfait la relation de récurrence suivante :
an = an-1 + an-2 + 1, n >= 3

***************
***************