COMBINATORIA, ANALISI

COMBINATORIA, ANALISI

. È una parte dell'aritmetica, la quale specialmente si prefigge di contare gli aggruppamenti di varia specie, che si possono formare con dati oggetti o con simboli di essi. È sussidiaria a diverse teorie di algebra, segnatamente a quella dei determinanti e a quella dei gruppi di sostituzioni, e porge i mezzi per la risoluzione di questioni di calcolo delle probabilità e per l'analisi di svariati giuochi matematici. Compare per la prima volta nel Traité du triangle arithmétique (1654) di B. Pascal; ne trattarono G. W. Leibniz nella Dissertatio de arte combinatoria (1666), J. Wallis nel Treatise of Algebra (1685), B. Frénicle de Bessy nell'Abrégé des combinaisons (1693), Giacomo Bernoulli nella Ars coniectandi (1713), A. de Moivre nella Doctrine of chances (1718).

Gli aggruppamenti di oggetti che prima sono da considerare sono le disposizioni, le permutazioni e le combinazioni.

Se si hanno m oggetti e ne collochiamo uno per ciascun posto su n posti allineati (s'intende che n è minore o tutt'al più eguale a m), e ciò facciamo in tutti i modi possibili, for,miamo le disposizioni degli m oggetti ad n ad n (di classe n). Con quattro oggetti, a, b, c e d, le disposizioni ad uno ad uno sono: a, b, c, d; quelle a due a due sono: ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc; e così via. In generale con m oggetti possiamo scegliere in m modi l'oggetto da collocare nel 1° posto, in m - 1 modi quello da collocare nel 20, in m - 2 modi quello da collocare nel 3° e così via. Appare così che il numero D_{m, n} delle disposizioni di m oggetti ad n ad n è dato dalla formula:

Le disposizioni di m oggetti ad m ad m, cioè gli ordinamenti di tali oggetti, si dicono permutazioni degli oggetti stessi. Il loro numero Pm (= D_{m, m}) è dato dalla formula:

il prodotto del 2° membro, cioè il prodotto dei numeri naturali da 1 a m, si dice fattoriale di m, e si trovano per esso adottati i simboli π(m), m, e, ora più comunemente, m!. Di due oggetti, a e b, si hanno le permutazioni a b e b a; di tre, a, b e c, le permutazioni a b c, a c b, b a c, b c a, c a b, c b a; dalla prima di queste, quando si abbia un quarto oggetto, d, si ricavano le quattro permutazioni d a b c, a d b c, a b d c, a b c d, e altre quattro se ne ricavano da ciascuna delle cinque rimanenti, così da farne in tutto 24, cioè 4!; e così via. I cosiddetti anagrammi di una parola sono le permutazioni delle sue lettere che dànno luogo ancora a parole (così da Roma si traggono amor, armo, mora, orma, ramo).

Fra le disposizioni di m oggetti ad n ad n (n ≤ m), due possono constare degli stessi elementi e distinguersi solo per l'ordine di questi: quando ciò accada, si dice che le due disposizioni corrispondono ad una stessa combinazione degli m oggetti ad n ad n o di classe n; le combinazioni di m oggetti ad n ad n sono dunque i diversi gruppi non ordinati di n fra gli m oggetti dati. Con gli oggetti a, b, c e d, le combinazioni a uno a uno sono: a, b, c, d; quelle a due a due sono: a b, a c, a d, b c, b d, c d; quelle a tre a tre sono: a b c, a b d, a c d, b c d; e si ha la sola combinazione a b c d dei quattro oggetti a quattro a quattro. Se di m oggetti si pensano fatte tutte le combinazioni ad n ad n, e su ciascuna di queste si fanno tutte le n! permutazioni possibili, si hanno le disposizioni degli m oggetti ad n ad n; perciò, indicato C_{m, m} il numero delle combinazioni di m oggetti ad n ad n, si ha: C_{m, n} • P_n = D_{m, n}, e risulta:

Se si hanno quindi in un'urna m palle distinte coi numeri da i ad m e si vuol sapere quanti casi sono possibili nell'estrazione di n di esse, senza aver riguardo all'ordine, siamo appunto condotti a contare le combinazioni di m oggetti ad n ad n. Con 90 numeri, come comunemente interessa, le combinazioni a due a due, o a tre a tre, o a quattro a quattro, o a cinque a cinque, cioè gli ambi o i terni o le quaterne o le cinquine possibili, sono rispettivamente

vale a dire rispettivamente 4005, 117.480, 2.555.190, 43.949.268.

I numeri interi C_{m, n} si denotano anche con

Una formula molto importante, nella quale si presentano come coefficienti codesti numeri C_{m,. n}, è lo sviluppo della potenza m^esima di un binomio x + y. Poiché, secondo il calcolo letterale, lo sviluppo del prodotto d'un polinomio per un altro si ottiene moltiplicando ciascun termine del primo per ciascun termine del secondo, si ha:

e così via. Si vede che lo sviluppo di (x + y)^m è formato dai termini che si ottengono prendendo, in tutti i modi e in tutti gli ordini possibili, m fattori, che siano gli uni uguali ad x, gli altri ad y. In tale sviluppo si ha un termine e uno solo, dove gli m fattori son tutti eguali a x, e un termine e uno solo, dove sono tutti eguali a y; e di termini che risultino da m - n (cioè m −1, o m −2,..., o 2, o 1) fattori x e da n (cioè 1, o 2,..., o m −2, o m −1) fattori y, se ne hanno tanti quante sono le combinazioni di m oggetti ad n ad n, cioè C_{m, n}. Termini siffatti sono fra loro eguali; e perciò, tenendo conto che è

