Décomposition en cycles non orientés
bonjour
On sait qu'il y a n! rangements possibles de n éléments en cycles orientés. En effet un rangement en cycles orientés peut être vu comme la décomposition en cycles d'une permutation de n éléments et il y a n! permutations.
Maintenant si on ignore l'orientation des cycles, combien de rangements y a t'il ?
merci
On sait qu'il y a n! rangements possibles de n éléments en cycles orientés. En effet un rangement en cycles orientés peut être vu comme la décomposition en cycles d'une permutation de n éléments et il y a n! permutations.
Maintenant si on ignore l'orientation des cycles, combien de rangements y a t'il ?
merci
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
est-il possible d'avoir des exemples de la chose pour des petites valeurs de n ?
merci d'avance.
bien cordialement
kolotoko
$$C_{n+1}=C_n+ n\sum_{k=0}^{n-1} {n-1 \choose k} C_k$$
Un conseil : jeter un coup d'oeil à OEIS.
> est-il possible d'avoir des exemples de la chose pour des petites valeurs de n ?
Après quelques recherches j'ai trouvé la dénomination exacte de ce que je cherche.
C'est le nombre de collection de colliers qu'il est possible de constituer à partir de n perles de couleurs toutes différentes.
Ce que j'appelais un "cycle non orienté" est en fait un collier. Si on retourne un collier, c'est toujours le même collier.
Il peut y avoir qu'une seule perle sur un collier.
[Inutile de répéter l'avant dernier message. Un lien suffit. AD]
Bonne idée que de chercher une relation de récurrence (mais ta formule semble fausse)
Voilà ce que je trouve:
$S_0 = S_1= 1$ ($S_0$ n'a pas de sens mais c'est utile pour la suite)
$\displaystyle S_{n+1} = S_n + nS_{n-1} + \sum_{k=2}^n C_n^k \frac {k!}{2} S_{n-k}$
et les premières valeurs à partir de $n=1$ sont : $1, 2, 5, 17, 73, 388$
Cette suite est répertoriée par OEIS ici OEIS
is the number of collections of necklaces created by using exactly n different colored beads (to make the entire collection). [Geoffrey Critzer, Apr 19 2009]
Mais leur relation de récurrence est bien plus simple: a(n) = n*a(n-1) - (n-1)*(n-2)*a(n-3)/2
Reste à comprendre comment arriver à cette relation de récurrence
$$C_{n+1}= C_n+nC_{n-1}+ \dfrac{n!}{2}\sum_{k=0}^{n-2} \dfrac{C_k}{k!}$$
Je poussé un peu plus loin pour vérifier qu'il s'agissait bien de A002135 :
$$C_{n+1}= (n+1) C_n - \dfrac{n(n-1)}{2}\,C_{n-2}$$
se comprend bien de la manière suivante. Imaginons $n$ objets répartis en cercles (flottant dans l'espace, comme ça les cercles n'ont pas d'orientation préférentielle). Un objet peut former un cercle à lui tout seul. Arrive un $n+1$-ème objet. Il peut se joindre à un cercle existant ($n$ places possibles) ou former un cercle à lui tout seul. Voila pour le $(n+1) C_n$. Mais on s'aperçoit que si le $n+1$-ème objet s'insère dans un cercle à deux, le choix de l'un ou l'autre des arcs de cercle importe peu : on aura toujours le même cercle non orienté de trois objets. Il faut donc retirer ce qu'on a compté en trop, c'est-à-dire $\dfrac{n(n-1)}{2}\,C_{n-2}$.
J'ai mis beaucoup de temps à déterminer la valeur du terme à retrancher