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?