fbpx

Complementi di Combinatoria

Dagli studenti, per gli studenti

Complementi di Combinatoria

31/05/2020 PIÙ DI 60 0
MATEMATICA: GLI APPUNTI DI LUCIO
COMPLEMENTI DI COMBINATORIA

Il calcolo combinatorio studia, dato un insieme finito di oggetti, i modi e le possibilità di ordinare, disporre o presentare i suoi elementi, in base a determinate regole o restrizioni.

PRINCIPIO DEL PRODOTTO
Se voglio andare da A a C ho prima 2 possibilità e, in seguito, altre 3: a seconda di quale scelgo prima ho sempre 3 possibilità dopo. Vale quindi che A → C vale 3+3 oppure 2⋅3. Le possibilità di A → C equivalgono a (A → B) (B → C). Valuto quindi tutte le possibili strade che da A mi portano in C: 2>3.

Con 3 magliette, 4 pantaloni e 2 scarpe per ogni scelta che faccio su un capo d’abbigliamento posso ancora scegliere tutte le altre: 3 possibilità di scegliere la maglietta 4 per i pantaloni 2 per le scarpe.

Alla base della combinatoria c’è questo semplice principio che applichiamo quotidianamente: moltiplicando correttamente le possibilità di effettuare delle scelte ottengo tutte le possibilità del caso.

PRINCIPIO DEL PRODOTTO

le possibilità di effettuare k scelte su n1nk scelte per ogni scelta di k da 1 a n corrisponde a:

n = n1… nk.

PERMUTAZIONI

Se devo sistemare 3 oggetti in 3 vani di un armadio, avrò 3 possibilità di scelta per il primo, 2 per il secondo e 1 per il terzo. Secondo il principio del prodotto avrò quindi 1⋅2⋅3 possibilità di mettere gli oggetti nei vani.

Allo stesso modo, se voglio determinare tutti i possibili anagrammi di MANO (4 lettere distinte), posso sempre ragionare con un modello a scatole: per la prima posso scegliere fra 4 lettere, per la seconda 3, e avanti così fino all’ultima quando avrò 1 sola scelta. Quindi posso dire di avere n possibilità, con n=4⋅3⋅2⋅1.

Notiamo uno schema comune: quando dobbiamo presentare in maniera ordinata degli oggetti finiamo sempre per avere la moltiplicazione del numero di oggetti con tutti i suoi minori fino a 1. Operazione che chiamiamo fattoriale.

FATTORIALE

 


Le presentazioni ordinate di oggetti si chiamano permutazioni: in entrambi gli esempi si può pensare che abbiamo dovuto determinare quante diverse possibilità ci fossero di ordinare gli elementi.

PERMUTAZIONI

Una presentazione ordinata di n elementi distinti tra loro è detta Permutazione e ha 

Pn=n! possibilità di essere ordinata.


Se però dovessimo calcolare quanti anagrammi della parola MAMMA esistono, ci accorgeremmo che ottenere MAMMA oppure MAMMA, per quanto siano permutazioni diverse, danno sempre lo stesso risultato. Come risolvere il problema delle ripetizioni? Basta dividere la permutazione totale per le permutazioni delle lettere che si ripetono, sempre secondo il principio del prodotto: se le stesse lettere cambiano di posizione, il risultato non cambia.

Anagrammi di mamma:

5!
3!⋅2!

PERMUTAZIONI

Una presentazione ordinata di n oggetti, di cui 

ki indistinguibili tra loro è detta permutazione con ripetizioni e vale

DISPOSIZIONI
Se dovessi invece stilare tutte le possibilità di comporre una classifica dei primi 10 concorrenti in una competizione con 20, potrei pensare al problema come una permutazione dove i 10 che non considero siano indistinguibili e quindi si ripetano tutti; oppure ancora, secondo il principio del prodotto, equivarrebbe a moltiplicare tutte le possibilità che ho fino all’11 (20⋅19⋅…⋅11) e per 1 con tutti i concorrenti che non considero.





DISPOSIZIONI SEMPLICI

Una presentazione ordinata di k oggetti scelti fra n è una disposizione semplice:


Se i k elementi scelti fra n si ripetessero potrei semplicemente applicare il principio del prodotto: n possibilità per il primo, per il secondo, fino al k-esimo.

DISPOSIZIONI CON RIPETIZIONI

Una presentazione ordinata di k oggetti scelti fra n, dove tutti gli elementi sono indistinguibili è una disposizione con ripetizioni:

COMBINAZIONI

Arriviamo ora al tema caldo della combinatoria: giustamente, le combinazioni. Pensiamo di voler determinare tutte le possibilità che abbiamo di formare un comitato di k persone scelte fra n. Rispetto alle disposizioni semplici quello che cambia è l’ordine: non ci interessa sapere quante possibilità ho di disporre i membri del nuovo comitato, ma solo sapere quanti possibili comitati potrei formare.

Quello che faccio è dividere le permutazioni totali (n!) oltre che per i membri che escludo ((n-k)!) anche per le permutazioni di quelli che scelgo (k!) mantenendo così una sola formazione per tutti i modi possibili che avrei di ordinarli.

COMBINAZIONI

Una combinazione è una presentazione non ordinata di k oggetti scelti fra n


Una combinazione equivale quindi a una disposizione senza più tener conto dell’ordine:


COEFFICIENTE BINOMIALE

Per comodità poniamo


Il coefficiente binomiale ha una particolarità: per ogni coppia n e k, con k da 0 a n, il valore del coefficiente binomiale corrisponde al k-esimo elemento dell’n-esima riga del triangolo di Tartaglia.

Da questa considerazione segue che, con meno calcolo rispetto a quello richiesto dal triangolo di Tartaglia, è possibile sfruttare il coefficiente binomiale per sviluppare un binomio. I coefficienti di (a+b)n sono appunto ( n / k ) con k=0, …, n.

Vuoi saperne di più? Ti consiglio questo articolo di weschool.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *