Partizioni di insiemi..

[pic88]

Le partizioni di un insieme di n elementi siano d(n). Posto d(0)=1, per ogni N abbiamo

$ \displaystyle d(N)=\sum_{k=0}^{N-1} \left {N-1} \choose k \right d(k) $

Dimostrare.

[pic88]

UP!
Se non sono completamente fuso, non è un problema difficile!

[albert_K]

mmm...così a occhio mi verrebbe da dire che

[albert_K]

scherzo, poi in realtà questa delirante formula calcola il numero di partizioni di un intero, quindi conta come uguali partizioni di 3 (1,2) e (2,1).

[pic88]

Adesso dimostri o quella formula o risolvi il problema!

Hint: fissato un elemento x dell'insieme....

[albert_K]

Scelgo la seconda!

Fisso un elemento. Allora per ognuno dei $ \displaystyle \binom{N-1}{k} $ sottoinsiemi X di k elementi che lo contengono esistono $ $d(k)$ $ partizioni distinte, formate dall'insieme X e da tutte le altre formate dai restanti k elementi.


In effetti, basta "leggere" la formula

Comunque, è un INDAM della specialistica vero?

[pic88]

Certo... mi piaceva perché ha una soluzione semplice, anche se la sua seconda parte è dimostrare la formula chiusa... per la quale credo servano i numeri di Bell..

[edriv]

Dire che per contare le partizioni servono i numeri di Bell è come dire che per contare quanti sono i cardi nel campo di mia nonna servono i numeri di Elvira, dove i numeri di Elvira per definizione indicano il numero di cardi nel campo di mia nonna (in funzione del mese e dell'anno).

[pic88]

Dire che per contare le partizioni servono i numeri di Bell è come dire che per contare quanti sono i cardi nel campo di mia nonna servono i numeri di Elvira, dove i numeri di Elvira per definizione indicano il numero di cardi nel campo di mia nonna (in funzione del mese e dell'anno).

è tuttavia più attinente alla discussione