Contare le relazioni di equivalenza su un insieme
\(\Box\) Problema di base: quante relazioni di equivalenza esistono in un insieme di cinque elementi?
Essendo cinque un numero relativamente piccolo, possiamo fare tutto esplicitamente contando le possibili partizioni. Innanzitutto, c'è \(1\) modo per prendere tutti gli elementi e \(1\) per prendere solo singoletti. Poi ci sono esattamente \(5\) modi per partizionare l'insieme in un singoletto contro quattro elementi. Dopodiché, posso suddividere l'insieme in due coppie e un singoletto; ho \(5\) modi per scegliere il singoletto, più \(3\) modi per formare le coppie, quindi \(15\) modi in totale. Un insieme di due elementi contro uno di tre, dà \(\binom{5}{3}=10\). Due singoletti contro una terzina, dà ancora \(10\). Infine, con tre singoletti e una coppia, la scelta della coppia fissa i singoletti rimanenti, per un totale di \(10\).
Dunque, se non ho sbagliato i conti (li ho sbagliati, ma poi li ho corretti
), il totale dovrebbe ammontare a \(52\) possibili relazioni di equivalenza. A questo punto la mia domanda è la solita. Nel caso di \(n\) elementi, esiste un modo di contare le relazioni di equivalenza passando da una teoria generale?
Ciao.
Essendo cinque un numero relativamente piccolo, possiamo fare tutto esplicitamente contando le possibili partizioni. Innanzitutto, c'è \(1\) modo per prendere tutti gli elementi e \(1\) per prendere solo singoletti. Poi ci sono esattamente \(5\) modi per partizionare l'insieme in un singoletto contro quattro elementi. Dopodiché, posso suddividere l'insieme in due coppie e un singoletto; ho \(5\) modi per scegliere il singoletto, più \(3\) modi per formare le coppie, quindi \(15\) modi in totale. Un insieme di due elementi contro uno di tre, dà \(\binom{5}{3}=10\). Due singoletti contro una terzina, dà ancora \(10\). Infine, con tre singoletti e una coppia, la scelta della coppia fissa i singoletti rimanenti, per un totale di \(10\).
Dunque, se non ho sbagliato i conti (li ho sbagliati, ma poi li ho corretti
), il totale dovrebbe ammontare a \(52\) possibili relazioni di equivalenza. A questo punto la mia domanda è la solita. Nel caso di \(n\) elementi, esiste un modo di contare le relazioni di equivalenza passando da una teoria generale?Ciao.
Risposte
Credo che il trucco sia fissare un certo numero di singoletti e poi capire in che modo posso partizionare gli elementi rimanenti. Sono abbastanza sicuro che ci debba essere una qualche relazione di ricorrenza, visto che fissare un singoletto equivale ricondursi ad un caso \(n-1\) e così via, ma ci sto ancora pensando per bene. Se qualcuno ha input e suggerimenti, li accetto volentieri.
Ciao.
Ciao.
Non so se hai sbagliato i conti (mi pare di sì ma vista l'ora non ci giurerei ) però si può notare questo: ogni relazione di equivalenza partiziona l'insieme in classi ovvero lo divide in sottoinsiemi disgiunti che "fanno" tutto l'insieme.
Il resto un'altra volta …
Cordialmente, Alex
) però si può notare questo: ogni relazione di equivalenza partiziona l'insieme in classi ovvero lo divide in sottoinsiemi disgiunti che "fanno" tutto l'insieme.Il resto un'altra volta …
Cordialmente, Alex
Ciao axpgn, sto correggendo ora il messaggio perché ho scritto delle cose sbagliate. Torno tra qualche minuto...
Anch'io Non è l'ora giusta 
Non è l'ora giusta
Okay, il post originale ora dovrebbe essere corretto.
Penso che questa sia la strada giusta. Infatti \(2^n\) è giustamente il numero di \(k-\)combinazioni al variare di \(k\) (come mi conferma Wikipedia ), ma bisogna considerare che data una \(k-\) combinazione esistono in generale più modi di partizionarla.
Questo però mi dà un'idea: il numero \(P_n\) di partizioni possibili è ricavabile in modo ricorsivo considerando la somma al variare di \(k\) delle \(k-\)combinazioni, moltiplicate per il numero \(P_k\) di partizioni corrispondenti. In formula, \(P_{n+1}=\sum_k\binom{n}{k}P_k\).
Cosa ne dici?
Penso che questa sia la strada giusta. Infatti \(2^n\) è giustamente il numero di \(k-\)combinazioni al variare di \(k\) (come mi conferma Wikipedia
), ma bisogna considerare che data una \(k-\) combinazione esistono in generale più modi di partizionarla.Questo però mi dà un'idea: il numero \(P_n\) di partizioni possibili è ricavabile in modo ricorsivo considerando la somma al variare di \(k\) delle \(k-\)combinazioni, moltiplicate per il numero \(P_k\) di partizioni corrispondenti. In formula, \(P_{n+1}=\sum_k\binom{n}{k}P_k\).
Cosa ne dici?
Dico di rileggere quello che ho scritto (cioè modificato ) e di cancellare la citazione del mio post per evitarmi figuracce
) e di cancellare la citazione del mio post per evitarmi figuracce
Guarda che bellina!
È proprio il tuo caso.
È proprio il tuo caso.
Wow, grazie mille! Ho cercato, prima di postare, "number of equivalence relations on a set", ma non ho trovato riferimenti ai numeri di Bell, che sono proprio quello che cercavo (cercando invece "number of partitions" vedo che sono tra i primi risultati...). Comunque, vedo che effettivamente la relazione di ricorrenza è corretta! E vedo anche che non ci sono formule più esplicite, quindi mi accontento del risultato.
Direi che cancellare la citazione è il minimo che possa fare. Ciao.
Direi che cancellare la citazione è il minimo che possa fare. Ciao.
Grazzzie!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo