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.

Annunci

Un pensiero su “Una semplice tecnica per contare

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...