Permutations, given a set of repeated digits

gAr · 2011-01-09 17:31:08

Suppose there are few digit {n1, n1, n2, n2, n2, n3, n3, n3 ... }, is there a simple way to find the no. of k-digit numbers?

E.g. , integers given are {1, 1, 2, 2, 3, 3, 4, 4, 4, 4}, how many 4-digit numbers can be formed?
Is there a method other than listing it manually 1122, 1123, 1124 ... and then adding the permutation of each of the 4-digit numbers??

At first I thought there must be an easy way, but wasn't able to figure it out.

bobbym · 2011-01-09 18:53:24

Hi gAr;

Yes there is a nice mathematical method to do these. The answer to your question is 217 permutations.

gAr · 2011-01-09 19:34:43

Hi bobbym,

good to know that there is a method, can you explain the method?
thanks..

bobbym · 2011-01-09 19:49:13

Because you have access to a CAS I can give you the advanced method. Most of the time you see people working these with NCR's and something they call casework. It is pure drudgery and makes people hate combinatorics.

The concept of the generating function is both beautiful and computationally easy. For permutations of a multiset ( list with repeated elements ) you use polynomial multiplication.

Enter into sage and expand:

You should get this.

Take a look at the coefficient of x^4 it is 217 / 24. Times that fraction by 24 and you get 217 that is the answer.

gAr · 2011-01-09 21:24:40

Oh, I haven't dealt with multisets I did not know it was called a multiset... The books I have seen, as I remember, did not have the topic of multisets under generating function...

So, if I need to know the no. of 5-digit numbers, is it (co-efficient of x^5) * (5!) ?

bobbym · 2011-01-09 21:27:37

That is right! The good part is the expansion solves for all of them from 1 to 10.

gAr · 2011-01-09 21:56:56

Ok, thanks...
that cleared my doubts

bobbym · 2011-01-09 22:10:32

No problem, glad to help.

gAr · 2011-01-09 22:11:57

Last one thing to ask,
what if I want the chosen number to begin with 1?

Is this the generating function:

bobbym · 2011-01-09 22:15:30

That looks good but what power are you interested in checking the coefficient of?

gAr · 2011-01-09 23:05:01

E.g., from post#1, I need the 4-digit numbers to begin with 1.
So I keep the first position fixed to 1. Then for the remaining 3 digits, the set is reduced to {1,2,2,3,3,4,4,4,4}. So I use the generating function :

and then find the co-efficent of x^3. Is that right?

I'm also curious to know if there are other methods. It was once asked in an exam, so generating functions would be tedious to do by hand

bobbym · 2011-01-09 23:12:57

That is what I would do.

I have never found a way that worked by another method for this type. If I think of one I will post it.

gAr · 2011-01-09 23:41:16

Thanks... you helped me to know the application of exponential generating function.

bobbym · 2011-01-09 23:48:25

That is what it is called. Actually, I remember working on this problem before. I have never even seen a solution to it. It is easy if you use the whole set but if you do not...

wintersolstice · 2011-01-11 08:09:12

I thought there was a simple formula, when you have a series of symbols (some are repeated)? then

where a,b,c represent the number of times each repeated symbol appears

Last edited by wintersolstice (2011-01-11 08:30:00)

bobbym · 2011-01-11 08:31:08

Hi;

I call that the Mississippi problem. That only works when you use all of them. When you only use some of them it is more complicated.

Math Is Fun Forum

#1 2011-01-09 17:31:08

Permutations, given a set of repeated digits

#2 2011-01-09 18:53:24

Re: Permutations, given a set of repeated digits

#3 2011-01-09 19:34:43

Re: Permutations, given a set of repeated digits

#4 2011-01-09 19:49:13

Re: Permutations, given a set of repeated digits

#5 2011-01-09 21:24:40

Re: Permutations, given a set of repeated digits

#6 2011-01-09 21:27:37

Re: Permutations, given a set of repeated digits

#7 2011-01-09 21:56:56

Re: Permutations, given a set of repeated digits

#8 2011-01-09 22:10:32

Re: Permutations, given a set of repeated digits

#9 2011-01-09 22:11:57

Re: Permutations, given a set of repeated digits

#10 2011-01-09 22:15:30

Re: Permutations, given a set of repeated digits

#11 2011-01-09 23:05:01

Re: Permutations, given a set of repeated digits

#12 2011-01-09 23:12:57

Re: Permutations, given a set of repeated digits

#13 2011-01-09 23:41:16

Re: Permutations, given a set of repeated digits

#14 2011-01-09 23:48:25

Re: Permutations, given a set of repeated digits

#15 2011-01-11 08:09:12

Re: Permutations, given a set of repeated digits

#16 2011-01-11 08:31:08

Re: Permutations, given a set of repeated digits

Board footer