I would like to know formula for circular variation with repetition. What I mean is :
You have round table with n-spots. On every spot there can be number from 1 to k.
So for n = 4 and k = 3 example could be.
2 1
1 3
Thet can be presented in array like this [2,1,1,3] where
[2,1,1,3]
[3,2,1,1]
[1,3,2,1]
[1,1,3,2]
the same variant.
How many option have we?
Marko
$n$ - number of spots on a circle
$k$ - number of distinct digits (for example, $1,2,...,k$)
If we define a recursive function $$f(m)=k^m-k-\sum_{d|m,1<d<m}f(d),$$ then the number of distinguishable circular configurations is $$g(n)=k+\sum_{d|n,d>1}\frac{f(d)}d.$$
Small explanation follows.
For a circle with prime number $p$ of spots there are $k$ trivial configurations: $11...1;22...2;...;kk...k$. (of course, each of configurations has $p$ digits)
Total number of combinations is $k^p$. Let's call the number of remaining, non-trivial configurations $r$. Since each of the non-trivial configurations can be repeated in $p$ ways around the circle then $k^p=k+pr,$ and therefore $r=\frac{k^p-k}p$. So total number of configurations is $k+\frac{k^p-k}p$.
Let's consider a circle with $p_1p_2$ spots, where $p_1$ and $p_2$ are prime, and $p_1\neq{p_2}$. For this case there are again $k$ trivial configurations of size $p_1p_2$. However, now we have three types of non-trivial configurations. First type is repeated $p_1$ times and is composed of $p_2$ identical parts of $p_1$ digits, second type is repeated $p_2$ times and is composed of $p_1$ identical parts of $p_2$ digits, and third type is repeated $p_1p_2$ times and is $p_1p_2$ digits long. Therefore $$r_{p_1}=\frac{k^{p_1}-k}{p_1},$$ $$r_{p_2}=\frac{k^{p_2}-k}{p_2},$$ and from total number of combinations $$k^{p_1p_2}=k+p_1r_{p_1}+p_2r_{p_2}+p_1p_2r_{p_1p_2},$$ we get $$r_{p_1p_2}=\frac{k^{p_1p_2}-k-(k^{p_1}-k)-(k^{p_2}-k)}{p_1p_2}.$$ Total number of configurations is $k+r_{p_1}+r_{p_2}+r_{p_1p_2}$.
And so on... In short, there are remaining configurations $r_d$ for each divisor $d$ of $n$ except $1$, the denominator of each $r_d$ is $d$, while the nominator of each $r_d$ is recursively defined as $k^d-k$ minus all the nominators of all remaining configurations for all divisors of $d$ except $1$ and $d$. For the total number of configurations add up all $r_d$ and add $k$ trivial configurations.