SmeltQuake
New member
- Joined
- Oct 22, 2014
- Messages
- 2
Hello, community!
STAHP! See the Edit Field below this explanation for a simplified version of the problem.
This question has some references to programming and not as many mathematical terms as you might like, but I think it's more appropriate in a mathematics forum.
Introduction:
I think everyone universally agrees that there are are n! permutations of a list of n numbers.
Assume we want one of the places in the permutations to only have certain values. Here's an example:
n=3 ; [1,2,3]; The permutation may not begin with a 2.
We now list all possible permutations.
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]
When we apply the rule, we have
[1,2,3],[1,3,2],[3,1,2],[3,2,1]
so instead of six, we have four possibilities. This can be generally expressed as (n-1)(n!/n) or just (n-1)(n-1)! for a list of n numbers in which any one place has a forbidden number.
Introduction (continuing):
Now assume I want all permutations of r length from a list of n numbers. Example:
n=4 ; [1,2,3,4] ; r=2
[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]
so as a result, we have 12 lists. Universally expressed: n!/(n-r)!
This can be found on wikipedia (http://en.wikipedia.org/wiki/Permutation#k-permutations_of_n).
Now for the real problem. What number of permutations of r length over n values are there when every place in the permutation has a list of forbidden values?
Let me get you another example.
n=5 ; [1,2,3,4,5] ; r=3 ; The permutations may not begin with a 1 or a 2, the second place may not be a 2, the third may not be a 2 or a 3.
First generate all permutations of 3 length over [1,2,3,4,5]. We get
[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 2), (1, 3, 4), (1, 3, 5), (1, 4, 2), (1, 4, 3), (1, 4, 5), (1, 5, 2), (1, 5, 3), (1, 5, 4), (2, 1, 3), (2, 1, 4), (2, 1, 5), (2, 3, 1), (2, 3, 4), (2, 3, 5), (2, 4, 1), (2, 4, 3), (2, 4, 5), (2, 5, 1), (2, 5, 3), (2, 5, 4), (3, 1, 2), (3, 1, 4), (3, 1, 5), (3, 2, 1), (3, 2, 4), (3, 2, 5), (3, 4, 1), (3, 4, 2), (3, 4, 5), (3, 5, 1), (3, 5, 2), (3, 5, 4), (4, 1, 2), (4, 1, 3), (4, 1, 5), (4, 2, 1), (4, 2, 3), (4, 2, 5), (4, 3, 1), (4, 3, 2), (4, 3, 5), (4, 5, 1), (4, 5, 2), (4, 5, 3), (5, 1, 2), (5, 1, 3), (5, 1, 4), (5, 2, 1), (5, 2, 3), (5, 2, 4), (5, 3, 1), (5, 3, 2), (5, 3, 4), (5, 4, 1), (5, 4, 2), (5, 4, 3)]
We have 60 possible answers. Now apply the first rule. Rule out all possibilities that start with 1 or 2. We get
[(3, 1, 2), (3, 1, 4), (3, 1, 5), (3, 2, 1), (3, 2, 4), (3, 2, 5), (3, 4, 1), (3, 4, 2), (3, 4, 5), (3, 5, 1), (3, 5, 2), (3, 5, 4), (4, 1, 2), (4, 1, 3), (4, 1, 5), (4, 2, 1), (4, 2, 3), (4, 2, 5), (4, 3, 1), (4, 3, 2), (4, 3, 5), (4, 5, 1), (4, 5, 2), (4, 5, 3), (5, 1, 2), (5, 1, 3), (5, 1, 4), (5, 2, 1), (5, 2, 3), (5, 2, 4), (5, 3, 1), (5, 3, 2), (5, 3, 4), (5, 4, 1), (5, 4, 2), (5, 4, 3)]
, so 36 possibilities. Applying the second rule (the second place may not be a two), we get
[(3, 1, 2), (3, 1, 4), (3, 1, 5), (3, 4, 1), (3, 4, 2), (3, 4, 5), (3, 5, 1), (3, 5, 2), (3, 5, 4), (4, 1, 2), (4, 1, 3), (4, 1, 5), (4, 2, 1), (4, 3, 1), (4, 3, 2), (4, 3, 5), (4, 5, 1), (4, 5, 2), (4, 5, 3), (5, 1, 2), (5, 1, 3), (5, 1, 4), (5, 3, 1), (5, 3, 2), (5, 3, 4), (5, 4, 1), (5, 4, 2), (5, 4, 3)]
...28 answers. With the third and final rule (the third place may not be a 2 or a 3), we get the final answer of
[(3, 1, 4), (3, 1, 5), (3, 4, 1), (3, 4, 5), (3, 5, 1), (3, 5, 4),(4, 1, 5), (4, 2, 1), (4, 3, 1), (4, 3, 5), (4, 5, 1), (5, 1, 4), (5, 3, 1), (5, 3, 4), (5, 4, 1)]
...15 permutations of r length over 5 values with the three rules applied.
It might be worth mentioning that a place can also have zero forbidden values, meaning it can be any value.
Now I would love to know how I can get to this number manually without the previous steps of generating all permutations and then applying the rules. I'm writing a program that deals with lists of r length over 9 values, with an unknown number of forbidden values for each place, and I do this in quite a big loop. So I don't want the computer generating all permutations every time it goes into the loop. A simple mathematical statement would be awesome. If anyone has the wits, I'd be absolutely thrilled if I got a pythonic answer. But really, a normal mathematical statement is enough (as long as you at least partly explain it), I'll be happy to convert it into code. Even a hint to keep me motivated is greatly appreciated. After hours of brain-teasing I've kind of given up on this.
Please do let me know if anything is unclear or if I made a mistake somewhere.
Many thanks in advance.
EDIT: Through the help of Doug Chatham on Stack Exchange I now know this problem is equivalent to the problem of placing r mutually non-attacking rooks (i.e., no two on the same row or column) on a n*r board with some of the squares forbidden. (See rook polynomial on wikipedia: http://en.wikipedia.org/wiki/Rook_polynomial), yet after digging my way through the wiki article, I'm more confused than before. As far as I get it, you have to figure out how many possibilities there are to arrange r non-attacking rooks on an r*n chess board. But how do I do this?
STAHP! See the Edit Field below this explanation for a simplified version of the problem.
This question has some references to programming and not as many mathematical terms as you might like, but I think it's more appropriate in a mathematics forum.
Introduction:
I think everyone universally agrees that there are are n! permutations of a list of n numbers.
Assume we want one of the places in the permutations to only have certain values. Here's an example:
n=3 ; [1,2,3]; The permutation may not begin with a 2.
We now list all possible permutations.
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]
When we apply the rule, we have
[1,2,3],[1,3,2],[3,1,2],[3,2,1]
so instead of six, we have four possibilities. This can be generally expressed as (n-1)(n!/n) or just (n-1)(n-1)! for a list of n numbers in which any one place has a forbidden number.
Introduction (continuing):
Now assume I want all permutations of r length from a list of n numbers. Example:
n=4 ; [1,2,3,4] ; r=2
[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]
so as a result, we have 12 lists. Universally expressed: n!/(n-r)!
This can be found on wikipedia (http://en.wikipedia.org/wiki/Permutation#k-permutations_of_n).
Now for the real problem. What number of permutations of r length over n values are there when every place in the permutation has a list of forbidden values?
Let me get you another example.
n=5 ; [1,2,3,4,5] ; r=3 ; The permutations may not begin with a 1 or a 2, the second place may not be a 2, the third may not be a 2 or a 3.
First generate all permutations of 3 length over [1,2,3,4,5]. We get
[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 2), (1, 3, 4), (1, 3, 5), (1, 4, 2), (1, 4, 3), (1, 4, 5), (1, 5, 2), (1, 5, 3), (1, 5, 4), (2, 1, 3), (2, 1, 4), (2, 1, 5), (2, 3, 1), (2, 3, 4), (2, 3, 5), (2, 4, 1), (2, 4, 3), (2, 4, 5), (2, 5, 1), (2, 5, 3), (2, 5, 4), (3, 1, 2), (3, 1, 4), (3, 1, 5), (3, 2, 1), (3, 2, 4), (3, 2, 5), (3, 4, 1), (3, 4, 2), (3, 4, 5), (3, 5, 1), (3, 5, 2), (3, 5, 4), (4, 1, 2), (4, 1, 3), (4, 1, 5), (4, 2, 1), (4, 2, 3), (4, 2, 5), (4, 3, 1), (4, 3, 2), (4, 3, 5), (4, 5, 1), (4, 5, 2), (4, 5, 3), (5, 1, 2), (5, 1, 3), (5, 1, 4), (5, 2, 1), (5, 2, 3), (5, 2, 4), (5, 3, 1), (5, 3, 2), (5, 3, 4), (5, 4, 1), (5, 4, 2), (5, 4, 3)]
We have 60 possible answers. Now apply the first rule. Rule out all possibilities that start with 1 or 2. We get
[(3, 1, 2), (3, 1, 4), (3, 1, 5), (3, 2, 1), (3, 2, 4), (3, 2, 5), (3, 4, 1), (3, 4, 2), (3, 4, 5), (3, 5, 1), (3, 5, 2), (3, 5, 4), (4, 1, 2), (4, 1, 3), (4, 1, 5), (4, 2, 1), (4, 2, 3), (4, 2, 5), (4, 3, 1), (4, 3, 2), (4, 3, 5), (4, 5, 1), (4, 5, 2), (4, 5, 3), (5, 1, 2), (5, 1, 3), (5, 1, 4), (5, 2, 1), (5, 2, 3), (5, 2, 4), (5, 3, 1), (5, 3, 2), (5, 3, 4), (5, 4, 1), (5, 4, 2), (5, 4, 3)]
, so 36 possibilities. Applying the second rule (the second place may not be a two), we get
[(3, 1, 2), (3, 1, 4), (3, 1, 5), (3, 4, 1), (3, 4, 2), (3, 4, 5), (3, 5, 1), (3, 5, 2), (3, 5, 4), (4, 1, 2), (4, 1, 3), (4, 1, 5), (4, 2, 1), (4, 3, 1), (4, 3, 2), (4, 3, 5), (4, 5, 1), (4, 5, 2), (4, 5, 3), (5, 1, 2), (5, 1, 3), (5, 1, 4), (5, 3, 1), (5, 3, 2), (5, 3, 4), (5, 4, 1), (5, 4, 2), (5, 4, 3)]
...28 answers. With the third and final rule (the third place may not be a 2 or a 3), we get the final answer of
[(3, 1, 4), (3, 1, 5), (3, 4, 1), (3, 4, 5), (3, 5, 1), (3, 5, 4),(4, 1, 5), (4, 2, 1), (4, 3, 1), (4, 3, 5), (4, 5, 1), (5, 1, 4), (5, 3, 1), (5, 3, 4), (5, 4, 1)]
...15 permutations of r length over 5 values with the three rules applied.
It might be worth mentioning that a place can also have zero forbidden values, meaning it can be any value.
Now I would love to know how I can get to this number manually without the previous steps of generating all permutations and then applying the rules. I'm writing a program that deals with lists of r length over 9 values, with an unknown number of forbidden values for each place, and I do this in quite a big loop. So I don't want the computer generating all permutations every time it goes into the loop. A simple mathematical statement would be awesome. If anyone has the wits, I'd be absolutely thrilled if I got a pythonic answer. But really, a normal mathematical statement is enough (as long as you at least partly explain it), I'll be happy to convert it into code. Even a hint to keep me motivated is greatly appreciated. After hours of brain-teasing I've kind of given up on this.
Please do let me know if anything is unclear or if I made a mistake somewhere.
Many thanks in advance.
EDIT: Through the help of Doug Chatham on Stack Exchange I now know this problem is equivalent to the problem of placing r mutually non-attacking rooks (i.e., no two on the same row or column) on a n*r board with some of the squares forbidden. (See rook polynomial on wikipedia: http://en.wikipedia.org/wiki/Rook_polynomial), yet after digging my way through the wiki article, I'm more confused than before. As far as I get it, you have to figure out how many possibilities there are to arrange r non-attacking rooks on an r*n chess board. But how do I do this?
Last edited: