Vi presento un semplice quiz, non per proporvelo, ma per risolverlo assieme, sfruttandolo poi per introdurre in modo estremamente intuitivo il coefficiente binomiale.

Al di là del suo nome che si riferisce al binomio di Newton, il coefficiente binomiale è uno strumento oltremodo utile nel calcolo combinatorio e le sue applicazioni sono numerosissime. Esso è talmente utile che si è usato un simbolo speciale per definire le operazioni che rappresenta.  Il problema è che, solitamente, viene data la sua definizione come formula compatta, in termini di fattoriali, ma raramente si spiega come tale formula si possa  ricavare in modo intuitivo.

Ed eccoci al quiz...

In  una stanze vi sono dieci persone. Ciascuna di loro stringe la mano a tutti gli altri una volta soltanto. Quante strette di mano sono avvenute nella stanza? Escludiamo subito la risposta che potrebbe forse apparire la più ovvia: ogni persona scambia la mano con le altre nove quindi il risultato dovrebbe essere 90 strette di mano.

La risposta è sbagliata e il suo perché deriva dalla scritta in neretto "una volta soltanto". Se la persona 1 scambia la mano con la persona 3, nel conto totale non si può più tener conto della persona 3 che stringe la mano alla 1: la loro stretta di mano va contata una volta soltanto.

Un minimo di ragionamento permette di risolvere correttamente la questione:

La persona 1 stringe la mano alle altre nove, il che comporta 9 strette di mano

La persona 2 stringe la mano a 8 persone, dato che la stretta di mano con la 1 è già stata contata.

La persona 3 stringe la mano a 7 persone, dato che le strette di mano con la 1 la 2 sono già state contate.

...

La persona 9 stringe la mano SOLO alla persona 10, dato che tutte le altre strette di mano sono già state contate.

La persona 10 non ha più nessuno a cui stringere la mano, dato che l'ha già stretta alle altre nove.

Quante strette di mano in totale:

9 + 8 + 7 + 6 + 4 + 5 + 3 + 2 + 1 + 0 = 45

Se non volete contarle direttamente, basta ricordare la formula che ci dà immediatamente la somma dei primi n numeri:

n (n+1)/2 = 9 10/2 = 90/2 = 45

Lo stesso quiz poteva essere espresso in altri termini:

Date 10 persone quante coppie di persone si possono formare, considerando identica la coppia (a,b) e la coppia (b,a)?

In realtà, nulla cambia, dato che la coppia (a,b) equivale a una stretta di mano tra a e b e va contata una volta sola.

Il quiz, però, potrebbe essere complicato in modo apparentemente "inoffensivo" ...

Date 10 persone, quante terne di persone si possono formare, considerando identiche le terne (a,b,c), (b,a,c), (c,b,a), (b,c,a), (c,a,b) e (a,b,c), ossia considerando identiche le terne composte dalle stesse persone, qualsiasi sia il loro ordine. Il considerare identiche le terne è proprio come considerare identiche le coppie che si stringono la mano: (a,b) e (b,a) sono la stessa cosa e va contata una sola volta.

Bene! Potete provare pure a risolvere questa variante, ma lavorando solo con la forza bruta la soluzione sarebbe tutt'altro che immediata. Vi posso anticipare che esistono ben 120 possibilità e sfido a non farsene scappare qualcuna, se le cercassimo senza una formula adeguata allo scopo.

