Relazioni di equivalenza
Buongiorno,
sottopongo alla vostra attenzione questa tipologia di esercizi.
Come lo risolvereste?
Calcolare il numero di relazioni di equivalenza $ ∼ $ nell’insieme $ {1, 2, 3, 4, 5, 6, 7, 8, 9} $ soddisfacenti
a tutte le condizioni seguenti:
(a) $ 1 ∼ 2, 2 ∼ 4, 3 ∼ 7; $
(b) tutte le classi di equivalenza hanno al più cinque elementi.
sottopongo alla vostra attenzione questa tipologia di esercizi.
Come lo risolvereste?
Calcolare il numero di relazioni di equivalenza $ ∼ $ nell’insieme $ {1, 2, 3, 4, 5, 6, 7, 8, 9} $ soddisfacenti
a tutte le condizioni seguenti:
(a) $ 1 ∼ 2, 2 ∼ 4, 3 ∼ 7; $
(b) tutte le classi di equivalenza hanno al più cinque elementi.
Risposte
le relazioni di equivalenza che soddisfano (a) corrispondono alle
partizioni dell'insieme quoziente $A$ dato da $\{1,2,3,4,5,6,7,8,9\}$ con identificazione
$1=2=4$ e $3=7$. L'insieme $A$ ha sei elementi e il numero di partizioni di $A$ e' quindi il
numero di Bell $B_6 =203$ (si veda http://en.wikipedia.org/wiki/Partition_of_a_set).
Questo e' anche il numero di relazioni di equivalenza che soddisfano (a).
Se vogliamo anche tener conto della condizione (b), dobbiamo buttar via le partizioni di
$\{1,2,3,4,5,6,7,8,9\}$ corrispondenti alle relazioni di equivalenza del tipo (a)
che contengono una parte di $\ge 6$ elementi.
Poiche' l'insieme ha 9 elementi, soltanto una unica parte $P$ puo' avere $\ge 6$ elementi.
Poi, abbiamo per forza $1,2,4\in P$ oppure $3,7\in P$. Ci sono tre possibilita':
1) $3,7\in P$ ma non $1,2,4\in P$. In questo caso abbiamo per forza $5,6,8,9\in P$.
Si tratta quindi di una unica partizione, vale a dire $P=\{3,7,5,6,8,9\}$ e $\{1,2,4\}$.
2) $1,2,4\in P$ ma non $3,7\in P$. In questo caso almeno tre degli elementi $5,6,8,9$
appartengono a $P$. Ci sono due casi: se tutti i quattro appartengono a $P$
abbiamo la partizione $P$, $\{3,7\}$. Nell'altro caso solo tre elementi di $\{5,6,8,9\}$
appartengono a $P$. Ci sono quattro possibilita' e ogni volta ci sono $B_2=2$
partizioni. Per esempio, se $5,6,8\in P$, ma $9\not\in P$, allora ci sono
le partizioni $P$, $\{3,7\}$, $\{9\}$ e $P$, $\{3,7,9\}$.
In totale si tratta quindi di $1 + 4*2 = 9$ partizioni.
3) $1,2,4,3,7\in P$. Per forza almeno uno elemento di $5,6,8,9$ sta anche in $P$.
Distinghiamo quattro casi:
1 elemento in $P$: 4 scelte e per ogni scelta ci sono $B_3 = 5$ partizioni: $4*5 = 20$.
2 elementi in $P$: 6 scelte e per ogni scelta ci sono $B_2 = 2$ partizioni: $6*2 = 12$.
3 elementi in $P$: 4 scelte e per ogni scelta ci sono $B_1 = 1$ partizioni: $4*1 = 4$.
4 elementi in $P$: la relazione di equivalenza banale: una partizione: = $1$.
Totale = $37$
Contando le partizioni nei casi 1), 2) e 3), trovo che il numero di relazioni di
equivalenza che non soddisfano (b) = $1 + 9 + 37 = 47$.
Il numero cercato = $203 - 47 = 156$.... Speriamo bene.
partizioni dell'insieme quoziente $A$ dato da $\{1,2,3,4,5,6,7,8,9\}$ con identificazione
$1=2=4$ e $3=7$. L'insieme $A$ ha sei elementi e il numero di partizioni di $A$ e' quindi il
numero di Bell $B_6 =203$ (si veda http://en.wikipedia.org/wiki/Partition_of_a_set).
Questo e' anche il numero di relazioni di equivalenza che soddisfano (a).
Se vogliamo anche tener conto della condizione (b), dobbiamo buttar via le partizioni di
$\{1,2,3,4,5,6,7,8,9\}$ corrispondenti alle relazioni di equivalenza del tipo (a)
che contengono una parte di $\ge 6$ elementi.
Poiche' l'insieme ha 9 elementi, soltanto una unica parte $P$ puo' avere $\ge 6$ elementi.
Poi, abbiamo per forza $1,2,4\in P$ oppure $3,7\in P$. Ci sono tre possibilita':
1) $3,7\in P$ ma non $1,2,4\in P$. In questo caso abbiamo per forza $5,6,8,9\in P$.
Si tratta quindi di una unica partizione, vale a dire $P=\{3,7,5,6,8,9\}$ e $\{1,2,4\}$.
2) $1,2,4\in P$ ma non $3,7\in P$. In questo caso almeno tre degli elementi $5,6,8,9$
appartengono a $P$. Ci sono due casi: se tutti i quattro appartengono a $P$
abbiamo la partizione $P$, $\{3,7\}$. Nell'altro caso solo tre elementi di $\{5,6,8,9\}$
appartengono a $P$. Ci sono quattro possibilita' e ogni volta ci sono $B_2=2$
partizioni. Per esempio, se $5,6,8\in P$, ma $9\not\in P$, allora ci sono
le partizioni $P$, $\{3,7\}$, $\{9\}$ e $P$, $\{3,7,9\}$.
In totale si tratta quindi di $1 + 4*2 = 9$ partizioni.
3) $1,2,4,3,7\in P$. Per forza almeno uno elemento di $5,6,8,9$ sta anche in $P$.
Distinghiamo quattro casi:
1 elemento in $P$: 4 scelte e per ogni scelta ci sono $B_3 = 5$ partizioni: $4*5 = 20$.
2 elementi in $P$: 6 scelte e per ogni scelta ci sono $B_2 = 2$ partizioni: $6*2 = 12$.
3 elementi in $P$: 4 scelte e per ogni scelta ci sono $B_1 = 1$ partizioni: $4*1 = 4$.
4 elementi in $P$: la relazione di equivalenza banale: una partizione: = $1$.
Totale = $37$
Contando le partizioni nei casi 1), 2) e 3), trovo che il numero di relazioni di
equivalenza che non soddisfano (b) = $1 + 9 + 37 = 47$.
Il numero cercato = $203 - 47 = 156$.... Speriamo bene.
Mi aggancio a questa discussione visto che ho un esercizio analogo.
Viene chiesto di calcolare il numero di relazioni di equivalenza $\tilde$ nell'insieme ${1,2,3,4,5,6,7,8,9}$ soddisfacenti le condizioni:
a) $1 (tilde) 2, 2 (tilde) 4, 3 (tilde) 5$
b) tutte le classi hanno tre elementi
Quindi io ottengo una cosa così (volendo una rappresentazione grafica):
${1, 2, 4} {3, 5, .} {., ., .}$
Ma mi trovo in difficoltà a dire se il numero di relazioni è $4$, oppure $36$
Viene chiesto di calcolare il numero di relazioni di equivalenza $\tilde$ nell'insieme ${1,2,3,4,5,6,7,8,9}$ soddisfacenti le condizioni:
a) $1 (tilde) 2, 2 (tilde) 4, 3 (tilde) 5$
b) tutte le classi hanno tre elementi
Quindi io ottengo una cosa così (volendo una rappresentazione grafica):
${1, 2, 4} {3, 5, .} {., ., .}$
Ma mi trovo in difficoltà a dire se il numero di relazioni è $4$, oppure $36$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo