# Thread: Necklaces and Bracelets in Combinatorics

1. ## Necklaces and Bracelets in Combinatorics

Ok, it seems I need some help in understanding and solving the following problem:
input :
4 (k)
6 3 2 2 2 (n,m,a1,a2,a3)
6 3 3 2 1 (n,m,a1,a2,a3)
4 2 2 2
12 4 6 2 2 2

output :
11
6
2
3530
SO : k is the number of test cases
n : the number of beads we have available
m: the colours of the beads we have
a1,a2,...a : the amount of beads of each colour that we must use.(note that we have m of these numbers)

For instance with 6 3 2 2 2 we have 6 beads, of 3 colours, and have 2 beads of each colour.
The question is "what is the maximum number of bracelets we can make using all the beads" ?
I have done some research on this and have found that the max number of bracelets of n-size and k-colours comes from this function
http://mathworld.wolfram.com/images/...dEquation2.gif
but this doesn't seem to implement the fact that you have a limited amount of beads of each colour and basicaly just gives you the amount of bracelets Combinatorial Necklaces and Bracelets - Jason Davies (see here) (if for instance n=6 and k=3, it comes out with 130, when what I want is 6 or 11)
What do I have to change in order to make it compatible with my specific input ?
(sry for possible bad english at some points)

EDIT: THIS http://mathworld.wolfram.com/Necklace.html is a very useful link that explains the function given above.

2. how would you do it?