3
$\begingroup$

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)

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ When you say 'integers', do you mean 'positive integers'; or is there another additional condition? $\endgroup$
    – user9072
    Jun 22, 2011 at 23:52
  • $\begingroup$ Infinitely many, if there is no positivity requirement. Gerhard "Email Me About System Design" Paseman, 2011.06.22 $\endgroup$
    – Gerhard Paseman
    Jun 22, 2011 at 23:52
  • 4
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Jun 22, 2011 at 23:54
  • $\begingroup$ mathoverflow.net/questions/12214/… $\endgroup$
    – Steve Huntsman
    Jun 23, 2011 at 4:01
  • $\begingroup$ Yes, I meant positive integers. Sorry for not being clear. And yes, Gerry, that is the right definition of a bracelet. $\endgroup$
    – Nemanja
    Jun 23, 2011 at 12:37

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Nemanja
    Jun 23, 2011 at 16:17
  • 1
    $\begingroup$ Following links give the answer to restriction to odd number of commas. oeis.org/… projecteuclid.org/DPubS/Repository/1.0/… $\endgroup$
    – Nemanja
    Jun 23, 2011 at 16:50
3
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Jun 23, 2011 at 15:23
  • $\begingroup$ 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? $\endgroup$
    – user9072
    Jun 23, 2011 at 15:34
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Jun 23, 2011 at 16:03
  • $\begingroup$ Thank you for the clarification, I guess I should have seen myself what you mean. I guess I also need coffee. $\endgroup$
    – user9072
    Jun 23, 2011 at 16:15
  • $\begingroup$ It looks like your bijection for that case is a restriction of my bijection. $\endgroup$
    – Douglas Zare
    Jun 23, 2011 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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