il numero di combinazioni possibili in un partizionamento

Question

Dato un insieme S di dimensione n, che è suddiviso in classi (s1,..,sk) di dimensioni n1,..,nk.Naturalmente, si sostiene che n = n1+...+nk.

Io sono interessato a scoprire il numero di modi in cui posso combinare gli elementi di questo partizionamento in modo che ogni combinazione contiene esattamente un elemento di ciascuna classe.

Dal momento che posso scegliere n1 elementi di s1, n2 elementi da s2 e così via, sto cercando la soluzione al max(n1*..*nk) per arbitrario n1,..nk per il quale si sostiene che n1+..+nk=n.

Ho la sensazione che questo è un lineare-problema di ottimizzazione, ma è stato troppo tempo da quando ho imparato questa roba come un undergrad.Spero che qualcuno si ricorda di come calcolare questo.

Answer 1

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

- MarkusQ

P.S. Per l'esempio che ha dato di S = {1,2,3,4}, n = 4, k = 2 questo dà:

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

... come si voleva.

Per chiarire, questa formula fornisce il numero di permutazioni generati dal partizionamento con il massimo numero possibile di permutazioni. Ci saranno ovviamente altri, paratia per meno ottimali.

Per un determinato perimetro del rettangolo con l'area più grande è quello che è più vicino a un quadrato (e lo stesso vale in dimensioni superiori) che significa che si desidera che i lati siano il più vicino alla parità di lunghezza possibile (es tutti o la lunghezza media arrotondato). La formula può quindi essere visto come:

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

che è solo il volume della riunione iper-rettangolo di questo vincolo.

Si noti che, se visti in questo modo, ti dice anche come costruire un partizionamento massima.

Answer 2

Stai cercando il numero di combinazioni con un elemento per ogni partizione?

Semplicemente n1*n2*...*nk.

Edit:Si sembra anche porre una questione a parte:

Dato N, come faccio ad assegnare n1, n2, ..., nk tale che il loro prodotto è ingrandita.Questo non è in realtà un problema di ottimizzazione lineare, in quanto le variabili sono moltiplicati insieme.

Esso può essere risolto con qualche calcolo, cioèprendendo parziale dervatives in ciascuna delle variabili, con il vincolo, utilizzando i moltiplicatori di Lagrange.

Il risultato sarà che il n1 ..nk dovrebbe essere la stessa dimensione come possibile.

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]

In sostanza, cerchiamo di distribuire gli elementi nel modo più uniforme possibile in partizioni.Se si divide equamente, grande.Se non si divide il più uniformemente possibile, e con tutto ciò che è rimasto, diamo un elemento in più alla prima che le partizioni.(Non deve essere la prima le partizioni, la scelta è abbastanza arbitrario). In questo modo, la differenza nel numero di elementi di proprietà di due partizioni saranno più di una.

Dettagli Scabrosi:

Questa è la funzione del prodotto che si vuole massimizzare:

P = n1*n2*nK...

Possiamo definire una nuova funzione utilizzando i moltiplicatori di Lagrange:

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

E prendere derivate Parziali in ognuna delle k n_i variabili:

dLambda/dn_i = P/n_i - l

e l:

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

l'impostazione di tutte le derivate parziali = 0, otteniamo un sistema di k + 1 equazioni, e quando siamo in grado di risolvere loro, otteniamo che n1 = n2 = ...= nk

Alcuni link utili:

I Moltiplicatori Di Lagrange

Ottimizzazione