1.3 Contare le soluzioni¶
Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 1 · Capitolo 1: Ottimizzazione combinatoria · Dispensa, volume 1 (PDF) · Slide · Esercizi: Ottimizzazione combinatoria · App: Forza bruta sul problema dello zaino 0/1
- Prima di risolvere un problema ci chiediamo quante soluzioni candidate ha. La risposta dipende solo dall'oggetto combinatorio: sottoinsiemi, ordinamenti o partizioni.
1.3.1 Sottoinsiemi¶
Proposizione 1.2
Un insieme con \(n\) elementi ha \(2^n\) sottoinsiemi.
Dimostrazione
Un sottoinsieme \(S \subseteq \{1,2,\dots,n\}\) è identificato dal vettore binario \({\vet{x}} \in \{0,1\}^n\) con \(x_j = 1\) se e solo se \(j \in S\). Ognuna delle \(n\) componenti assume \(2\) valori in modo indipendente, quindi i vettori sono \(2 \cdot 2 \cdots 2 = 2^n\). Equivalentemente, il numero di sottoinsiemi con \(k\) elementi è \(\binom{n}{k}\), e abbiamo:
□
-
Geometricamente, i \(2^n\) vettori binari sono i vertici dell'ipercubo unitario \([0,1]^n\): il quadrato per \(n=2\) (\(4\) vertici) e il cubo per \(n=3\) (\(8\) vertici).
-
Ogni decisione IN/OUT su \(n\) elementi è un sottoinsieme: i \(2^n\) sottoinsiemi sono le sue soluzioni candidate.
1.3.2 Ordinamenti e ordinamenti ciclici¶
-
Gli \(n\) elementi di un insieme si possono ordinare in \(n! = n \cdot (n-1) \cdots 2 \cdot 1\) modi (permutazioni).
-
Un ordinamento ciclico dispone gli \(n\) elementi lungo un cerchio, come in un giro attraverso \(n\) luoghi: l'elemento di partenza e il verso di percorrenza non contano.
Proposizione 1.3
Per \(n \ge 3\) elementi, il numero di ordinamenti ciclici distinti, dove una sequenza, le sue rotazioni e la sua inversa sono lo stesso ordinamento ciclico, è
Dimostrazione
Poiché l'elemento di partenza non cambia un ordinamento ciclico, possiamo partire sempre dall'elemento \(1\): i restanti \(n-1\) elementi si possono ordinare in \((n-1)!\) modi. Ogni ordinamento ciclico si ottiene due volte, una per ogni verso, per esempio \((1,3,5,2,4)\) e \((1,4,2,5,3)\). Quindi il numero di ordinamenti ciclici distinti è \((n-1)!/2\). □
- Per \(n=4\) ci sono \(3!/2 = 3\) ordinamenti ciclici: \((1,2,3,4)\), \((1,2,4,3)\) e \((1,3,2,4)\). Ogni altra sequenza è una rotazione o un'inversa di uno di essi, per esempio \((2,1,4,3)\) è l'inversa di \((1,2,3,4)\) fatta partire dall'elemento \(2\).
1.3.3 Partizioni e numeri di Bell¶
-
Una partizione di un insieme finito \(A\) è una collezione di sottoinsiemi non vuoti e a due a due disgiunti di \(A\) la cui unione è \(A\). Le decisioni di raggruppamento, come la suddivisione di oggetti in gruppi, hanno partizioni come soluzioni.
-
Il numero di partizioni di un insieme con \(n\) elementi è il numero di Bell \(B(n)\), definito dalla ricorsione:
\[\begin{equation*} \label{eq:oc1-bell} B(0) = 1, \qquad B(n) = \sum_{k=0}^{n-1} \binom{n-1}{k} \, B(k), \quad \forall n \ge 1 . \tag{1.1} \end{equation*}\]La ricorsione conta le partizioni in base al blocco che contiene l'elemento \(n\): se questo blocco ha altri \(n-1-k\) elementi, essi si possono scegliere in \(\binom{n-1}{n-1-k}=\binom{n-1}{k}\) modi, e i restanti \(k\) elementi si partizionano in \(B(k)\) modi.
-
I primi numeri di Bell sono:
\[ \begin{array}{c|ccccccccccc} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline B(n) & 1 & 1 & 2 & 5 & 15 & 52 & 203 & 877 & 4140 & 21147 & 115975 \end{array} \] -
Un assegnamento di \(n\) elementi a \(m\) etichette è una funzione dagli elementi alle etichette: ce ne sono \(m^n\). Se le etichette sono intercambiabili (risorse identiche), due assegnamenti che differiscono solo per una ridenominazione delle etichette sono la stessa soluzione; le soluzioni distinte sono le partizioni degli elementi in al più \(m\) blocchi.
Esempio 1.2: quante soluzioni candidate
Per un insieme con \(n=5\) elementi, i numeri dei quattro oggetti combinatori sono:
| oggetto combinatorio | numero |
|---|---|
| sottoinsiemi | \(2^5 = 32\) |
| ordinamenti (permutazioni) | \(5! = 120\) |
| ordinamenti ciclici | \(4!/2 = 12\) |
| partizioni | \(B(5) = 52\) |
| assegnamenti a \(3\) etichette | \(3^5 = 243\) |
| partizioni in al più \(3\) blocchi | \(1+15+25 = 41\) |
L'ultima riga conta le partizioni di \(5\) elementi in \(1\), \(2\) o \(3\) blocchi (rispettivamente \(1\), \(15\) e \(25\)); le altre \(10+1\) partizioni delle \(52\) hanno \(4\) o \(5\) blocchi.
- Questi numeri contano le soluzioni candidate. Quelle ammissibili possono essere molte meno: nell'Esempio 1.1 solo \(11\) dei \(16\) sottoinsiemi sono ammissibili.