(I'm trying to post this again testing different
methods of mail posting. My aplogies if it
appears twice...)
Roiem found a major flaw in my latest f(n):
f(n) = 1 - (n * ((n-1)!/n!)^x)
Which is wrong (as he states) for two reasons...
>> 1. You added an additional factor of n, but
>> since you want to not choose ANY particular
>> item (your words, not mine), you need a
>> factor of n! (because "ANY particular item"
>> refers to the permutations, not the letters.
>> 2. If you add the factor of n!, you'll be
>> counting those options in which you didn't
>> choose more than one permutation, multiple
>> times.
>> Let's try looking at this a different way:
>> We are going to pick a random element out
>> of m (here, "element"="permutation" and m=n!),
>> x times, and we want all of them to be there.
>> The number of ways to do this is g(m,x) = m^x
>> - Sum[1<=i<m]C(m,i)g(i,x)
>> C(m,k) is the number of combinations of k from
>> m, "m choose k", which is m!/((m-k)!k!)
>> From m^x we subtract the number of ways to
>> choose m-1, times m (i.e., the number of ways
>> to miss exactly one specific element, times the
>> number of possible elements we can miss), then
>> the number of ways to choose m-2, times C(m,2)
>> (the number of ways to miss two elements, times
>> the number of pairs of elements we can miss),
>> and so on. Now, we get f(n,x) = g(n!,x)/(n!^x).
All of this promted me to write the code below
which accepts two arguments, the first being the
number of items (n), and the second being the
number of selections (x).
The output is the probability that we will select
all permutations of n items with x random
selections.
(Please note that running time increasing
dramatically as n increases, making the code only
practical for n <= 4.)
#!/usr/bin/perl -l
sub f {$_[0]<2?$_[0]:$_[0]*f($_[0]-1)}
sub g {
$_[2]=$_[0]**$_[1];
$_[2]-=(f($_[0])/(f($_[0]-$_)*f($_)))*g($_,$_[1])for 1..$_[0]-1;
$_[2]
}
print g(f($ARGV[0]),$ARGV[1])/f($ARGV[0])**$ARGV[1]
## Riley
## (o0lit3)
