|
|
| Author |
Message |
MatthewGKerr@gmail.com
science forum beginner
Joined: 18 May 2006
Posts: 1
|
 Posted: Thu May 18, 2006 1:23 am Post subject:
Help with permutations
|
|
|
Son asked me to explain, but knowledge limited regarding permutations.
x1 + x2 + x3 = 15, how many permutions are there when 0< x1 <= 6;
Manually doing the process reveals 75 combinations to produce the
required outcome however I can seem to do the math. I know that total
permutations = c(n + k-1, k-1) = c(15 + 3 -1, 3-1) = c(17,2) = (17 *
16)/2! = 136.
Please can someone explain how to solve this. |
|
| Back to top |
|
 |
Gerry Myerson
science forum Guru
Joined: 28 Apr 2005
Posts: 871
|
| Posted: Thu May 18, 2006 2:44 am Post subject:
Re: Help with permutations
|
|
|
In article <1147915384.637904.217010@38g2000cwa.googlegroups.com>,
MatthewGKerr@gmail.com wrote:
| Quote: | Son asked me to explain, but knowledge limited regarding permutations.
x1 + x2 + x3 = 15, how many permutions are there when 0< x1 <= 6;
Manually doing the process reveals 75 combinations to produce the
required outcome however I can seem to do the math. I know that total
permutations = c(n + k-1, k-1) = c(15 + 3 -1, 3-1) = c(17,2) = (17 *
16)/2! = 136.
Please can someone explain how to solve this.
|
Here's one way.
First look at a simpler problem: r + s = n. Can you see that, given n,
there are n - 1 solutions in positive integers? Good.
Now x_1 is 1, 2, 3, 4, 5, or 6.
If it's 1, then you're left with x_2 + x_3 = 14. But that's exactly
the kind of problem you know how to do.
If x_1 = 2, then x_2 + x_3 = 13. You can do this one, too. In fact,
you can do all 6 of the problems resulting from the 6 different
possibilities for x_1. So, at the end, you have 6 numbers to add up.
--
Gerry Myerson (gerry@maths.mq.edi.ai) (i -> u for email) |
|
| Back to top |
|
|
Abstract Dissonance
science forum Guru Wannabe
Joined: 29 Dec 2005
Posts: 201
|
| Posted: Thu May 18, 2006 7:43 am Post subject:
Re: Help with permutations
|
|
|
<MatthewGKerr@gmail.com> wrote in message
news:1147915384.637904.217010@38g2000cwa.googlegroups.com...
| Quote: | Son asked me to explain, but knowledge limited regarding permutations.
x1 + x2 + x3 = 15, how many permutions are there when 0< x1 <= 6;
Manually doing the process reveals 75 combinations to produce the
required outcome however I can seem to do the math. I know that total
permutations = c(n + k-1, k-1) = c(15 + 3 -1, 3-1) = c(17,2) = (17 *
16)/2! = 136.
Please can someone explain how to solve this.
|
An easy way to think about this is to know that sum(x_i) = n is a
partitioning of adding a bunch of ones... i.e., any integer sum is canonical
to
sum(1,i=1..n) = 1 + 1 + 1 + ..... + 1 + 1 + 1 = n
so if we are trying to find how to add up 3 integers then we are just trying
to find all the possible ways to group them into three "bins".
say we are trying to find a + b = 5
we have
1 + 1 + 1 + 1 + 1 = 5
we could group as
(1) + (1 + 1 + 1 + 1) = 1 + 4
(1 + 1) + (1 + 1 + 1) = 2 + 3
(1 + 1 + 1) + (1 + 1) = 3 + 2
(1 + 1 + 1 + 1) + (1) = 4 + 1
Which implies there are 4 ways
adding in another variable complicates things slightly because when we take
away 1 from the first we can give it to the other two in two ways. This
should make you think that there exists some combinatorial like answer.
The best way to see it is simple to figure out how many ways there are to
"group" consecutive 1's similar to what I said above.
xxx....xxx
how many ways can we stick m bars '|' between the n 'x'?
well, there are exactly n - 1 choose m - 1 because this is just a standard
partitioning problem.
If you have a constraint on some of the variables then you need to find an
elegant want to state the constrant so it falls within the parameters of
this basic formula or find another formula that is more specific to the
problem. For your 0 < x1 <= 6 you must realize that in effect what we are
doing is solving
x1 + x2 + x3 = 15 but really
x2 + x3 = 14
x2 + x3 = 13
x2 + x3 = 12
x2 + x3 = 11
x2 + x3 = 10
x2 + x3 = 9
or
8 < a + b < 15
I'll leave the rest of the work up to you.
Jon |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Thu Jan 08, 2009 10:21 pm | All times are GMT
|
|
Mortgages | Credit Card Shop | Loans | Bankruptcy | Free Advertising
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
