# Permutations of multi-set

1. Dec 8, 2015

### Crazorin

[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. Dec 8, 2015

### 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}?

3. Dec 9, 2015

### Crazorin

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.

4. Dec 22, 2015

### MrAnchovy

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