7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Clarification of first question: $\endgroup$ Commented Apr 17, 2013 at 18:43

1 Answer 1

6
$\begingroup$

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)!}$.

$\endgroup$
1
  • $\begingroup$ Small remark: What you define in the first line is a right action. $\endgroup$ Commented Apr 22, 2013 at 21:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .