Thread: Necklaces and Bracelets in Combinatorics

  1. #1
    Registered User
    Join Date
    Jan 2012

    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 :
    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
    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 is a very useful link that explains the function given above.
    Last edited by Stamatis; 03-26-2013 at 01:17 PM.

  2. #2
    Registered User
    Join Date
    Oct 2006
    how would you do it?

Popular pages Recent additions subscribe to a feed