number of possible combinations in a partitioning

Question

Given is a set S of size n, which is partitioned into classes (s1,..,sk) of sizes n1,..,nk. Naturally, it holds that n = n1+...+nk.

I am interested in finding out the number of ways in which I can combine elements of this partitioning so that each combination contains exactly one element of each class.

Since I can choose n1 elements from s1, n2 elements from s2 and so on, I am looking for the solution to max(n1*..*nk) for arbitrary n1,..nk for which it holds that n1+..+nk=n.

I have the feeling that this is a linear-optimization problem, but it's been too long since I learned this stuff as an undergrad. I hope that somebody remembers how to compute this.

Answer 1

floor(n/k)^(k - n mod k)*ceil(n/k)^(n mod k)

-- MarkusQ

P.S. For the example you gave of S = {1,2,3,4}, n = 4, k = 2 this gives:

floor(4/2)^(2 - 4 mod 2)*ceil(4/2)^(4 mod 2)
floor(2)^(2 - 0)*ceil(2)^(0)
2^2 * 2^0
4 * 1
4

...as you wanted.

To clarify, this formula gives the number of permutations generated by the partitioning with the maximum possible number of permutations. There will of course be other, less optimal partitionings.

For a given perimeter the rectangle with the largest area is the one that is closest to a square (and the same is true in higher dimensions) which means you want the sides to be as close to equal in length as possible (e.g. all either the average length rounded up or down). The formula can then be seen to be:

   (length of short sides)^(number of short sides)
times
   (length of long sides)^(number of long sides)

which is just the volume of the hyper-rectangle meeting this constraint.

Note that, when viewed this way, it also tells you how to construct a maximal partitioning.

Answer 2

You're looking for the number of combinations with one element from each partition?

That's simply n1*n2*...*nk.

Edit: You seem to also be asking a separate question:

Given N, how do I assign n1, n2, ..., nk such that their product is maximized. This is not actually a linear optimization problem, since your variables are multiplied together.

It can be solved by some calculus, i.e. by taking partial dervatives in each of the variables, with the constraint, using Lagrange multipliers.

The result will be that the n1 .. nk should be as close to the same size as possible.

if n is a multiple of k, then n_1 = n_2 = ... = n_k = n/k

otherwise, n_1 = n_2 = ... = n_j = Ceiling[n/k]
      and  n_j+1 = ... = n_k = floor[n/k]

Basically, we try to distribute the elements as evenly as possible into partitions. If they divide evenly, great. If not, we divide as evenly as possible, and with whatever is left over, we give an extra element each to the first partitions. (Doesn't have to be the first partitions, that choice is fairly arbitrary.) In this way, the difference in the number of elements owned by any two partitions will be at most one.

Gory Details:

This is the product function which we wish to maximize:

P = n1*n2*...nK

We define a new function using Lagrange multipliers:

Lambda = P + l(N - n1 - n2 ... -nk)

And take Partial derivatives in each of the k n_i variables:

dLambda/dn_i = P/n_i - l

and in l:

dLambda/dl = N - n1 -n2 ... -nk

setting all of the partial derivatives = 0, we get a system of k + 1 equations, and when we solve them, we'll get that n1 = n2 = ... = nk

Some useful links:

Lagrange Multipliers

Optimization