First question. I'm just generally curious about combinations in group theory. How do they relate?

  • If I take the set of permutations of $\langle 1,2,3,4 \rangle$, I get the symmetry group S4. How about the set of permutations of $\langle 0,0,1,1 \rangle$?

Longer question:

  • Suppose I look at the power-set of all permutations of $\langle 0,0,1,1 \rangle$ (or any list with repeated elements):
    • $\{\{\}, \{\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\}$
  • Now apply this equivalency relationship to partition this set into equivalency classes:

    • $\{E_1, E_2, \ldots, E_n\} \sim \{F_1, F_2, \ldots, F_n\}$ if and only if there exists a permutation such that applying this permutation to each of $\{E_1, E_2,\ldots, E_n\}$ results in ${F_1, F_2, \ldots, F_n}
    • Examples:

      • $\{ \langle 0,0,1,1\rangle \} \sim \{ \langle 0,1,0,1\rangle \}$ (transform is to swap the second and third elements)

      • $\{ \langle 0,0,1,1\rangle , \langle 0,1,0,1\rangle \} = \{ \langle 0,1,0,1\rangle , \langle 0,0,1,1\rangle \}$ (sets are unordered. These are equal and equivalent)

      • $\{ \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 \}$ (both sets have a single overlapping '1' and '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 \}$ (not equivalent. Overlapping '$1$' and '$0$' in first set, but not second)

  • There are exactly $11$ equivalency classes for the power-set of permutations of $\langle 0,0,1,1\rangle$. I'm mostly wondering how to enumerate these for larger sets of combinations, and was curious if each class cooresponds to a mathematical group.

  • $\begingroup$ Clarification of first question: $\endgroup$ – BobIsNotMyName Apr 17 '13 at 18:43

Let $S_n$ act on the set of arrangements $\mathfrak{S}$ of the multiset of $k$ ones with $n-k$ zeroes by $\sigma(a)_i=a_{\sigma(i)}$, that is, $\sigma$ acts on $a$ by sending the number $a_i$ at position $i$ to position $\sigma(i)$. We consider two of these arrangements $a$ and $b$ to be the same if $a_i=b_i$ for every $i\in\{1,\ldots,n\}$.

Now let $$a=\underbrace{1,1,1,1,\ldots}_{k\text{ ones}},\underbrace{0,0,0,0,\ldots}_{n-k\text{ zeroes}}$$ In other words, $a$ is defined by $a_i=1$ for $i=1,\ldots, k$ and $a_i=0$ for $i=k+1,\ldots, n$.

Let's compute $\operatorname{Stab}_{S_n}(a)$. It's easy to see that this is the set of all permutations $\sigma$ such that $$\sigma(i)\in\{ 1,\ldots, k\}\text{ if and only if }i\in \{1,\ldots, k\}.$$ Thus $\sigma$ may permute the set $\{1,\ldots, k\}$ and $\{k+1,\ldots, n-k\}$ in any way. It follows that $\operatorname{Stab}_{S_n}(a)\cong S_k\times S_{n-k}$. By the Orbit-Stabilizer theorem, we then have that $$\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$. Thus we can interpret this in the following way:

Given a set of $n$ objects, we want to choose $k$ of them, with no regard to how they are arranged afterwards. We choose an object in position $i$ if and only if $a_i=1$. $\mathcal{O}_a$ is the set of ways we can do this, so we conclude that ${n \choose k}=\frac{n!}{k!(n-k)!}$.

  • $\begingroup$ Small remark: What you define in the first line is a right action. $\endgroup$ – Martin Brandenburg Apr 22 '13 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.