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