A conti fatti. Formule utili per la risoluzione di esercizi.

Conteggi classici

Ricordiamo alcune formule che possono essere molto utili per la risoluzione di alcuni esercizi, ottenute facendo anche uso di tecniche combinatorie.

• La somma dei primi n numeri naturali è data dalla formula:

• La somma dei primi n quadrati è data dalla formula:

• La somma dei primi n cubi è data dalla formula:

• Il numero delle diagonali di un poligono di n vertici è dato dalla formula:

Infatti ogni vertice può essere collegato agli n−3 vertici non adiacenti (tutti i vertici tranne se stesso, quello alla sua destra, e quello alla sua sinistra). In questo modo, tuttavia, ogni diagonale A_iA_j viene contata due volte: una volta come uscente da A_i e una volta come uscente da A_j. Occorre quindi dimezzare, ottenendo la formula cercata.

•  Si consideri il numero m con scomposizione in fattori primi m = p^α: risulta ovvio che m avrà come unici divisori

1,p,p²,p³,…,p^α.

Il numero di tali divisori è dunque α +1.

Se invece consideriamo un numero m₀ con scomposizione in fattori m₀ = p₁^α1· p₂^α2, rifacendosi al procedimento precedente otteniamo che il numero di divisori di m₀ è (α₁+1)·(α₂+1): infatti ogni divisore sarà del tipo d = p₁^β1·p₂^β₂ con 0 ≤ β_i ≤ α_i, e possiamo scegliere β₁ in (α₁ + 1) modi e β₂ in altri (α₂ + 1) modi indipendenti.
Sia infine n = p₁^α1· p₂^α2· … · p_k^αk la fattorizzazione in numeri primi di n qualunque. Se si utilizza un ragionamento analogo a quello condotto sopra, si ottiene che il numero di divisori di n è dato da

Cerchiamo ora di capire come si può esprimere in formula la somma dei divisori di un numero. Consideriamo nuovamente il numero m = p^α : la somma dei suoi divisori sarà data dall’espressione:

(1 + p + p² + p³ + … + p^α).

In modo analogo si ottiene la formula generale:

Infatti, distribuendo i prodotti nella prima formula precedente, si ottiene la somma di tutti i possibili fattori

p₁^β1· p₂^β2· … · p_k^βk.

• Dati due interi, n non negativo, e k positivo, definiamo una partizione dell’intero n in k parti, una scrittura di n come n₁+n₂+…+n_k , dove i vari n_i sono non negativi. Il numero totale delle partizioni di un intero, tenendo conto dell’ordine con cui viene partizionato (per esempio, 12 = 3 + 5 + 4 è diverso da 12 = 5 + 3 + 4), è dato da:

(32)