How do combinations (not permutations) relate to group theory?

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. • Clarification of first question: – BobIsNotMyName Apr 17 '13 at 18:43 1 Answer 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)!}\$.

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