Una semplice tecnica per contare

È la prima volta che in questo blog mi metto a parlare di matematica nel senso più stretto della parola. In realtà questo non è un blog di matematica (forse lo diventerà? Chi può dirlo?), ma in fin dei conti può essere comunque carina qualche divagazione.

Quello che mostro ora è una ben nota e semplicissima (ma semplicissima) tecnica per contare gli elementi di un insieme finito, che ha il pregio di essere applicabile in una quantità sterminata di casi. Ciò che abbiamo sono un insieme finito $X$ (quello di cui vogliamo contare gli elementi), un altro insieme finito $Y$ e una funzione surgettiva $F : X \rightarrow Y$ . È veramente semplice accorgersi che:

$\displaystyle X = F^{-1}(Y) = \bigcup_{y \in Y} F^{-1}(y)$ ,

e quell’unione è disgiunta. Ma allora si ottiene la seguente formula:

$\displaystyle \# X = \sum_{y \in Y} \# F^{-1}(y)$ .

Tale formula diventa particolarmente utile quando la cardinalità di ognuno degli insiemi $F^{-1}(y)$ è indipendente da $y$ . In quel caso, denotata con $d$ tale cardinalità, quello che si ottiene immediatamente è:

$\# X = d \# Y$ .

Come applicazione, dimostriamo un semplice risultato sui gruppi finiti: dato un gruppo finito $G$ , e dato $n$ un intero, allora il numero degli elementi di ordine $n$ è esattamente $\varphi(n)$ volte il numero dei sottogruppi ciclici di $G$ di ordine $n$ . Con $\varphi(\cdot)$ denoto la funzione di Eulero. Ricordo che $\varphi(n)$ è pari al numero di generatori di un gruppo ciclico di ordine $n$ . Per vedere il risultato appena enunciato, ragioniamo così. Prendiamo $X$ l’insieme degli elementi di ordine $n$ in $G$ , poi $Y$ l’insieme dei sottogruppi ciclici di $G$ di ordine $n$ . Definiamo $F : X \rightarrow Y$ nel seguente modo:

$F(g) = \langle g \rangle$ ,

ove con $\langle g \rangle$ denoto il sottogruppo di $G$ generato da $g$ . È abbastanza chiaro che $F$ sia surgettiva; d’altra parte, per ogni $H \in Y$ (sottogruppo ciclico di ordine $n$ ), ho che $F^{-1}(H)$ è esattamente l’insieme dei generatori di $H$ . Dunque, per ogni $H$ , ottengo che $\# F^{-1}(H)=\varphi(n)$ . Ma allora, possiamo applicare la formula di cui sopra per contare gli elementi di $X$ , trovando proprio che:

$\# X = \varphi(n) \# Y$ ,

che è esattamente ciò che volevamo.

Like this:

Be the first to like this post.

Questo post è stato pubblicato il lunedì, 9 maggio 2011 alle 17:47 ed è archiviato in Matematica. Segui i commenti a questo post con il feed RSS 2.0. Puoi lasciare una risposta, o mandare un trackback dal tuo sito.

Una risposta a Una semplice tecnica per contare

Ani-sama scrive:

lunedì, 9 maggio 2011 alle 18:08

In realtà l’ipotesi di surgettività della $F$ non è essenziale, anche se è vera in tutti i casi interessanti.

Replica