calcolo combinatorio

calcolo combinatorio

calcolo combinatorio settore disciplinare che studia i modi di scegliere, raggruppare e ordinare oggetti appartenenti a uno o più insiemi finiti, con l’obiettivo finale di enumerare i possibili raggruppamenti o ordinamenti. Fa parte di un più generale settore di studi denominato → analisi combinatoria. I raggruppamenti combinatori più spesso considerati sono: → disposizioni, → combinazioni di n oggetti di classe k (con o senza ripetizione) e → permutazioni di n oggetti. Se per esempio occorre scegliere k oggetti tra n, il calcolo combinatorio permette di determinare il numero di tutte le possibili scelte, distinguendo tra diversi casi a seconda che sia importante l’ordine con cui si selezionano tali oggetti oppure no e che sia possibile ripetere la scelta dello stesso elemento oppure no. Se importa l’ordine, come per esempio accade se si debbono premiare il primo, il secondo e il terzo arrivato in una competizione, ognuna delle possibili scelte si chiama disposizione, oppure permutazione se k coincide con n. Se non interessa l’ordine, come quando per esempio si vuole valutare il numero di possibili gruppi di cinque carte che si possono estrarre da un mazzo, si parla invece di combinazioni. Se gli oggetti sono simboli, quali per esempio cifre o lettere dell’alfabeto, è possibile che occorra considerare scelte ordinate che comportano delle ripetizioni; si parla allora di disposizioni con ripetizione. Per il calcolo del numero di ognuno di tali raggruppamenti combinatori si utilizza questo principio base: se un esperimento ha p esiti possibili e un altro esperimento, indipendente dal precedente, ha q esiti possibili, allora i due esperimenti danno luogo complessivamente a pq esiti possibili. Così, per un codice formato da due cifre diverse, si hanno 10 possibili esiti per la prima scelta e 9 per la seconda (giacché tale cifra deve essere diversa da quella scelta in precedenza): il numero di tali possibili codici è allora 90. Il problema della scelta, eventualmente ordinata, di k elementi semplici tra n assegnati interviene in molti settori della matematica, per cui il calcolo combinatorio si applica anche alla teoria dei grafi, allo studio delle cardinalità di famiglie di insiemi soggette a particolari vincoli di intersezioni o all’analisi della complessità degli algoritmi finiti. Inoltre, poiché molti dei problemi classici di calcolo delle probabilità si riducono al calcolo del numero dei casi favorevoli e di quelli possibili, il calcolo combinatorio interviene in modo determinante in tali problemi.