You are not logged in.
Pages: 1
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.
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
Offline
Hi gAr;
Yes there is a nice mathematical method to do these. The answer to your question is 217 permutations.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
Hi bobbym,
good to know that there is a method, can you explain the method?
thanks..
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
Offline
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.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
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!) ?
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
Offline
That is right! The good part is the expansion solves for all of them from 1 to 10.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
Ok, thanks...
that cleared my doubts
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
Offline
No problem, glad to help.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
Last one thing to ask,
what if I want the chosen number to begin with 1?
Is this the generating function:
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
Offline
That looks good but what power are you interested in checking the coefficient of?
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
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
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
Offline
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.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
Thanks... you helped me to know the application of exponential generating function.
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
Offline
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...
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
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)
Why did the chicken cross the Mobius Band?
To get to the other ...um...!!!
Offline
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.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
Pages: 1