Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose we have a combinatorial bracelet composed of natural numbers.

(Two bracelets are equivalent if you can get from one to the other via rotation or reflection.)

What is the number of different bracelets whose elements sum up to a previously fixed natural number N?

Also, are there any results if we add a constraint that the number of beads on the bracelet is always odd?

P.S. Any good upper bounds are also helpful.

(EDITED in the light of the comments below)

share|improve this question
2  
When you say 'integers', do you mean 'positive integers'; or is there another additional condition? –  quid Jun 22 '11 at 23:52
    
Infinitely many, if there is no positivity requirement. Gerhard "Email Me About System Design" Paseman, 2011.06.22 –  Gerhard Paseman Jun 22 '11 at 23:52
4  
The term "combinatorial bracelet" is not defined, or used, at the link. I take it you want to put (positive?) intgers around a circle, adding up to $N$, with two arrangements considered equivalent if you can get from one to the other via rotation or reflection. My advice would be to calculate the answer for some small values of $N$, then look it up in the Online Encyclopedia of Integer Sequences. –  Gerry Myerson Jun 22 '11 at 23:54
    
    
Yes, I meant positive integers. Sorry for not being clear. And yes, Gerry, that is the right definition of a bracelet. –  Nemanja Jun 23 '11 at 12:37
add comment

2 Answers

up vote 7 down vote accepted

There is almost a bijection between your partition bracelets adding to $n$ and bracelets of length $n$ with $2$ colors. Let the colors be pluses "+" and commas "," and put a $1$ between each two beads. Then the bracelet $++,$ corresponds to the partition bracelet $1+1+1,$ or $(3)$. The bracelet $+,+,$ corresponds to $1+1,1+1,$ or $(2~2)$. The bracelet $,,,,,$ corresponds to $(1~1~1~1~1)$. The exception is that there is no partition bracelet which corresponds to $+++...+$, so there is one more bracelet of length $n$ than there are partition bracelets summing to $n$. So, use the formula for the count of bracelets and subtract $1$.

To restrict to the case where there are an odd number of terms, you restrict to an odd number of commas. I don't know whether the formula is as simple as the previous.

share|improve this answer
    
Thank you for your explanation. Actually, I have just calculated answer for small values, as Gerry Myerson suggested, and got the (almost) bijection over the OEIS, but nevertheless your explanation is valuable. –  Nemanja Jun 23 '11 at 16:17
1  
Following links give the answer to restriction to odd number of commas. oeis.org/… projecteuclid.org/DPubS/Repository/1.0/… –  Nemanja Jun 23 '11 at 16:50
add comment

This is a transform which tightens the problem and asks the reader to consult the bracelet literature.

Consider first the question as specified with the additional proviso that the number of beads is fixed at k.

The number of such bracelets is the same as the number of bracelets with k black and n white beads, if 0 is a color on the original bracelet, otherwise k black and n-k white beads. I assume 0 is not a color and let someone else deal with the case that 0 is a color. I also assume k is at most n and at least 1.

Since many of the black and white bracelets do not map to themselves under rotation and reflection, we get a lower bound of (n choose k)/2k. For more precise values, one needs to look at cyclic bracelets with a period p dividing gcd(k,n) as well as for each p considering those invariant under reflection. This analysis should be part of the bracelet literature.

Finally, as the problem did not fix k, one needs presumably to sum over all considered k to get the answer, which should be greater than the number of partitions of n.

Gerhard "Email Me About System Design" Paseman, 2011.06.23

share|improve this answer
    
Of course, for n < 5, the number of bracelets is the number of partitions of n if 0 is not a color. If 0 is a color, again there are infinitely many bracelets. Gerhard "Shouldn't Do This Sans Coffee" Paseman, 2011.06.23 –  Gerhard Paseman Jun 23 '11 at 15:23
    
Sorry, I do not understand the second paragraph. OK, you fix a size k, which seems like an interesting idea, and I assume your n is the N. But then how do you get what your write? –  quid Jun 23 '11 at 15:34
    
For each bead labeled b, I replace it with b white beads, and separate each group with a black bead. This should be a bijection. However, Douglas Zare is a professional at this, so I may be speaking in haste. Gerhard "Really Needs Coffee For This" Paseman, 2011.06.23 –  Gerhard Paseman Jun 23 '11 at 16:03
    
Thank you for the clarification, I guess I should have seen myself what you mean. I guess I also need coffee. –  quid Jun 23 '11 at 16:15
    
It looks like your bijection for that case is a restriction of my bijection. –  Douglas Zare Jun 23 '11 at 16:15
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.