Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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