If you a set of the n elements, in how many ways $Q(n,k)$ can you take some of them and arrange them on a $k$-gon, when repetition of one element is allowed but rotations of one arrangement are not counted twice?
If I am not mistaken, the number for $n=k=3$ should be 11, all of them being listed in the following image (arranged on a triangle which of course is equivalent):
My question now is to give and explain a formula for computing $Q(n,k)$ for general $n$ and $k$ and to optionally note down an algorithm for generating all possible permutations.
Ok, if I understand correctly what you want is basically the number of ways to color the vertices of a $k$-gon having $n$ colors available, but taking two colorings to be the same if you can rotate one of them so that they look the same.
To do this we need a little bit of group theory. The intuition is the following, first take the set $C$ of all the colorings of a $k$-gon with $n$ colors available (taking all of them to be different). Then take the group $\mathbb Z_k$ and define the action of $Z_k$ on $C$ by rotation, that is, if $c\in C$ is a coloring and $m\in \mathbb Z_k$define $m*c$ to be the coloring $c$ rotated so that vertex $1$ is now vertex $m+1$.
What we want to count is precisely the number of orbits under this action of $\mathbb Z_k$ on $C$. To do this we shall use Burnsides lemma.
This tells us the number of orbits is $\frac{1}{k}\sum\limits_{m\in \mathbb Z_k}|X^m|$. Where $X^m$ is the set of colorings that are unchanged after applying the rotation $m$. (In other words the colorings $c$ such that $m*c=c$).
As an example notice that the colorings that use only one color belong to $X^m$ for any $m$, since rotating them doesn't change them.
We now proceed to calculate $|X^m|$ for fixed values of $m$. What exactly is $m*c$? in the coloring $m*c$ vertex $m+1$ has the color vertex $1$ had in the coloring $c$, vertex $m+2$ has the color vertex $2$ had, and so on. The vertices are partitioned into $\gcd(m,k)$ sets of uniform size in the following sense. Take a vertex and draw the edge going from that vertex to the same vertex plus $m$. do this again with the new vertex and stop once you go back to the same vertex. You will have passed through all vertices if and only if $m$ and $k$ are relatively prime. More generally, the vertices are seperated into $\gcd(k,m)$ "connected components".
It is easy to see if you want $c=m*c$ then all vertices that belong to the same "connected component" need to have the same color. Why? well, clearly vertex $v$ needs to have the same color as vertex $v+m$, but vertex $v+m$ needs to have the s ame color as vertex $v+2m$, and so on untill we go back to vertex $v$.So if we want $c=m*c$ we can select one color for each of the $\gcd(m,k)$ components.
Thus we obtain $|X^m|=n^{\gcd(m,k)}$
Using this result in combination with Burnsides lemma we get the number of colorings is
$\frac{1}{k}\sum\limits_{m\in \mathbb Z_k}n^{gcd(m,k)}$.
But we can simplify this a bit more. to do this we make two observations: First off notice $\gcd(m,k)$ is always a divisor of $m$. Having that out of the way we ask ourselves: given $d$ a divisor of $k$, how many numbers $m$ satisfy $\gcd(m,k)=d$?. Notice $d$ does, and any number satisfying $\gcd(m,k)$ is going to be a multiple of $d$, how many of those are there?$\frac{k}{d}$, they are precisely $d,2d,3d\dots \frac{k}{d}d$. However the only ones we want are those whose coefficient is relatively prime to $\frac{k}{d}$,so that the $\gcd$ doesn't become larger. therefore there are $\varphi(\frac{k}{d})$ elements of $\mathbb Z_k$ satisfying $(m,k)=d$.
Using this we simplify the result to
$$\frac{1}{k}\sum\limits_{d|k}\varphi(k/d)n^d$$