Polya's theorem to number of $d$-tuples of integers modulo n

124 Views Asked by At

The problem is to count the number of $d$-tuples of the integers mod $n$ where two points are considered equal if the coordinates of one are the inversions of the other.

More formally, we have $G=\mathbb{Z}_2$ acts on $\mathbb{Z}_n$ by $(0,m)\mapsto m$ and $(1,m)\mapsto -m \pmod n$ and this induces an action on $X=\mathbb{Z}_n^d$. Using Burnside's lemma, I have calculated that, $$|X/G|=\frac12[n^d+2^{d(n+1 \pmod 2)}]$$ and one can check $n=12$, $d=1$, this counts the $7$ inversion classes (in fact, jotting out the classes for a few $n$, with $d=1$, one can obtain the result by observation but I wanted to practice these tools).

Now I want to calculate the same result using Polya's theorem but I am having some trouble. I believe I have the solution for $d$-combinations and $d$-permutations, where $d\leq n$ and no repetitions are allowed. But I am unsure which weights to choose for $d$-tuples. Any help is appreciated.

1

There are 1 best solutions below

2
On BEST ANSWER

This is Power Group Enumeration with the group $A$ acting on the $n$ slots containing one permutation, namely the identity and the group $B$ acting on the values (the $d$-tuples) containing two permutations, the identity and the permutation that takes an element of a $d$-tuple to its inverse. Unfortunately we only start profiting from this technique when the two groups have cycle indices of lower count of partitions than the order of the group. We are lead back to Burnside in the present case.

With PGE in its unrestricted form we place complete cycles or sequences thereof from the cycle index of the group $B$ acting on the values on the cycles from the group $A$ acting on the slots. In the present case we have one slot permutation, the identity, which can only be covered by fixed points from the two permutations acting on the $d$-tuples. There is the identity, which contains $n$ fixed points, for a contribution of $n^d$ (we may place any fixed point on any fixed point of the slot permutation). And there is the permutation that implements the inversion, which has one fixed point namely zero when $n$ is odd and two fixed points when $n$ is even, namely zero and $n/2.$ This yields one choice for the $d$ fixed points of the slot permutation when $n$ is odd and two choices when $n$ is even for a contribution of $2^{d(n+1 \mod 2)}.$ This is the same as Burnside. The standard procedure would be to compute the cycle index of the power group $B^A$ and apply PET, but here we only have two permutations.

Observe that the choice of variables $X_0, X_1, \ldots X_{n-1}$ does not work here because the weight would not be identical on the orbits.