Décomposition en cycles non orientés

joel_5632 · September 2013

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

kolotoko0 · September 2013

Bonsoir,

est-il possible d'avoir des exemples de la chose pour des petites valeurs de n ?

merci d'avance.

bien cordialement

kolotoko

Zo! · September 2013

Si on appelle $C_n$ le nombre que tu cherches, il y a, sauf erreur, une formule de récurrence sur le principe de la formule de récurrence pour le nombre de partitions :
$$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.

joel_5632 · September 2013

kolotoko écrivait:

> 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.

joel_5632 · September 2013

Zo! écrivait : http://www.les-mathematiques.net/phorum/read.php?34,867259,867436#msg-867436
[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

Zo! · September 2013

Oui, tu as raison, je m'étais trompé dans mon calcul et ça m'a réveillé en sursaut cette nuit

. D'accord avec ta formule, une variante (je garde mon $C_n$, qui me fait penser à "cercles") :
$$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 :

29580

Zo! · September 2013

La formule de récurrence
$$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}$.

joel_5632 · September 2013

Bien vu Zo! pour l'explication de la relation: $C_{n+1}= (n+1) C_n - \dfrac{n(n-1)}{2}\,C_{n-2}$

J'ai mis beaucoup de temps à déterminer la valeur du terme à retrancher

Décomposition en cycles non orientés

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 18