ENUMERATIVE QUESTIONS ON ROOTED WEIGHTED NECKLACES

We develop the language and the tools to create a new family of intege r sequences. The concrete motivation for this article came from a comb inatorial counting problem first posed by Cipra [Math. Mag. 65(1) (199 2), 56] and still open in full generality. Let C-k be the cyclic group {q(0), q(1),..., q(k-1)} and let Z[C-k] be the algebra of polynomials in the variables q(0), q(1), q(2),...,q(k-1) with coefficients from Z . We introduce weighted rooted necklaces, which give a combinatorial i nterpretation of Z[C-k]. Actions on Z[C-k] via a family of operators o f the form R(f[q])= q(t)(f[q] + h[q]), where t is an element of Z and h[q], f[q] is an element of Z[C-k], are introduced. In particular we s tudy the nonlinear, invertible operator R(f[ql]= q(-f[0])(f[q] - f[0] + Sigma(i=1)(f[0]))q(i)), sigma(f[0])q(i), where f[q] = Sigma(i=0)(k-1 ) n(i)q(i) is an element of Z[C-k] and f[0] = n(0). The operator R cre ates equivalence classes on Z[C-k]. We determine a recursive function to count the equivalence class containing G[q] = Sigma(i=0)(k) q(i) is an element of Z[C-k] which solves a special case of the aforementione d counting problem posed by Cipra. We give a closed form for such recu rsive formula in some instances. We also develop a series of related q uestions. (C) 1998 Academic Press.