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?
 A: 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
A: 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.)
