Calculer le nombre de permutations de séquence

Question

Je voudrais calculer le non. permutations possibles pour un sous-ensemble d'objets. Considérez l'ensemble des objets:$$ X = \{X_1,X_2,X_3,....,X_N\} $$ Question: Quel est le nombre de façons dont je peux choisir une sous-séquence $X$ de longueur $M \leq N$, tel que:

1. Chaque objet, $X_i$, ne peut apparaître qu'une seule fois dans la sous-séquence

2. L'ordre compte, c'est-à-dire $S_1 = \{X_1, X_2, X_3\}$ n'est pas la même chose que $S_2 = \{X_2, X_1, X_3\}$ - c'est-à-dire que ces deux exemples comptent pour 2

3. Symétrie de rotation, c'est-à-dire $S_1 = \{X_1, X_2, X_3\}$ est le même que $S_2 = \{X_2, X_3, X_1\}$ - c'est-à-dire que ces deux exemples comptent pour 1. La raison en est que $S_2$ apparaît comme une sous-séquence de $S_1$ si $S_1$ est répété $\{X_1, \mathbf{X_2, X_3\} \{X_1}, X_2, X_3\}$.

J'ai pu trouver une formule pour le problème de 1) et 2). Le nombre de combinaisons est la manière de choisir M éléments parmi N éléments. Sans répétition et avec ordre, la formule est:$\frac{N!}{(N-M)!}$. Cependant, je ne sais pas comment étendre la formule pour tenir compte de 3).

Answer 1

Il y a $M$ façons de faire pivoter un ensemble pour obtenir $$\frac{N!}{M(N-M)!}$$ Le total, pour $M=1$ à $N$, est dans http://oeis.org/A002104

Answer 2

Vous voudrez peut-être essayer avec le problème vous-même, c'est intéressant! Voici quelques conseils

1. Chaque $n$-Ensemble d'éléments $S$ a $2^{\vert S\vert}=\displaystyle\sum_{k=1}^{n}\binom{n}{k}$ sous-ensembles.
2. Chaque sous-ensemble $S_k \subseteq S$ a $k!$ permutations.
3. La rotation est cependant délicate . Vérifiez le problème des manèges .