e ponendo, per uniformità di notazione,

si ha:

È questa la cosiddetta formula del binomio del Newton (per la storia v. binomio, VII, p. 40). Per le prime potenze si ha:

e coi coefficienti si forma la tabella:

dove ogni elemento è la somma di quello che gli sta sopra e dell'elemento che sta alla sinistra di questo (si pensino scritti degli zeri nei posti che così si trovino vuoti). Tale tabella è detta triangolo aritmetico di N. Tartaglia, perché la troviamo nel General trattato di numeri et misure (II, 1556; fol. 69 verso) o di B. Pascal (Traité cit.); la legge ora indicata per la sua formazione era nota a M. Stifel, quando scriveva l'Aritmetica integra (1544), ed anche anteriormente (v. binomio, IV, p. 41).

Nelle diverse verticali della tabella, dopo la prima, si hanno le successioni dei cosiddetti numeri figurati (v. aritmetica, IV, p. 364); i numeri 1, 2,3,... sono quelli degli elementi delle figure che si ottengono allineando oggetti quali si vogliano; i numeri 1, 3, 6, 10, 15,... (triangolari) sono quelli degli elementi dei triangoli che si possono formare ponendo in un piano, a contatto l'uno dell'altro, dei dischi circolari eguali; i numeri 1, 4, 10, 20, 35,... (tetraedrali) sono quelli degli elementi dei tetraedri che si possono formare con sfere eguali a contatto una dell'altra (come quando si fanno mucchi, a basi triangolari, di proiettili sferici); i numeri delle verticali successive si possono dire numeri figurati del 4°, 5°, ... ordine. Si vede che se, in una qualsiasi delle verticali di numeri figurati, sommiamo elementi consecutivi a partire dal primo, otteniamo il numero che sta alla destra del sottostante all'ultimo sommato.

Dopo gli aggruppamenti delle specie considerate interessano le permutazioni di m oggetti fra i quali se ne abbiano degli eguali; e poi le disposizioni con ripetizione e le combinazioni con ripetizione di m oggetti ad n ad n.

Dati m oggetti, se ne fissino k 〈 m. Fra le m! permutazioni degli m oggetti dati se ne hanno k!, dove i k oggetti fissati occupano certi determinati k posti e nei rimanenti m − k posti sono disposti nel medesimo modo i rimanenti m − k oggetti; e queste permutazioni si confondono in una sola, diversa da ciascuna delle rimanenti, se i k oggetti fissati si sostituiscono con altrettanti oggetti eguali. Si riducono quindi a m!/k! le permutazioni di m oggetti fra i quali se ne abbiano k eguali; e in generale il numero P′_m delle permutazioni di m oggetti, fra i quali se ne abbiano k fra loro eguali, l fra loro uguali ma diversi dai precedenti, e così via, è dato da:

Quando si parla di disposizioni e di combinazioni con ripetizione di m oggetti ad n ad n (di classe n), s'intende che si operi con segni degli m oggetti e che ogni tal segno, in ognuno degli aggruppamenti definiti sopra come disposizioni o combinazioni, possa essere ripetuto una o più volte. Con osservazioni analoghe a quelle già fatte si trova che il numero D′_{m, n} delle disposizioni con ripetizione di m oggetti ad n ad n è mⁿ. E quanto alle combinazioni, è ovvio che le combinazioni con ripetizione di m oggetti a uno ad uno sono m, cioè C_{m, 1}; quelle a due a due, che possiamo formare accompagnando il primo elemento a sé stesso e a ciascuno dei successivi, quindi il secondo pure a sé stesso e a ciascuno dei successivi e così via, sono m + (m − 1) + ... + 2 + 1, cioè (m + 1) m/2 0 C_m +1,2; e quelle a tre a tre si possono formare accompagnando il primo elemento a ciascuna delle (m + 1) m/2 combinazioni con ripetizione degli m oggetti a due a due; quindi, accompagnando il secondo elemento a ciascuna delle m (m − 1)/2 combinazioni con ripetizione a due a due degli m − 1 oggetti che restano, di quelli dati, togliendo il primo; e poi accompagnando il terzo elemento a ciascuna delle (m − 1) (m − 2)/2 combinazioni con ripetizione a due a due degli m - 2 oggetti che restano, di quelli dati, togliendo i primi due; e così via. Si vede in tal guisa che le combinazioni con ripetizione di m oggetti a tre a tre sono

e quindi per una proprietà, sopra osservata, delle somme di numeri figurati, sono

In generale le combinazioni con ripetizione di m oggetti a n a n sono C_m+n-1.m con quattro oggetti, a, b, c, e d, le disposizioni con ripetizione a due a due sono

sono, nel quadrato, sottolineate le diverse combinazioni con ripetizione dei quattro oggetti a due a due. S'intende come si possano pensare distribuite in un cubo le disposizioni con ripetizione di m oggetti a tre a tre, e come nel cubo si possano distinguere le diverse combinazioni con ripetizione.

Bibl.: Gli elementi del calcolo combinatorio si trovano in tutti i principali trattati di algebra (v.). Per sviluppi più ampî v. E. Netto, Lehrbuch der Combinatorik, Lipsia 1901, 2ª ed., 1927.