# Is an algebraic formula for the number of cyclic compositions of n known?

From Wikipedia:

In January 2011, it was announced that Ono and Jan Hendrik Bruinier, of the Technische Universität Darmstadt, had developed a finite, algebraic formula determining the value of p(n) (number of partitions of n) for any positive integer n.

Is such a formula known for the number of cyclic compositions of n (i. e., cyclically ordered partitions of n - where (1,2,3), (2,3,1), and (3,1,2) are considered the same, but not (1,3,2))?

If so, what about the number of cyclic compositions of n with parts at least equal to 2?

-
You could try computing the number of cyclic compositions of $n$ for a few small values of $n$ and then looking up the resulting sequence of numbers in the Online Encyclopedia of Integer Sequences. Let us know what you find. –  Gerry Myerson Nov 7 '11 at 21:51
@Gerry, I did this for the second sequence listed above (cyclic compositions with parts at least equal to 2); it's OEIS A032190. I will check the first sequence as well. –  Dan Moore Nov 7 '11 at 23:07
@Gerry, The first sequence listed above (cyclic compositions) is A08965. –  Dan Moore Nov 7 '11 at 23:16
Good. Post what you have found as an answer (it may seem strange, but the rules actually explicitly encourage this) and accept it and then we can all move on to the next question. –  Gerry Myerson Nov 8 '11 at 0:13

Added March 5, 2012: Arnold Knopfmacher and Neville Robbins (Some Properties of Cyclic Compositions, Fibonacci Quarterly, August 2010) give the number of cyclic compositions of n having k parts as:

$\langle$ $\matrix{n\cr k}$ $\rangle$ = $1/n$ $\sum_{j|gcd(n,k)}\phi(j)$ ( $\matrix{n/j\cr k/j}$ )

Also:

$\sum_{k=1}^n\langle$ $\matrix{n\cr k}$ $\rangle$ = $-1 + 1/n$ $\sum_{d|n}\phi(d)$ $2^{n/d}$

The Online Encyclopedia of Integer Sequences shows the first few values of the following:

-A08965 gives the number of cyclic compositions of n; and

-A032190 gives the number of cyclic compositions of n having parts at least equal to 2.

If there is an algebraic formula for the latter sequence not relying on the prime factorization of n, then RSA-type factoring might be relatively simple. It’s straightforward to show the following: The number of ways of choosing one or more vertices from an n-gon where no two chosen vertices are consecutive is fn+1 + fn-1 – 1, where fn is the Fibonacci sequence.

Denote the A032190 sequence as cc(2, n), and define a composite cyclic composition as a cyclic composition composed of two or more identical sub-compositions. Define a primitive cyclic composition as a cyclic composition that is not composite, and denote the number of these as ccprim(2, n). It’s straightforward that the number of vertex arrangements described above is $\sum_{a|n}$ a * ccprim(2, a). Also, cc(2, n) = $\sum_{a|n}$ ccprim(2, a). So, you have:

n * ccprim(2, n) $\le$ fn+1 + fn-1 – 1 $\le$ n * cc(2, n),

with equality occurring if n is prime; otherwise strict inequality.

Say you have a large n with two prime factors k and m, the (much) larger of which is m. You have:

k * ccprim(2, k) + m * ccprim(2, m) + n * ccprim(2, n) = fn+1 + fn-1 – 1, and

cc(2, n) = cc(2, k) + cc(2, m) + ccprim(2, n) (as k and m are prime.)

Starting with a good enough estimate of cc(2, n), develop an estimate for m by ignoring the smallest term involving k and rounding (n - m) to n as follows:

n*cc(2, n) - (fn+1 + fn-1 – 1) $\approxeq$ (n - m) * cc(2, m) $\approxeq$ n * (fm+1 + fm-1 – 1) / m

-

I do not have access to the above article at this time but as the results are fairly basic I will try to include a proof here, for the sake of completeness and with no claim to originality.

We will use the Polya Enumeration Theorem. By definition we have that $$\Big\langle {n\atop k}\Big\rangle = [z^n] Z(C_k)\left(\frac{z}{1-z}\right)$$ where $Z(C_k)$ is the cycle index of the cyclic group acting on $k$ slots. The notation here is from the first response and should not be confused with Eulerian numbers.

