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
Réponses
-
Bonsoir,
est-il possible d'avoir des exemples de la chose pour des petites valeurs de n ?
merci d'avance.
bien cordialement
kolotoko -
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. -
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. -
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 -
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 :
-
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}$. -
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
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 2
2 Invités