Matematica Discreta I Lezione del giorno 28 novembre 2007 Partizioni e numeri di Stirling

(1)

Matematica Discreta I

Lezione del giorno 28 novembre 2007 Partizioni e numeri di Stirling

Dato un insieme non vuoto A, si chiama partizione di A un qualunque insieme di sottoinsiemi di A che soddisfano le seguenti proprietà:

1) sono sottoinsiemi non vuoti

2) a 2 a 2 sono disgiunti, cioè non hanno elementi in comune 3) la loro unione coincide con l’insieme A

Esempi:

1) Se A={1,2,3,4,5,6,7}, esempi di partizioni di A sono:

{{1},{2,3,4},{5},{6,7}}

{{1,2,3,7},{6},{4,5}}

{{1,3,5,7}, {2,4,6,}}

(la prima è una partizione in 4 sottoinsiemi, la seconda in 3 sottoinsiemi, la terza in 2 sottoinsiemi) 2) Se A è l’insieme dei numeri naturali, esempi di partizioni di A sono:

{{numeri naturali pari}, {numeri naturali dispari}}

{{1,2},{3,4},{5,6},…….}

(la prima è una partizione in 2 sottoinsiemi, la seconda in un numero infinito di sottoinsiemi)

Sia ora A un insieme finito di cardinalità n, e consideriamo le partizioni di A in m sottoinsiemi (dove m è un naturale fissato): ovviamente m può avere valore minimo m=1 e valore massimo m=n.

Il numero di tutte le possibili partizioni di A in m sottoinsiemi è chiamato numero di Stirling ed è indicato con S(n,m) (sempre con 1mn).

Calcoliamo alcuni valori di S(n,m).

Per i valori estremi m=1 ed m=n si ha S(n,1)=1 (vi è una sola partizione di A in 1 sottoinsieme, in cui questo sottoinsieme è A stesso) e si ha S(n,n)=1 (vi è una sola partizione di A in n sottoinsiemi, in cui ognuno di questi sottoinsiemi contiene un singolo elemento di A).

Si ha S(3,2)=2: infatti se A={a,b,c} ha cardinalità n=3, le partizioni possibili di A in 2 sottoinsiemi sono le 3 seguenti:

{{a},{b,c}} , {{b},{a,c}} , {{c},{a,b}}.

Possiamo sistemare i numeri di Stirling S(n,m) nel triangolo di Stirling, in cui in ogni riga vi sono i valori con n fissato ed m che varia da 1 a d n:

S(1,1)=1

S(2,1)=1 S(2,2)=1

S(3,1)=1 S(3,2)=3 S(3,3)=1

S(4,1)=1 S(4,2)=? S(4,3)=? S(4,4)=1

S(5,1)=1 S(5,2)=? S(5,3)=? S(5,4)=? S(5,5)=1 e così via.

Vi è una relazione molto stretta fra i numeri di una riga e quelli della riga precedente, che può servire per calcolare facilmente i numeri di Stirling, espressa dalla seguente formula:

S(n+1,m) = S(n,m-1)+mS(n,m)

(2)

Dimostrazione della formula:

S(n+1,m) é il numero delle partizioni di un insieme di cardinalità n+1 in m sottoinsiemi; sia quindi A={a

1

, a

2

, …. , a

n

, a

n+1

} un insieme di cardinalità n+1. Poniamo poi B=A-{a

n+1

}: B ha cardinalità n.

Le partizioni di A in m sottoinsiemi possono essere suddivise in 2 categorie:

1) le partizioni in cui l’elemento a

n+1

è da solo in uno dei sottoinsiemi della partizione

2) le partizioni in cui l’elemento a

n+1

è insieme con altri elementi in uno dei sottoinsiemi della partizione

Le partizioni della categoria 1) si ottengono scegliendo una partizione di B in m-1 sottoinsiemi (tale scelta si può effettuare in S(n,m-1) modi diversi) e poi aggiungendo il sottoinsieme {a

n+1

}: quindi le partizioni della categoria 1) sono in numero di S(n,m-1).

Le partizioni della categoria 2) si ottengono scegliendo una partizione di B in m sottoinsiemi (tale scelta si può effettuare in S(n,m) modi diversi) e poi inserendo l’elemento a

n+1

in uno degli m sottoinsiemi della partizione (questa scelta si può effettuare in m modi diversi): quindi, per il principio delle scelte multiple, le partizioni della categoria 2) sono in numero di mS(n,m).

Il numero totale S(n+1,m) delle partizioni dell’insieme A di cardinalità n+1 in m sottoinsiemi si ottiene sommando il numero delle partizioni delle 2 categorie, e si ottiene la formula voluta.

La formula permette di calcolare tutti i numeri di Stirling di una riga, conoscendo quelli della riga precedente. Per esempio:

S(4,2)=S(3,1)+2S(3,2)=7 , S(4,3)=S(3,2)+3S(3,3)=6 (tali valori completano la riga n. 4).

Conoscendo i valori della riga 4, si possono calcolare quelli della riga 5 e così via.