Ok here's a question I wonder if any maths boffins can help me with please?
It's to do with set theory/combinatorics.
I think this could come in handy for multiple PE problems.
How do I find out the total number of sets containing up to n in each, containing each of k distinct objects at least once (where k <= n) ?
So for instance, if n=5, k=3
You could have
{1 2 3}
{3 2 1}
{1 1 2 3}
{1 1 1 2 3}
{1 1 1 3 2}
{1 1 2 2 3}
{1 1 3 3 2}
{1 2 2 2 3}
etc
but you couldn't have
{1 1 1 2} (doesn't contain 3)
{3 3 3 3 3} (doesn't contain 1 or 2)
etc.
and the order matters, so {1 2 3} != {3 2 1}
I know it's something like
f(n,k) = k^n - f(n,k, k-1) - f(n,k, k-2) - ... - f(n,k,1)
where f(n,k,m) is the number of sets of n from k where the total number of distinct elements is m.
(so therefore f(n,k) is always equal to f(n,k,k) )
and f(n,n) is always just n factorial, because it's the number of permutations of the distinct set of objects.
because k^n is the total permutations of n sets from 1..k, but then you have to discount all the ones where there are less than k distinct elements, i.e. not all the numbers are represented.
but what's f(n,k,m) ?
I've tried an implementation that says
f(n,k)
{
if(n==k) return n!;
res = k^n;
for(m = k-1; m > 0; m--)
{
res -= f(n,k,m);
}
}
f(n,k,m)
{
if(m == 1) return k;
return k * f(n,k)
}
and that works for any k when n <= 5
and for f(6,1), f(6,2), f(6,3)
but it fails for f(6,4).
It returns f(6,4,2) = 2160 when it should be 372.
any ideas?