Calcular el número de permutaciones de la secuencia

Question

Me gustaría calcular el número de permutaciones posibles para un subconjunto de objetos. Considere el conjunto de objetos: $$ X = \{X_1,X_2,X_3,....,X_N\} $$ Pregunta: ¿Cuál es el número de formas en que puedo escoger una subsecuencia de $X$ de longitud $M \leq N$ tal que..:

1. Cada objeto, $X_i$ sólo puede aparecer una vez en la subsecuencia

2. El orden importa, es decir $S_1 = \{X_1, X_2, X_3\}$ no es lo mismo que $S_2 = \{X_2, X_1, X_3\}$ - es decir, estos dos ejemplos cuentan como 2

3. Simetría rotacional, es decir $S_1 = \{X_1, X_2, X_3\}$ es lo mismo que $S_2 = \{X_2, X_3, X_1\}$ - es decir, estos dos ejemplos cuentan como 1. La razón de esto es que $S_2$ aparece como una subsecuencia de $S_1$ si $S_1$ se repite $\{X_1, \mathbf{X_2, X_3\} \{X_1}, X_2, X_3\}$ .

He podido elaborar una fórmula para el problema teniendo en cuenta 1) y 2). El número de combinaciones son las formas de elegir M elementos de un conjunto de N elementos. Sin repetición y con orden, la fórmula es: $\frac{N!}{(N-M)!}$ . Sin embargo, no sé cómo ampliar la fórmula para tener en cuenta 3).

Answer 1

Hay $M$ formas de girar un conjunto, por lo que se obtiene $$\frac{N!}{M(N-M)!}$$ El total, para $M=1$ a $N$ , está en http://oeis.org/A002104

Answer 2

Quizá quieras probar con el problema tú mismo, ¡es interesante! Aquí tienes algunos consejos

1. Cada $n$ -conjunto de elementos $S$ tiene $2^{\vert S\vert}=\displaystyle\sum_{k=1}^{n}\binom{n}{k}$ subconjuntos.
2. Cada subconjunto $S_k \subseteq S$ tiene $k!$ permutaciones.
3. Sin embargo, la rotación es complicada . Consulte Tiovivos problema.