Numero di relazioni di equivalenza in un insieme

[Spike32]

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}$?

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

Relazione di equivalenza = partizione. Quindi basta contare le partizioni.

[Spike32]

"Martino":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?

[anti-spells]

Direi proprio di no, una partizione deve soddisfare diversi criteri, non basta prendere sottoinsiemi qualsiasi in $P(A)$

[Spike32]

"anti-spells":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"?

[fmnq]

"Spike32":[quote="anti-spells"]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"?[/quote]
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.

[Pazzuzu]

"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

[fmnq]

"Pazzuzu":"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?

[Pazzuzu]

Sto dicendo che esiste un'espressione in forma chiusa per calcolare l'ennesimo numero di Bell.