Relazioni di equivalenza e partizioni

[Marix]

Come si fa a calcolare quante relazioni di equivalenza si possono definire su un insieme di 4 elementi? E quindi come faccio a contare tutte le possibili partizioni dell'insieme? Non c'è un modo sbrigativo per farlo?
grazie

[adaBTTLS]

il numero di partizioni di un n-insieme si chiama "numero di Bell" e si indica con $B_n$.
le partizioni di un insieme di 4 elementi sono 15.
le partizioni di un n-insieme in k classi sono date dai numeri S(n,k), numeri di Stirling di seconda specie [in questi giorni mi è capitato di citarli un numero impressionante di volte: prova anche con la funzione "cerca"].
sono argomenti di calcolo combinatorio, sono tra le prime cose che si studiano, però non sono argomenti elementari per l'algebra e l'analisi.
puoi cercare con un motore di ricerca numeri di Bell e numeri di Stirling.
se mi fai sapere qualcosa di più, tipo quello che stai studiando e che cosa dovresti dimostrare in particolare, cercherò di indirizzarti meglio. ciao.

[Marix]

Sto studiando elementi di algebra e logica e un esercizio chiede appunto quante relazioni di equivalenza si possono definire su un insieme (a,b,c,d).
Il problema è che nella soluzione di questo esercizio viene fuori che in totale si hanno 29 partizioni. Io smanettando un po' ho trovato questi numeri di bell e di stirling di cui mi hai parlato e come hai detto tu ad un insieme con 4 elementi corrispondono 15 partizioni. Ma non riesco ancora a capire come dalla soluzione dell'esercizio viene fuori il numero 29.

[adaBTTLS]

tu dici che "nella soluzione di questo esercizio viene fuori che in totale si hanno 29 partizioni".
dunque non è un semplice risultato, ma un esercizio svolto?
se è così, postalo come dice il testo, e cercheremo di svelare l'arcano...
ciao.

[Marix]

Non l'ho postata perchè è abbastanza lunghetta, comunque eccola:

Le relazioni di equivalenza distinte sull'insieme $A={a,b,c,d}$ sono tante quante le partizioni di A. Per contarle procediamo così: fissiamo un elemento (si può fare in 4 modi) e consideriamo le partizioni di cui fa parte il sottoinsieme formato da quell'elemento soltanto

$[{a},{b},{c},{d}]$ $[{a},{b,c},{d}]$ $[{a},{b,d},{c}]$ $[{a},{b},{c,d}]$ $[{a},{b,c,d}]$
$[{b},{a},{c},{d}]$ $[{b},{a,c},{d}]$ $[{b},{a,d},{c}]$ $[{b},{a},{c,d}]$ $[{b},{a,c,d}]$
$[{c},{b},{a},{d}]$ $[{c},{b,a},{d}]$ $[{c},{b,d},{a}]$ $[{c},{b},{a,d}]$ $[{c},{b,a,d}]$
$[{d},{b},{c},{a}]$ $[{d},{b,c},{a}]$ $[{d},{b,a},{c}]$ $[{d},{b},{c,a}]$ $[{d},{b,c,a}]$

Fissiamo due elementi (si può fare in $((4),(2))=6$ modi) e consideriamo le partizioni di cui fa parte il sottoinsieme formato da quei due elementi soltanto

$[{a,b},{c},{d}]$ $[{a,b},{c,d}]$
ecc.

Se fissiamo tre elementi e consideriamo le partizioni di cui fa parte il sottoinsieme formato da quei tre elementi soltanto, tali partizioni sono state già conteggiate nel primo caso. Manca solo la partizione il cui unico sottoinsieme è tutto A. In totale abbiamo,

$16+12+1=29$

Ad esempio:
la partizione $[{a},{b},{c},{d}]$ corrisponde alla relazione di uguaglianza su A: xRy se x=y;
la partizione $[{a,b},{c,d}]$ corrisponde alla relazione di equivalenza su A che contiene aRb, cRd,
ecc.



Spero di non aver sbagliato qualcosa.

[adaBTTLS]

mi dispiace, ma questa risposta mi era completamente sfuggita. è ritornata alla luce nello spostare i topic per vuotare la sezione Università.

per quanto io ne sappia, la partizione che lascia i 4 elementi isolati è unica, non c'è differenza tra $|{a}, {b}, {c}, {d}| " e " |{b},{c},{a},{d}|$ ad esempio. io invece partirei proprio da quello che hai detto tu a proposito dei coefficienti binomiali:
$((4),(2))=6$ è il numero di modi di scegliere due dei quattro elementi. se consideri {a,b},{c,d}, le due coppie sono due elementi distinti delle sei scelte. quindi se vogliamo considerare le partizioni distinte non possiamo moltiplicare 6*2, ma casomai 6*3/2, nel senso che per ogni coppia si hanno tre partizioni, o in maniera più semplice abbiamo 6 partizioni del tipo $|{a,b}, {c}, {d}|$, una per ogni scelta, e 3 partizioni del tipo $|{a,b}, {c,d}|$, una ogni due scelte.
inoltre ci sono $((4),(3))=4$ partizioni del tipo $|{a,b,c},{d}|$, ed in più le due banali ($((4),(4))=1, ((4),(0))=1$): $|{a},{b},{c},{d}| " e " |{a,b,c,d}|$.
in totale: $6+3+4+2=15$.

spero sia chiaro. mi dispiace di aver atteso tanto nella risposta. ciao.