Now we have $$Z(C_k) = \frac{1}{k} \sum_{q|k} \varphi(q) a_q^{k/q}.$$

Substituting $Z(C_k)$ into the above we obtain $$\Big\langle {n\atop k}\Big\rangle = [z^n] \frac{1}{k} \sum_{q|k} \varphi(q) \left(\frac{z^q}{1-z^q}\right)^{k/q} = [z^n] \frac{1}{k} \sum_{q|k} \varphi(q) \frac{z^k}{(1-z^q)^{k/q}} \\ = [z^{n-k}] \frac{1}{k} \sum_{q|k} \varphi(q) \frac{1}{(1-z^q)^{k/q}}.$$

The next step is to expand the rational term in $z$ using the Newton binomial taking care to note that it only contains exponents that are multiples of $q$ in its power series. This yields $$\frac{1}{k} \sum_{q|k \wedge q|n} \varphi(q) {\frac{n-k}{q} + \frac{k}{q} - 1 \choose \frac{k}{q} -1} = \frac{1}{k} \sum_{q|k \wedge q|n} \varphi(q) {\frac{n}{q} - 1 \choose \frac{k}{q} -1} \\= \frac{1}{k} \sum_{q|k \wedge q|n} \varphi(q) \frac{k/q}{n/q} {n/q \choose k/q } = \frac{1}{n} \sum_{q|\gcd(k,n)} \varphi(q) {n/q \choose k/q }.$$ This establishes the first formula.

For the sum we have that $$\sum_{k=1}^n \Big\langle {n\atop k}\Big\rangle = \frac{1}{n} \sum_{k=1}^n \sum_{q|\gcd(k,n)} \varphi(q) {n/q \choose k/q }.$$ Re-indexing this on $q$ and putting $k=pq$ yields $$\frac{1}{n} \sum_{q|n} \varphi(q) \sum_{p=1}^{n/q} {n/q \choose p} = \frac{1}{n} \sum_{q|n} \varphi(q) (2^{n/q} - 1) \\ = - \frac{1}{n} \sum_{q|n} \varphi(q) + \frac{1}{n} \sum_{q|n} \varphi(q) 2^{n/q} = - 1 + \frac{1}{n} \sum_{q|n} \varphi(q) 2^{n/q}.$$ This establishes the second formula.

There are many more Polya Enumeration computations at this MSE Meta link.

Addendum. The count for parts at least equal to two is given by $$[z^n] Z(C_k)\left(\frac{z^2}{1-z}\right)$$

which yields $$[z^{n-2k}] \frac{1}{k} \sum_{q|k} \varphi(q) \frac{1}{(1-z^q)^{k/q}}$$ which produces $$\frac{1}{k} \sum_{q|k \wedge q|n} \varphi(q) {\frac{n-2k}{q} + \frac{k}{q} - 1 \choose \frac{k}{q} -1} = \frac{1}{k} \sum_{q|k \wedge q|n} \varphi(q) {\frac{n-k}{q} - 1 \choose \frac{k}{q} -1} \\ = \frac{1}{k} \sum_{q|k \wedge q|n} \varphi(q) \frac{k/q}{(n-k)/q} {\frac{n-k}{q} \choose \frac{k}{q}} = \frac{1}{n-k} \sum_{q|\gcd(k,n)} \varphi(q) {(n-k)/q \choose k/q}.$$

This seems to be the right count e.g. for $k=5$ and $n\ge 10$ we get $$1, 1, 3, 7, 14, 26, 42, 66, 99, 143, 201, 273, 364, 476, 612, 776,\ldots$$ which is OEIS A008646.

For $k=6$ and $n \ge 12$ we get $$1, 1, 4, 10, 22, 42, 80, 132, 217, 335, 504, 728, 1038, 1428, 1944,\ldots$$ which is OEIS A032191.

Note that by a trivial argument these values for parts at least two are also given by $$\Big\langle {n-k\atop k}\Big\rangle$$ (put a value one in every slot then add a cyclical composition into $k$ parts of $n-k$, this assures that all parts are at least two and the initial value does not change the symmetry.)

-