Vediamo, allora, di affrontare il problema in modo generale e poi ricavare ciò che ci interessa veramente. Al posto delle strette di mano o delle terne di persone, possiamo semplificare la problematica, immaginando di avere tutti gli n numeri interi (con n qualsiasi) dentro a un sacchetto (un po' come il lotto... con n = 90)

Quanti numeri posso estrarre dal sacchetto? E' ovvio: n numeri. Bene, passo a una seconda estrazione: quanti numeri posso estrarre? Ovviamente solo (n -1) dato che un numero è già stato estratto e viene "eliminato" in quanto NON vogliamo che compaia più volte lo stesso numero nelle nostre estrazioni.  Per ogni numero estratto la prima volta vi sarebbero (n - 1) risultati possibili per la seconda estrazione. In altre parole, avremmo n (n-1) possibilità. Estraiamo un terzo numero. Otterremmo n(n-1)(n-2) possibilità.

Discorso analogo per la terza, la quarta, ecc. Dopo n- 1 estrazioni, quante palline sono rimaste nell’urna. Ovviamente una soltanto. Per cui i possibili risultati sono n(n-1)(n-2)… · 2 · 1. Questa scrittura, dove si moltiplicano tutti numeri da 1 a n viene sintetizzata con il simbolo esclamativo, ossia con il fattoriale "!" Parlando più tecnicamente, cosa rappresenta nel nostro caso? Il numero di possibili PERMUTAZIONI degli n numeri, ossia in quanti modi possono essere scritti gli n numeri, considerando ovviamente diversa qualsiasi posizione assunta da ciascun numero. In poche parole 1, 2, 3 è diversa da 3, 2, 1 , da 1, 3, 2, e via dicendo...

Bene a sapersi, ma il nostro problema è diverso, ossia vogliamo sapere quante possibili terne (o coppie, o quaterne o quello che preferite) possono essere estratte.

Bene, ricominciamo da capo. Estraiamo un primo numero. Esso può valere qualsiasi n. Estraiamo il secondo, esso può valere (n - 1) numeri. Quante possibili coppie ho ottenuto? Come detto prima, n(n-1). Estraiamo il terzo ottenendo n(n- 1)(n - 2) terne. Possiamo fermarci, dato che siamo interessati solo nelle terne e abbiamo descritto tutte le possibili terne estraibili dagli n numeri.  In pratica basta moltiplicare n per n - 1, fino a n - k + 1 a seconda del valore di k (due = coppie, tre = terne, ecc.). Infatti per k = 2, dobbiamo moltiplicare n per (n -1), ossia n(n - 1) = n(n - k + 1); per n = 3, dobbiamo moltiplicare n per (n - 1) per (n - 2), ossia per (n - 3 + 1) = n(n - k + 1).

Siamo a buon punto, dato che per sapere quante terne si possono formare basta eseguire la moltiplicazione appena descritta. Tuttavia, è comunque un modo abbastanza lungo di scrittura. Infatti, se avessimo 100 numeri e volessimo sapere quanti gruppi di 10 numeri si possono costruire, dovremmo scrivere 100 · 99 · 98 · 97 · 96 · 95 · 94 · 93 · 92 · 91, dove il 91 è proprio n - k + 1 = 100 - 10 + 1 = 91. Come poter compattare questa scrittura, utilizzando l'operazione di fattoriale appenda descritta?

Non è certo difficile. Basta scrivere n! e dividerlo per (n-k)!. Nel caso di k = 10, avremmo n - k = 90

(100 · 99 · 98 · 97 · 96 · 95 · 94 · 93 · 92 · 91 · 90 · 89 · 88 ·  ..... · 2 · 1)/(90 · 89 · 88 · .... · 2 · 1) = (100 · 99 · 98 · 97 · 96 · 95 · 94 · 93 · 92 · 91)

Usando i fattoriali :

n(n- 1)(n - 2) .... (n - k + 1) = n!/(n - k)!

Questa scrittura è decisamente più comoda, dato che i fattoriali dei numeri del secondo membro sono  facilmente reperibili  in rete, mentre le moltiplicazioni del primo membro andrebbero eseguite una per una...

Risolto il problema? Non ancora. Ciò che abbiamo ottenuto è il numero di possibili terne (o coppie, o quaterne  quello che preferite), ma esse non hanno vincoli sull'ordine in cui sono stati estratti i numeri. Ostacolo facilmente superabile, dato che ormai sappiamo quanto valgono tutte le permutazioni su k numeri. Esso è dato dal fattoriale del numero. Per chiarire melio la situazione, consideriamo ancora k = 3. Come possono presentarsi  tre numeri a, b e c? Presto detto:

(a, b, c), (a, c, b), (b ,a, c), (b, c, a), (c, a, b), (c, b, a)

In sei modi diversi, ma nel quiz reso più complicato, consideriamo uguali le terne che contengono i nostri numeri, in qualsiasi ordine vengano estratti. E 6 è proprio uguale a 3!, come preannunciato.

Ed ecco perciò la formula risolutiva che ci permette di conoscere quante sono le possibili terne relative a 100 numeri, in cui i tre numeri siano, però, sempre diversi tra loro.

In modo più rigoroso abbiamo trovato le COMBINAZIONI possibili di n elementi presi a gruppi di k:

n!/(k!(n- k)!)

Questa formula risolve, ovviamente, anche il caso delle strette di mani. In quel caso, infatti:

n = 10

k = 3

n! = 10!

(n - k) = (10 - 2)! = 8!

k! = 2! = 2 · 1 = 2

Da cui

10!/(2! 8!) = 45

La stessa formuletta ha la stessa facilità a risolvere il caso più complicato di 10 numeri presi a gruppi di 3:

10!/(3!7!) = 120

Un numero piuttosto alto, estremamente difficile da determinare lavorando con la forza bruta...

Il simbolo che lo indica è quello riportato di seguito che corrisponde a quanto trovato con i fattoriali: