Discussioni su Algebra astratta, Logica Matematica, Teoria dei Numeri, Matematica Discreta, Teoria dei Codici, Algebra degli insiemi finiti, Crittografia.
08/01/2019, 17:04
Ciao a tutti, sto riproponendo questo argomento probabilmente già trattato in questo forum, ma sto effettuando ricerche sia qui e sia altrove e non riesco proprio a venirne a capo, neanche sul libro da dove sto studiando riporta queste informazioni. Come si fa a stabilire quante relazioni di equivalenza è possibile definire in un insieme?
Ad esempio su un insieme molto semplice come $S = {1, a, 3}$?
09/01/2019, 08:31
Relazione di equivalenza = partizione. Quindi basta contare le partizioni.
09/01/2019, 09:19
Martino ha scritto:Relazione di equivalenza = partizione. Quindi basta contare le partizioni.
Se $S$ è un insieme finito con $|S|=n$ elementi, allora l'insieme delle parti di $S$ contiene $|P(S)|=2^n$ sottoinsiemi.
Quindi in ogni caso per trovare il numero di relazioni di equivalenza basta elevare 2 alla cardinalità dell'insieme?
09/01/2019, 10:36
Direi proprio di no, una partizione deve soddisfare diversi criteri, non basta prendere sottoinsiemi qualsiasi in $P(A)$
09/01/2019, 11:51
anti-spells ha scritto:Direi proprio di no, una partizione deve soddisfare diversi criteri, non basta prendere sottoinsiemi qualsiasi in $P(A)$
Giusto giusto non ci avevo pensato. Quindi c'è un modo per calcolare il numero di partizioni di un insieme o bisogna procedere "a mano"?
09/01/2019, 12:10
Spike32 ha scritto:anti-spells ha scritto:Direi proprio di no, una partizione deve soddisfare diversi criteri, non basta prendere sottoinsiemi qualsiasi in $P(A)$
Giusto giusto non ci avevo pensato. Quindi c'è un modo per calcolare il numero di partizioni di un insieme o bisogna procedere "a mano"?
Notoriamente non c'è una formula chiusa per faro; puoi trovare delle relazioni di ricorrenza che ti permettono di implementare degli algoritmi relativamente efficaci che calcolino le partizioni di un intero dato, ma sono comunque molto dispendiose.
12/01/2019, 17:34
"Notoriamente non c'è una formula chiusa per faro; puoi trovare delle relazioni di ricorrenza che ti permettono di implementare degli algoritmi relativamente efficaci che calcolino le partizioni di un intero dato, ma sono comunque molto dispendiose.".
Direi che invece c'è :
https://en.wikipedia.org/wiki/Bell_number
12/01/2019, 18:31
Pazzuzu ha scritto:"Notoriamente non c'è una formula chiusa per faro; puoi trovare delle relazioni di ricorrenza che ti permettono di implementare degli algoritmi relativamente efficaci che calcolino le partizioni di un intero dato, ma sono comunque molto dispendiose.".
Direi che invece c'è :
https://en.wikipedia.org/wiki/Bell_number
Cioè esiste una funzione $f : NN \to NN$, possibilmente ricorsiva, il cui valore in $n$ non dipenda da \(\{f(k)\mid k < n\}\), che permette di esprimere l'$n$-esimo numero di Bell?
12/01/2019, 21:50
Sto dicendo che esiste un'espressione in forma chiusa per calcolare l'ennesimo numero di Bell.
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.