5 - Combinazioni semplici.

Esaminiamo ora una delle più classiche situazioni dalla quale scaturiscono combinazioni alle quali spetta la definizione di combinazioni semplici, da cui ha preso il nome tutta la combinatoria. Le regole che presiedono alla costituzione delle combinazioni semplici sono:

  • Si dispone di n oggetti, tutti diversi tra loro
  • se ne prendono ogni volta k (k £ n) per formare una combinazione di k oggetti
  • due combinazioni differiscono se hanno almeno un oggetto diverso
  • non ha importanza l'ordine con cui sono disposti gli oggetti.

Un esempio chiarirà meglio la situazione. Si deve costituire una commissione di k membri, scegliendoli all'interno di un gruppo di n persone. E' chiaro che non ha importanza l'ordine con cui sono scelti i membri. Ciò vale in Parlamento o in un Consiglio Comunale, in cui k deputati o consiglieri sono scelti fra tutti gli n cittadini, ma ognuno ha gli stessi poteri di qualunque altro, indipendentemente dai voti presi.
Nel linguaggio comune, il termine combinazione è usato a volte in modo improprio, quando ad esempio si definisce combinazione il gruppo di cifre necessarie per aprire una cassaforte. In questo caso si tratta invece di disposizioni, essendo importante anche l'ordine con cui le cifre sono composte. In particolare, si tratta di disposizioni con ripetizione, dal momento che una stessa cifra può essere usata più volte.
Il principio del pastore.
Prima di procedere alla individuazione delle regole che determinano il numero di combinazioni semplici di n elementi, presi k alla volta, è opportuno raccontare una storiella.
Un turista si rivolge ad un pastore incontrato in montagna: Certo è una bella fatica dover contare tutti i giorni un numero così grande di pecore!
Ribatte il pastore: No, è facilissimo!
Il turista, incuriosito, chiede: Come fai?".
Risponde il pastore: E' facile! Prima conto le zampe, e poi ... divido per 4!
La regola del pastore, che chiameremo principio di divisione, può sembrare alquanto ridicola, ma non lo è poi tanto. A volte, si fa prima a contare le "zampe" che le "pecore".
Un esempio, tratto dalla biografia di Gauss, può servire a chiarire questa apparente contraddizione. Il piccolo Gauss ebbe dal maestro l'ingrato compito di sommare i primi 100 numeri naturali. Dopo un po' l'allievo presentò la risposta : "La somma è 5050". Il maestro restò esterrefatto e chiese a Gauss come avesse fatto ad ottenere la somma in così breve tempo. Gauss rispose che gli era bastato riflettere sul fatto che, abbinando ai numeri da 1 a 100 i numeri da 100 ad 1, si ottenevano 100 coppie (un termine sulla 1a riga e l'altro sulla 2a) la cui somma è sempre 101:

1234...979899100
100999897...4321

Moltiplicando 100 x 101, si ottiene 10.100, che è il doppio della somma richiesta. A questo punto, basta dividere per 2 e il gioco è fatto: la somma richiesta è 5.050!
Si fa prima dunque a contare 200 numeri usando la moltiplicazione e dividendo per 2, che contarne 100 uno la volta.
Torniamo alla nostra questione: quante combinazioni di n elementi di classe k si possono formare? Sappiamo già che le disposizioni semplici, per gli stessi valori di k sono date dal fattoriale decrescente (n)k. Fra queste, però, ce ne sono alcune che sono costituite dagli stessi elementi per i quali varia soltanto l'ordine. Queste vanno contate una volta sola, dal momento che nelle combinazioni non interessa l'ordine. Quante ne sono? A questa domanda sappiamo già rispondere: si tratta delle permutazioni di k elementi, pari a k! Basta allora applicare il principio di divisione. Si avrà:

 


Il simbolo con cui vengono indicate le combinazioni semplici di k elementi presi da un insieme di n, si chiama anche coefficiente binomiale, per ragioni che vedremo in seguito.
E' bene chiarire l'uso della precedente formula con un esempio concreto: quante diverse commissioni si possono costituire, scegliendo 5 rappresentanti in un gruppo di 30 persone?

 


Le combinazioni semplici rivestono una particolare importanza nel calcolo combinatorio, trovando applicazione nella risoluzione di svariati problemi. Torneremo ancora sulle combinazioni, esaminando altri casi. Chiariremo alcuni aspetti ed alcune proprietà del calcolo combinatorio. Ora, però, occorre completare il quadro, esaminando altre situazioni combinatorie, nelle quali gli n elementi dell'insieme possono essere utilizzati più volte per la costituzione di una combinazione.