1
$\begingroup$

Given a circular code $X$ (for example: $X=\{ w,b \}$) with generating function $u(z)=\sum\limits_{k=0}^{\infty}{u_k z^k}$ (in this example : $u(z)=2z$), the generating function $p(z)=\sum\limits_{k=0}^{\infty}{p_k z^k}$ counts all words with a conjugate in $X^{*}$ which is given by $p(z)=\frac{z u'(z)}{1-u(z)}$. For more details, you can see "Handbook of Enumeration" (edited by Miklos Bona, chapter 8.3) or part one of the combinatorics book which is written by Stanley (Proposition 4.7.13).

In our example, $X=\{w,b \}$, $p_n$ would count all necklaces with white and black points having in total $n$ points (not up to rotation). If we want to count $c_n$, the number of such necklaces up to rotation, then $c_n$ and $p_n$ are in general related by $c_n= \frac{1}{n} \sum\limits_{d | n}^{}{\phi(\frac{n}{d}) p_d}$. Now I want to do all this in a weighted situation, so for example I want to take how many points are black into considerations. Thus, I need multivariable generating function. In the example $X= \{w, b \}$, this would be $u(x,y)=x+y$. What are the generalizations to the weighted (multivariable) situation for the formulas: $p(z)=\frac{z u'(z)}{1-u(z)}$ and $c_n= \frac{1}{n} \sum\limits_{d | n}^{}{\phi(\frac{n}{d}) p_d}$? Is there a reference? Of course for $X= \{w,b \}$ everything is easy but there are more complicated things like $X= \{b,baa,baaaa,baaaaaa,.... \}$, which by the way has a nice solution in the one-variable case: https://oeis.org/A001350 .

$\endgroup$
1
$\begingroup$

The formula expressing $c_n$ in terms of $p_d$ follows from the Redfield-Polya enumeration theorem, which also has a weighted mutivariate version. See https://en.wikipedia.org/wiki/Pólya_enumeration_theorem

$\endgroup$
  • $\begingroup$ Thank you for your answer. But I can not find an explicit formula, generalizing the one-dimensional case on wikipedia. Also I would prefer a book reference. Note that I am not a combinatorialist and I search a reference, which I can directly quote. $\endgroup$ – Mare May 7 '16 at 12:27
  • $\begingroup$ Wikipedia gives some references. Necklaces are described in a separate article en.wikipedia.org/wiki/Necklace_(combinatorics) $\endgroup$ – Max Alekseyev May 7 '16 at 12:34
  • $\begingroup$ Note also that Im searching for a reference for the problem with general $X$. Most books only look at the case $X= \{ a_1, a_2 , ... , a_n \}$ with $n$ colors. $\endgroup$ – Mare May 7 '16 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.