Newsgroup: it.hobby.enigmi
Titolo: Partizioni

Nell'NG it.scienza.matematica Serena chiede
<Quante sono le partizioni di n elementi ?>
El Filibustero risponde con
mathworld.wolfram.com/PartitionFunctionP.html
Dove si trova una dettagliata descrizione riguardante il difficile
problema di contare le partizioni Non Orientate di un intero n.
Esistono pero' altri casi che possono essere affrontati in questo NG.
Ecco 3 problemi.
----------------------------------------------------------------
Quante sono le partizioni orientate ? Per capirci, prendiamo n palline
tutte bianche e dividiamole in gruppi in tutti i modi possibili. Nel
caso di partizioni orientate x+y e' differente da y+x.
Es. per n=3
1+1+1
1+2
2+1
3
-----------------------------------------------------------
Fin qui abbiamo considerato elementi indistinguibili, (palline tutte
dello stesso colore)
Quante sono le partizioni Non Orientate di elementi distinguibili ?
Come es. prendiamo n=3 palline di colore diverso A,B,C. Allora le Non
Orientate sono
ABC      
AB    C   
AC    B
BC    A
A     B     C
-----------------------------------------------------------
Supponiamo ora di avere n palline di colore diverso e n cestini numerati
(distinguibili) che le possono contenere.
In quanti modi posso ripartire le palline?
Es. con 2 palline:
Cesto1 Cesto2 
  A      B
  B      A
 AB      -
  -     AB 
 ----------------------------------------------------------
:) dario

In quanti modi posso ripartire le palline?
n^n. Per ognuno degli n oggetti si puo' scegliere uno qualunque degli
n cestini. Ciao

 funzione ricorsiva uguale a 2^(n-1).
Vero. Questo fatto si puo' notare subito mettendo i nostri elementi in
una stringa, diciamo di tutti "1". Ora una separazione la possiamo
indicare con "|".
Es:   1 1 1|1 1|1 1 = 3+2+2
E' chiaro che in ciascuno degli n-1 spazi tra due elementi consecutivi
posso mettere o NON mettere la separazione = 2^(n-1).
:) dario

Quante sono le partizioni Non Orientate di elementi distinguibili ?
1 per n=1, 2 per n=2, 5 per n=3, 15 per n=4, 52 per n=5, 173 per
n=6...  non sembra affatto semplice come gli altri 2 quesiti. Ciao

 n=6...  non sembra affatto semplice come gli altri 2 quesiti. Ciao
Vediamo di saperne qualcosa di piu' su questi particolari numeri, che in
letteratura sono noti come numeri di Bell. Prima chiediamoci: quanti sono le
partizioni Non Orientate di n elementi in *esattamente* m gruppi? Esempio,
per n=4
m=1 (1)
ABCD
m=2 (7)
ABC,D
ABD,C
ACD,B
BCD,A
AB,CD
AC,BD
AD,BC
m=3 (6)
A,B,CD
A,C,BD
A,D,BC
B,C,AD
B,D,AC
C,D,AB
m=4 (1)
A,B,C,D
Totale B(4)={4,1}+{4,2}+{4,3}+{4,4}=1+7+6+1=15
dove {m,n} sono proprio i numeri cercati, e si chiamano numeri degli insiemi
di Stirling, o numeri di Stirling di seconda specie.
Quindi l'ennesimo numero di Bell e' la somma dei n. di Stirling della
ennesima riga. Proviamo a costruire una specie di triangolo di Pascal:
n      numeri di Stirling    numeri di Bell
1               1                 1
2             1   1               2
3           1   3   1             5
4         1   7   6   1          15
5       1  15  25  10   1        52
6     1  31  90  65  15   1     203
7   1  63 301 350 140  21   1   877
la relazione ricorsiva e'
{n+1,k}={n,k-1}+k*{n,k}. Per esempio:
{5,3}={4,2}+3*{4,3}
 25  =  7  +3*  6
Ciao, Silv:o)

la relazione ricorsiva e' {n+1,k}={n,k-1}+k*{n,k}.
Se somma{k=1..n} Stirling(n,k) e' il modo piu' semplice di esprimere
B(n), ribadisco che il problema non e' per niente piu' semplice di
quello delle partizioni non orientate di n oggetti non distinguibili,
per cui c'e' la relazione ricorsiva 
P(n,k)=P(n-1,k-1)+P(n-k,k)
P(n,k)=0 per k>n
P(n,n)=1
P(n,0)=0
che da' Partizioni(n) = somma{k=1..n} P(n,k). Ciao