Cómo hacer combinaciones (no permutaciones) se refieren a la teoría de grupo?

Question

La primera pregunta. Estoy en general curioso acerca de las combinaciones en teoría de grupos. ¿Cómo se relacionan?

• Si me tome el conjunto de permutaciones de $\langle 1,2,3,4 \rangle$, me sale el grupo de simetría S4. Cómo sobre el conjunto de las permutaciones de $\langle 0,0,1,1 \rangle$?

No pregunta:

• Supongamos que fijamos en el poder-el conjunto de todas las permutaciones de $\langle 0,0,1,1 \rangle$ (o de cualquier lista con elementos repetidos):
  • $\{\{\}, \{\langle 0,0,1,1\rangle\}, \{\langle 0,1,0,1\rangle \},\ldots,\{\langle 0,0,1,1\rangle,\langle 0,1,0,1 \rangle \}, \ldots\}$

• Ahora aplicar esta relación de equivalencia para la partición de este conjunto en clases de equivalencia de:

  • $\{E_1, E_2, \ldots, E_n\} \sim \{F_1, F_2, \ldots, F_n\}$ si y sólo si existe una permutación tal que la aplicación de esta permutación para cada una de las $\{E_1, E_2,\ldots, E_n\}$ resultados en ${F_1, F_2, \ldots, F_n}

  • Ejemplos:

    • $\{ \langle 0,0,1,1\rangle \} \sim \{ \langle 0,1,0,1\rangle \}$ (transformación es intercambiar los elementos segundo y tercero)

    • $\{ \langle 0,0,1,1\rangle , \langle 0,1,0,1\rangle \} = \{ \langle 0,1,0,1\rangle , \langle 0,0,1,1\rangle \}$ (conjuntos están desordenadas. Estos son iguales y equivalentes)

    • $\{ \langle 0,0,1,1\rangle , \langle 0,1,0,1\rangle \} \sim \{ \langle 0,1,1,0\rangle , \langle 1,1,0,0\rangle \}$ (ambos conjuntos tienen un solo superposición de '1' y '0')

    • $\{ \langle 0,0,1,1\rangle , \langle 0,1,0,1\rangle \} \not= \{ \langle 0,1,1,0\rangle , \langle 1,0,0,1\rangle \}$ (no equivalente. La superposición de '$1$ " y "$0$ ' en el primer set, pero no la segunda)

• Hay exactamente $11$ equivalencia de clases por el poder-el conjunto de las permutaciones de $\langle 0,0,1,1\rangle$. Yo soy todo preguntándose cómo enumerar estas para grandes conjuntos de combinaciones, y fue por curiosidad, si cada clase cooresponds a un grupo de matemáticos.

Answer 1

Deje $S_n$ actúan en el conjunto de arreglos $\mathfrak{S}$ del conjunto múltiple de $k$ con $n-k$ ceros por $\sigma(a)_i=a_{\sigma(i)}$, $\sigma$ actúa en $a$ enviando el número de $a_i$ en la posición $i$ a la posición $\sigma(i)$. Consideramos que dos de estos arreglos $a$ $b$ a ser el mismo si $a_i=b_i$ por cada $i\in\{1,\ldots,n\}$.

Ahora vamos a $$a=\underbrace{1,1,1,1,\ldots}_{k\text{ ones}},\underbrace{0,0,0,0,\ldots}_{n-k\text{ zeroes}}$$ En otras palabras, $a$ está definido por $a_i=1$$i=1,\ldots, k$$a_i=0$$i=k+1,\ldots, n$.

Vamos a calcular $\operatorname{Stab}_{S_n}(a)$. Es fácil ver que este es el conjunto de todas las permutaciones $\sigma$ tal que $$\sigma(i)\in\{ 1,\ldots, k\}\text{ if and only if }i\in \{1,\ldots, k\}.$$ Por lo tanto $\sigma$ puede permutar el conjunto $\{1,\ldots, k\}$ $\{k+1,\ldots, n-k\}$ en cualquier forma. De ello se desprende que $\operatorname{Stab}_{S_n}(a)\cong S_k\times S_{n-k}$. Por la Órbita-Estabilizador de teorema, entonces tenemos que $$\left|\mathcal{O}_a\right|=[S_n:S_k\times S_{n-k}]=\frac{\left|S_n\right|}{\left|S_k\times S_{n-k}\right|}=\frac{n!}{k!(n-k)!}$$ (Look familiar?) So let's think about what $\mathcal{O}_a$ is - the set of all arrangements in $\mathfrak{S}$ for which the $1$'s and $0$'s are in different positions than $1,1,1,1,\ldots,0,0,0,0,\ldots$. By forgetting the arrangements of the $1$s and $0$s among themselves, we have made them indistinct, and all that matters is which positions are $1$ and which are $0$. Por lo tanto, podemos interpretar esto de la siguiente manera:

Dado un conjunto de $n$ objetos, queremos elegir a $k$ de ellos, con independencia de cómo se organizan después. Elegimos un objeto en la posición $i$ si y sólo si $a_i=1$. $\mathcal{O}_a$ es el conjunto de formas en que podemos hacer esto, así que llegamos a la conclusión de que ${n \choose k}=\frac{n!}{k!(n-k)!}$.