Anzahl der möglichen Kombinationen in einer Partitionierung

Question

Gegeben ist eine Menge S der Größe n, die in Klassen (s1, .., sk) der Größen n1, .., nk unterteilt ist. Natürlich gilt n = n1 + ... + nk.

Ich interessiere mich für die Anzahl der Möglichkeiten, wie ich Elemente dieser Partitionierung kombinieren kann, so dass jede Kombination genau ein Element jeder Klasse enthält.

Da ich n1 Elemente von s1, n2 Elemente von s2 und so weiter wählen kann, suche ich nach der Lösung zu max (n1 * .. * nk) für beliebige n1, .. nk, für die es das n1 + hält .. + nk = n.

Ich habe das Gefühl, dass dies ein Problem der linearen Optimierung ist, aber es ist zu lange her, dass ich dieses Zeug als Anfänger gelernt habe. Ich hoffe, dass sich jemand daran erinnert, wie man das berechnet.

Answer 1

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

- MarkusQ

P. S. Für das Beispiel gab man von S = {1,2,3,4}, n = 4, k = 2 ergibt dies:

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 

... wie man wollte.

Um dies klarzustellen, gibt diese Formel die Anzahl der Permutationen an, die durch die Partitionierung mit der maximal möglichen Anzahl von Permutationen erzeugt werden. Es wird natürlich andere, weniger optimale Partitionierungen geben.

Für ein gegebenes Perimeter ist das Rechteck mit der größten Fläche dasjenige, das einem Quadrat am nächsten kommt (und dasselbe gilt für höhere Dimensionen), dh die Seiten sollten möglichst gleich lang sein (zB alle entweder die durchschnittliche Länge auf- oder abgerundet). Die Formel kann dann wie folgt aussehen:

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

Dies ist nur das Volumen des Hyper-Rechtecks, das diese Einschränkung erfüllt.

Beachten Sie, dass, wenn Sie auf diese Weise angezeigt werden, Sie auch erfahren, wie Sie eine maximale Partitionierung erstellen.

Answer 2

Sie suchen nach der Anzahl der Kombinationen mit einem Element aus jeder Partition?

Das ist einfach n1 * n2 * ... * nk.

Edit: Sie scheinen auch eine separate Frage stellen werden:

Gegeben N, wie ordne ich n1, n2, ..., nk, so dass ihr Produkt maximiert wird. Dies ist kein lineares Optimierungsproblem, da Ihre Variablen miteinander multipliziert werden.

Es kann durch einen Kalkül gelöst werden, d. H. Indem partielle Dervative in jeder der Variablen mit der Einschränkung unter Verwendung von Lagrange-Multiplikatoren vorgenommen werden.

Das Ergebnis wird sein, dass der n1 .. nk so nah wie möglich an der gleichen Größe sein sollte.

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] 

Grundsätzlich versuchen wir die Elemente so gleichmäßig wie möglich in Partitionen zu verteilen. Wenn sie sich gleichmäßig teilen, großartig. Wenn nicht, teilen wir uns so gleichmäßig wie möglich, und mit allem, was übrig bleibt, geben wir den ersten Partitionen jeweils ein zusätzliches Element. (Es müssen nicht die ersten Partitionen sein, diese Wahl ist ziemlich willkürlich.) Auf diese Weise wird der Unterschied in der Anzahl der Elemente, die zwei Partitionen gehören, höchstens eins betragen.

Gory Einzelheiten:

Dies ist die Produktfunktion, die wir maximieren wollen:

P = n1 * n2 * ... nK

Wir definieren eine neue Funktion mit Lagrange-Multiplikatoren :

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

Und Partielle Ableitungen nehmen in jede der k n_i Variablen:

dLambda/dn_i = P/n_i - l

und in l:

dLambda/dl = N - N1 -N2 ... -NK

Setzen wir alle partiellen Ableitungen = 0, erhalten wir ein System von k + 1 Gleichungen, und wenn wir sie lösen, erhalten wir, dass n1 = n2 = ...= Nk

einige nützliche Links:

Lagrange Multipliers

Optimization