1
$\begingroup$

Let $R=\{0,1\}$ and let $D$ be the set of the $2^n$ binary numbers consisting of $n$ bits. Now we apply a permutation $\pi_{i_1i_2...i_n}$ in $D$ to each element $i_1i_2...i_n$ in $D$, which is defined by $$\pi_{i_1i_2...i_n}(j_1j_2...j_n) = k_1k_2...k_n\text{ with } k_m = \begin{cases} j_m, &i_m =0\\ 1-j_m, &i_m=1\end{cases}$$ I'm asked to prove that these permutations form a group, and that the cycle index is $\frac1{2^n}\left({x_1}^{2^n}+(2^n-1){x_2}^{2^{n-1}}\right)$. Furthermore, I'm asked to calculate the number of different functions (in relation to the permutation group) from $D$ to $R$.


For proving it's a group, I should prove that the closure, associativity, identity element and inverse element properties hold for $D$. However, I'm completely lost at the cycleindex. Can anyone provide any tips?

$\endgroup$
  • $\begingroup$ "...we add..." or "we apply ? And what is a "cycle index" or "cycleindex"?? $\endgroup$ – DonAntonio Apr 22 '14 at 11:52
  • $\begingroup$ Sorry, I meant "apply" (English isn't my native language) $\endgroup$ – RBS Apr 22 '14 at 11:54
  • $\begingroup$ What is your language? And what is cycleindex?? $\endgroup$ – DonAntonio Apr 22 '14 at 11:57
  • $\begingroup$ Quote: "The cycleindex $P_G(x_1,x_2,...,x_k)$ of a permutation group $G$ on $D$ is defined as the standardized sum over the cycle structures (in other words, if $|D|=k$): $$P_G(x_1,x_2,...,x_k) = \frac{1}{|G|} \sum_{\pi\in G} x_1^{b_1(\pi)}...x_k^{b_k(\pi)}"$$, where $\pi$ is a permutation and there are $b_i(\pi)$ cycles of length $i (1\leq i\leq k)$ $\endgroup$ – RBS Apr 22 '14 at 12:09
1
$\begingroup$

When computing cycle indices we ask about the set being permuted. In your case it is the set of $2^n$ bit strings of length $n$. Your permutations are bit masks that flip the bits present in the mask being applied to all of $D$ and thereby permuting it. (Convince yourself that we indeed have permutation here -- could the bit flips produce the same value on two different inputs?) Now the empty bit mask preserves its argument, producing $2^n$ one-cycles. All other bit masks return their arguments to the initial state in two steps, producing $2^{n-1}$ two-cycles. The claim now follows. If you are familiar with table notation for permutations you may want to visualize this as a table with two rows, the first one holding the bit strings in order and the second one listing the bit-flipped value. The cycle decomposition can then be read off the table using the standard procedure of following the map until one returns to the initial value. This is not strictly necessary but it may help to understand what is going on.

To count the number of functions from $D$ to $R$ under the action of this group call it $G$ use the Polya Enumeration Theorem and substitute $1+x$ (bit zero or bit one) into the cycle index, getting $$Z(G)(1+x) = \frac{1}{2^n} \left((1+x)^{2^n}+ (2^n-1) (1+x^2)^{2^{n-1}}\right)$$ and evaluate at $x=1$ to obtain $$\frac{1}{2^n} \left(2^{2^n}+ (2^n-1) 2^{2^{n-1}}\right).$$ Computing the first few values we get $$3, 7, 46, 4336, 134281216, 288230380379570176,\ldots$$

This is OEIS A000231. We do seem to have the right answer according to the OEIS commentary.

Addendum. Here is an example to make the introduction easier to read. Suppose we are working with three binary digits ($n=3$) and the bit mask $\pi$ is $001.$ This gives $$\begin{array}{|l|l|l|l|l|l|l|l|} \hline 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\ \hline 001 & 000 & 011 & 010 & 101 & 100 & 111 & 110 \\ \hline \end{array}$$ Disjoint cycle decomposition is $$(000\quad 001)\quad (010\quad 011)\quad (100\quad 101)\quad (110\quad 111)$$ and the contribution to the cycle index is therefore $$ x_2^4 = x_2^{2^{3-1}} = x_2^{2^{n-1}}.$$

$\endgroup$

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.