combinatorio, calcolo
combinatorio, calcolo
Settore della matematica che studia la maniera di contare in quanti modi si possono raggruppare e/o ordinare un certo numero finito di oggetti. I raggruppamenti più frequentemente considerati sono disposizioni, permutazioni, combinazioni.
Disposizioni semplici
Dati n oggetti distinti contenuti in un’urna, una disposizione semplice di h≤n di essi si può pensare realizzata registrando i risultati di h successive estrazioni senza procedere al reimbussolamento. Indicando con Dn,h il numero di tali disposizioni semplici risulta Dn,h=n· (n−1)·…·(n−h+1). Lo si intende pensando che alla prima estrazione sono possibili n diverse alternative; alla seconda una delle (n−1) rimaste nell’urna, alla terza (n−2) e così via fino alla h-esima estrazione quando sono rimaste nell’urna n−(h−1) alternative.
Permutazioni
Nel particolare caso in cui h sia eguale a n, le disposizioni semplici si dicono permutazioni; esse sono in numero di Dn,n=n(n−1)·…·1, ovvero pari al prodotto dei primi n numeri interi. Per indicare tale prodotto si usa anche la sintetica notazione n!. Il numero delle permutazioni di n elementi si può interpretare come il numero degli anagrammi (indipendentemente dal loro senso linguistico) che si possono formare con una parola composta da n lettere distinte. Posto 0!=1, vale per ogni n intero positivo l’importante relazione n!=n(n−1)!. Risulta poi Dn,h=n(n−1)·…·(n−h+1)·(n−h)!/(n−h)! = n!/(n−h)!.
Disposizioni con ripetizione
Modificando lo schema in modo da effettuare estrazioni seguite dal reimbussolamento dell’oggetto estratto si contano invece le disposizioni con ripetizione. Esse sono in numero di nh e non è più necessario richiedere che h non sia superiore a n.
Combinazioni semplici
Dividendo invece Dn,h per h! si trova il numero delle combinazioni semplici di n elementi di classe h. Esse contano il numero dei modi in cui si possono scegliere h elementi fra n dati, quando non si badi all’ordine con cui si presentano gli elementi scelti, e dunque, considerando una combinazione semplice distinta da un’altra, quando differiscano per almeno uno degli elementi. Il simbolo usato per indicare il numero delle combinazioni semplici è poi Cn,h=n!/[h!(n−h)!]. Tali simboli sono noti anche con il nome di coefficienti binomiali. Risulta Cn,h =Cn,n−h. Infatti scegliere h elementi fra n dati significa anche simmetricamente scegliere l’insieme complementare degli n−h rimanenti. Posto Cn,0=1, risulta verificata la 2n=Cn,0+Cn,1+Cn,2+… +Cn,n. Lo si prova notando che a secondo membro si contano tutti i possibili modi di costruire sottoinsiemi di un insieme di n elementi, prendendone 0 (in un modo solo), oppure 1 in Cn,1 modi e via dicendo fino a prenderli tutti (ancora in un solo modo). D’altra parte, ordinati in modo arbitrario tutti gli elementi, si può procedere scegliendo per ciascuno di essi se farlo appartenere o meno all’insieme. Vi sono 2 possibilità (sì, no) per il primo elemento, 2 per il secondo, e così via e dunque globalmente 2n possibilità diverse: esattamente il numero a primo membro. Dati 2 numeri a, b si dice potenza n-esima del binomio la quantità (a + b)n; sfruttando i ragionamenti sulle combinazioni semplici è facile accertare che (a+b)n=a0bn Cn,0+a1bn−1 Cn,1 + a2bn−2 Cn,2 …+anb0 Cn,n Basti pensare che (a+b)n=(a+b)1 (a+b)2 ... (a+b)n e che quindi il termine ahbn−h , corrispondente alla scelta di h volte a e n−h volte b nel prodotto, comparirà Cn,h volte. I Cn,h sono quindi i coefficienti che compaiono nello sviluppo della potenza n-esima di un binomio; per tale motivo sono detti coefficienti binomiali. Si consideri una parola formata da n lettere non tutte distinte. Quanti sono gli anagrammi di tale parola? Se nella parola vi sono h lettere distinte e, indicando con con n1, n2, …, nh il numero di volte in cui compare ripetuta la prima, rispettivamente la seconda… la h-esima lettera il numero degli anagrammi è n!/[n1!n2!…nh!] che si dice numero delle permutazioni con elementi uguali. Esso si può interpretare anche come il numero delle diverse possibili ripartizioni di n oggetti fra h individui quando sia stabilito che al primo ne spettano n1, al secondo n2, …, all’h-esimo nh.