Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutations of multi-set

  1. Dec 8, 2015 #1
    [mentor note: THis is not a homework assignment. It is for a work project.]

    I need a formula that is probably based on permutations of multi-set. Except in my case you will not use up all elements of the sets, only some of them.

    For example I have the following sets: {1,1,1}{2}{3};

    Altogether 5 elements and I need to find out how many 3 digit numbers can be created. So I would use only 3 of the 5 elements.

    Or the sets could be {1,1}{2,2,2}{3}; 6 elements to create 4 digit number.
    Last edited by a moderator: Dec 8, 2015
  2. jcsd
  3. Dec 8, 2015 #2


    Staff: Mentor

    Why are there multiple sets? Is the first set allowed elements for the first digit?

    Can you give a more concrete example as sets like {1,1,1} is really the set {1}?
  4. Dec 9, 2015 #3
    When I originally wrote up the problem, I didn't used sets.
    I approached it as I have 6 numbers: 1, 1, 2, 2, 2, 3. How many different 4 digit number can be created of these 6 numbers?
    Then someone said, what I need is the permutation of multi-set. In that case you handle each repetition as a set and than use the size of the sets in the formula.
    Following this line you would get 3 sets with the size of 2, 3 and 1; and the permutation of the multi-set would be 5!/(2!3!1!)

    So I thought after a learned that the permutation of multi-set seems to be the closest what I need out of the million different permutation/combination formulas, I decided to write up the problem with sets, instead of just a list of numbers.

    I am not sure if the solution to my problem is a modification of the permutation of a multi-set, or I need a completely different approach.
  5. Dec 22, 2015 #4
    This is indeed a multiset problem, but not a simple one. You want the number of permutations of 4 items from the multiset {1, 1, 1, 2, 3}. I am not sure there is an analytical formula for this but they are simple to enumerate algorithmically:
    Code (Text):
    1    1    1
    1    1    2
    1    1    3
    1    2    1
    1    2    3
    1    3    1
    1    3    2
    2    1    1
    2    1    3
    2    3    1
    3    1    1
    3    1    2
    3    2    1
    So the answer is 21.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook