John wrote:

>Puzzle. If p is prime, how many actions of the group Z/p are there on a set with n elements?

For a database with schema \\(\mathbb{Z}_p\\) and maps the node to a set with n elements, the edge is mapped to either the identity or an n-permutation of order p.



So to find how many actions we have, we need to count the number of different n-permutations of order p and then add 1 to such number. For this purpose, let's review some basic notions and properties of n-permutations.

- We use the notation \\((i_1,i_2, ..., i_k)\\) to denote the permutation which maps the \\(i^{th}_1\\) element to the \\(i^{th}_2\\) element, the \\(i^{th}_2\\) element to the \\(i^{th}_3\\) element, ..., the \\(i^{th}_k\\) element to the \\(i^{th}_1\\) element, and leave the rest of the elements fixed. Such permutations are called a k-cycle. Each k-cycle is of order k.

- Two cycles \\((i_1,i_2, ..., i_k)\\) and \\((j_1,j_2, ..., j_l)\\) are disjoint if the sets \\(\lbrace i_1,i_2, ..., i_k\rbrace\\) and \\(\lbrace j_1,j_2, ..., j_l\rbrace\\) are disjoint.

- Every n-permutation can be written uniquely (up to rearrangement of the cycles) as a composition of disjoint cycles.

- The order of a composition of disjoint cycles is equal to the LCM of the orders of the constituent cycles.

Now, suppose \\(F\\) is a functor representing an action of the group \\(\mathbb{Z}_p\\) on a set with n elements, \\(e\\) is the edge in \\(\mathbb{Z}_p\\), then \\(F(e)\\) is either the identity or an n-permutation of order p. According to the above properties, \\(F(e)\\) must be a p-cycle, a composition of 2 p-cycles, a composition of 3 p-cycles, ..., or at most a composition of \\(\lfloor n/p \rfloor\\) p-cycles. Let's count the number of different permutations in each case.

- **1 p-cycle**: We have n choices for the first element in the p-cycle, (n-1) choices for the second element, ..., and (n-p+1) choices for the \\(p^th\\) element. However, for each such p-cycle, we overcount it by p times because the cyclic permutations of the p elements produce the same permutation. For example, \\((123)=(231)=(312)\\). Hence, there are

$$\frac{n(n-1)...(n-p+1)}{p}$$

different p-cycles.

- **Composition of 2 p-cycles**: Again, for the first p-cycle in the composition, we have \\(\frac{n(n-1)...(n-p+1)}{p}\\) choices. For the second p-cycle, since the pool of elements to pick is down to \\((n-p)\\) elements, there are only \\(\frac{(n-p)(n-p-1)...(n-2p+1)}{p}\\) choices. Finally, since disjoint p-cycles commute, scambling the order of composition produces the same permutation, we have to divide the product of the abover numbers by \\(2!\\). Hence the number of different compostions of 2 p-cycles is

$$\frac{n(n-1)...(n-2p+1)}{2!p^2}.$$

...

- **Composition of \\(\lfloor n/p \rfloor\\) p-cycles**: By the same token, there are \\(\frac{n(n-1)...(n-p+1)}{p}\\) choices for the first p-cycle, \\(\frac{(n-p)(n-p-1)...(n-2p+1)}{p}\\) choices for the second p-cycle, ..., and \\(\frac{(n-(\lfloor \frac{n}{p} \rfloor-1)p)(n-p-1)...(n-\lfloor \frac{n}{p} \rfloor p+1)}{p}\\) choices for the last p-cycle. Moreover, there are \\(\lfloor n/p \rfloor !\\) ways to scamble each composition, the number of different compostions of \\(\lfloor n/p \rfloor\\) p-cycles is

$$\frac{n(n-1)...(n-\lfloor \frac{n}{p} \rfloor p+1)}{\lfloor \frac{n}{p} \rfloor !p^{\lfloor \frac{n}{p} \rfloor}}.$$

So the total number of different actions of the group Z/p are there on a set with n elements is

$$1+\frac{n(n-1)...(n-p+1)}{p}+\frac{n(n-1)...(n-2p+1)}{2!p^2}+...\frac{n(n-1)...(n-\lfloor \frac{n}{p} \rfloor p+1)}{\lfloor \frac{n}{p} \rfloor !p^{\lfloor \frac{n}{p} \rfloor}}.$$