I already asked this question in the mathoverflow forums, but it seems I won't get an answer as fast as I need one. So I'm moving the thread here. Besides, maybe it isn't as hard as to post it there.
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 (Skip if you are familiar with k-permutations and permutations with one forbidden number):
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 here or just look at the comment of Matt right under this question.
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.
