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?
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