Combinatòria

L'art de comptar sense comptar

Formació d'Aprofundiment en Probabilitat per a Professorat

Mapa de la Combinatòria

Reptes inicials ▶ 1. Variacions amb Repetició ($VR_{m,n}$) ▶ 2. Variacions sense Repetició ($V_{m,n}$) ▶ 3. Permutacions ($P_n$) ▶ 4. Els Misteris del Factorial ($n!$) ▶ 5. Combinacions ($C_{m,n}$) ▶ Propietats del nombre combinatori $\binom{m}{n}$ ▶ El triangle de Tartàglia i el binomi de Newton ▶ La Màquina Enigma i el seu càlcul ▶ Ciberseguretat: Força Bruta vs Longitud ▶

1. Quants pins possibles podem fer amb un cadenat de 4 xifres del 0 al 9?
2. Quants passwords amb 6 caràcters podem fer fent servir les lletres a, b i c?
3. Llancem un dau i una moneda. Quants resultats possibles podem obtenir?
4. En un menú d'un restaurant podem escollir:
- De primer: amanida, gaspatxo o macarrons
- De segon: fricandó o llenguado
- De postres: flam, gelat, mató o trufes.
Quants menús diferents es poden demanar?
5.Llancem una moneda de 10 cèntims i una de 50. Quantes possibles solucions hi poden haver? I si en llamcem dues d'un euro?
6. Es fa una cursa on participen 30 persones. Es repartirà medalla d'or a qui arribi primer, plata al segon i bronze al tercer. Quants podis possibles hi podrien haver?
7. Un grup musical ha composat 11 cançons. De quantes maneres diferents les pot ordenar per elaborar un nou àlbum?
8. Quantes banderes diferents podem fer amb tres bandes horitzontals de colors diferents si tenim 8 colors disponibles? I si podem repetir colors?
9. En un equip d’handbol de 9 membres s’ha de repartir els números de samarreta de l'1 al 20. Tenint en compte que el número 1 es destina al porter, de quantes maneres es pot fer el repartiment?
10. D'una classe de 30 persones cal fer un grup de 5 persones. Quants grups possibles es poden fer?
11. Disposem de 10 parèntesis esquerres "(" i 10 parèntesis drets ")". De quantes maneres es poden col·locar correctament?

Exemple: La seqüència ( ( ( ( ( ( ( ( ( ( ) ) ) ) ) ) ) ) ) ) és correcta, i la seqüència ( ( ) ) ) ) ( ( ( no.

Repte 1: Quants pins possibles podem fer amb un cadenat de 4 xifres del 0 al 9?

Repte 2: Quants passwords amb 6 caràcters podem fer fent servir les lletres a, b i c?

Repte 3: Llancem un dau i una moneda. Quants resultats possibles podem obtenir?

Repte 4: En un menú podem escollir: 3 primers, 2 segons i 4 postres. Quants menús diferents es poden demanar?

Repte 5: Llancem una moneda de 10 cèntims i una de 50. Quantes possibles solucions hi poden haver? I si en llancem dues d'un euro?

Repte 6 (El Podi): Es fa una cursa amb 30 persones. Medalla d'or al primer, plata al segon i bronze al tercer. Quants podis possibles hi ha?

Repte 7 (L'Àlbum): Un grup ha composat 11 cançons. De quantes maneres les pot ordenar per a l'àlbum?

Repte 8 (Les Banderes): Banderes de 3 bandes horitzontals usant 8 colors. Sense repetir colors? I si podem repetir?

Repte 9 (Handbol): Equip de 9. El porter té el nº1. Queden 8 jugadors i els números del 2 al 20 (19 disponibles). Quants repartiments hi ha?

Repte 10 (El Grup): D'una classe de 30 persones cal fer un grup de 5. Quants grups possibles es poden fer?

Repte 11 (Els Parèntesis): 10 "(" i 10 ")". De quantes maneres es poden col·locar formant una seqüència correcta?

El tancament: Què hem après de la nostra lluita amb les pissarres?

L'Ordre dels factors

De vegades intercanviar els elements crea un resultat nou (passwords, podis). D'altres vegades, l'ordre és una il·lusió geomètrica i no importa gens (grups de 5 persones).

La Disponibilitat

Ens calen tots els elements per construir el resultat (ordenar les 11 cançons de l'àlbum), o només en seleccionem uns quants deixant-ne fora la majoria (3 atletes d'un grup de 30)?

El Reposatori

Podem repetir l'opció anterior com si tinguéssim subministrament infinit (PINs, Passwords), o el fet d'escollir un element l'elimina de la llista per sempre (Samarretes, Menús)?

⚠️ I l'advertència final...

Comptar pot arribar a ser extremadament difícil quan hi ha regles dinàmiques pel mig (com els parèntesis tancant-se abans d'hora). Necessitem eines visuals i algebraiques per no perdre'ns!

La Gran Eina Visual: Mou el ratolí d'esquerra a dreta per anar construint l'arbre.

El Principi Multiplicatiu: comptatge de branques

Aplicació al Repte 2: Ara tenim 3 opcions (a, b, c)

Aplicació al Repte 4 (Els Menús): 3 Primers, 4 Segons i 2 Postres. Bases variables!

Aplicació al Repte 6 (El Podi): 30 atletes per a 3 medalles. No hi ha repetició!

El Repte de l'àlbum: Hem d'ordenar 11 cançons!

El Dilema (Repte 8): I si assignem els Jugadors a les Samarretes? (Model: 5 Samarretes, 3 Jugadors).

La Solució Elegant (Repte 8): Els 11 Jugadors trien entre les 25 Samarretes. Simetria recuperada!

És com el podi! Qui són els corredors i qui les medalles?

El Repte 10 (L'ordre no importa): 30 persones, n'escollim 5. Quantes llistes idèntiques estem repetint?

1. Escollim amb ordre

2. Desordenem els 5 (Repeticions)

1. Variacions amb Repetició ($VR_{m,n}$):

¿De quantes maneres podem escollir $n$ elements de $m$ possibles si els podem repetir i l'ordre importa?

2. Variacions sense Repetició ($V_{m,n}$):

De quantes maneres podem escollir $n$ elements de $m$ possibles si NO els podem repetir i l'ordre importa?

3. Permutacions ($P_n$):

De quantes maneres podem ORDENAR $n$ elements sense repetir-ne cap (és a dir, utilitzant-los tots)?

El Factorial ($n!$): Molt més que multiplicar

Ara que sabem que $n! = n \cdot (n-1) \cdot \dots \cdot 3 \cdot 2 \cdot 1$, resolem aquests petits misteris.

$1! = 1$

$0! = 1$

$\frac{m!}{(m-1)!} = m$

$V_{m,n} = \frac{m!}{(m-n)!}$

$(-3)! \rightarrow \text{NO}$

0. Un creixement explosiu!

Busca la tecla x! a la teva calculadora. Provem-la:

$5! = 120$ $10! = 3.628.800$

$20! \approx 2,43 \times 10^{18}$

El límit de la calculadora: Sabies que una estàndard només arriba a $69!$ ?
(El $70!$ supera la xifra de $10^{100}$ i fa "Math Error").

0. Un creixement explosiu! (cont.)

El factorial guanya gairebé sempre: $\quad \mathbf{n! > a^n}$

Per molt gran que sigui la base $a$ (per exemple $1000^n$), tard o d'hora el factorial creixerà més.

Existeix alguna expressió que creixi MÉS ràpid?

Sí! Expressions com $\mathbf{n^n}$, o $\mathbf{n!^{n!}}$, o les terrorífiques Tetracions (${^{n}n} = n^{n^{n...}}$).

1. Quant val $1!$ ?

$1! = 1$

2. I quant val $0!$ ?

$0! = 1$

De quantes maneres podem ordenar $0$ elements? D'1 sola manera: no fent res. És una necessitat matemàtica!

3. Simplifiquem la fracció!

$\frac{m!}{(m-1)!} =$

$\frac{m \cdot (m-1) \cdot (m-2) \cdot \dots \cdot 2 \cdot 1}{(m-1) \cdot (m-2) \cdot \dots \cdot 2 \cdot 1}$

$= \require{cancel} \frac{m \cdot \cancel{(m-1)} \cdot \cancel{(m-2)} \cdot \dots \cdot \cancel{2} \cdot \cancel{1}}{\cancel{(m-1)} \cdot \cancel{(m-2)} \cdot \dots \cdot \cancel{2} \cdot \cancel{1}} = \mathbf{m}$

4. La fórmula de les Variacions!

Com escurcem $V_{m,n} = m \cdot (m-1) \cdot \dots \cdot (m-n+1)$ ?

Multipliquem dalt i baix per la "cua" que falta fins a l'1: $\mathbf{(m-n)!}$

$V_{m,n} = \frac{m \cdot (m-1) \cdot \dots \cdot (m-n+1) \color{#d97706}{\cdot (m-n)!}}{\color{#d97706}{(m-n)!}}$

$V_{m,n} = \frac{m!}{(m-n)!}$

5. Existeix $(-3)!$ ?

No podem anar restaurant elements d'1 en 1 des d'un nombre negatiu per acabar arribant a l'1. No té cap sentit lògic!

6. I què passa amb els decimals?

Existeix $1.5!$ ?

SÍ!
($\approx 1.329$)

Existeix $\pi!$ ?

SÍ!
($\approx 7.188$)

Hi ha una increïble eina de matemàtiques avançades anomenada Funció Gamma $\Gamma(x)$ que aconsegueix estendre el factorial a qualsevol nombre!

4. Combinacions ($C_{m,n}$): Quan l'ordre NO importa

Repte 10: De quantes maneres podem escollir un equip de $5$ persones d'entre $30$ possibles sense assignar-los cap posició?

1r. Ordre importa: $V_{30,5}$

2n. Repeticions: $P_5$

$C_{m,n} = \frac{V_{m,n}}{P_n}$

1r Pas: Comptem-ho tot (incloent l'ordre)

De moment, calculem les maneres d'escollir 5 persones donant-los una posició al camp (porter, defensa, mig...). Això ja sabem fer-ho: són les Variacions!

$V_{30,5}$

2n Pas: Detectem les repeticions

Com que no volem posicions, l'equip "A-B-C-D-E" i "E-D-C-B-A" són exactament el mateix. Quantes vegades s'ha repetit cada grup? Tantes com maneres tinguem d'ordenar 5 persones!

$P_5$

3r Pas: La Divisió Màgica

Per trobar la xifra real, només cal dividir el total d'equips ordenats per la quantitat de vegades que s'ha repetit cadascun.

$C_{30,5} = \frac{\color{#10b981}{V_{30,5}}}{\color{#8b5cf6}{P_5}}$

$\rightarrow$

$C_{m,n} = \frac{\color{#10b981}{V_{m,n}}}{\color{#8b5cf6}{P_n}}$

4t Pas: La Fórmula Final!

I si substituïm la $\color{#10b981}{V_{m,n}}$ i la $\color{#8b5cf6}{P_n}$ pels factorials que acabem d'aprendre a la diapositiva anterior?

$C_{m,n} = \frac{\frac{\color{#10b981}{m!}}{\color{#10b981}{(m-n)!}}}{\color{#8b5cf6}{n!}}$

$=$

$\mathbf{\frac{m!}{n!(m-n)!}}$

El Nombre Combinatori $\binom{m}{n}$

A les combinacions se les acostuma a anomenar Nombres Combinatoris i s'escriuen: $\mathbf{C_{m,n} = \binom{m}{n}}$. Es llegeix "m sobre n".

$\binom{m}{m} = 1$

$\binom{m}{1} = m$

$\binom{m}{0} = 1$

$\binom{m}{n} = \binom{m}{m-n}$

$\binom{m}{m} = \color{#10b981}{?}$

$\binom{m}{m} = 1$

De $m$ elements, quantes maneres tenim d'escollir-ne $m$?
Només una: escollir-los tots!

$\binom{m}{1} = \color{#0ea5e9}{?}$

$\binom{m}{1} = m$

De $m$ elements, quantes maneres tenim d'escollir-ne només 1?
Doncs $m$ maneres. Tantes com individus tinguem!

$\binom{m}{0} = \color{#8b5cf6}{?}$

$\binom{m}{0} = 1$

De $m$ elements, de quantes maneres puc no escollir-ne cap?
Només d'una manera: no escollint-ne cap.

$\binom{m}{n} = \binom{m}{m-n}$

Per què? Perquè cada vegada que escollim els $n$ que juguen (blaus),
automàticament estem escollint els $m-n$ que es queden a la banqueta (vermells).

Són exactament la mateixa quantitat de combinacions!

PROPIETAT EXTRA DEDUÏDA:

$\binom{m}{m-1} = \binom{m}{1} = \mathbf{m}$

Com passa en triar 29 de 30: escollir la gran majoria és exactament el mateix que escollir a qui deixes fora.

$\binom{m}{n} = \binom{m-1}{n} + \binom{m-1}{n-1}$

Fixem-nos en una persona concreta de les $m$ possibles (per exemple, la Maria). Totes les combinacions possibles es divideixen en dos grups:

1. La Maria NO juga: Ens toca triar els $n$ jugadors d'entre els $m-1$ restants $\rightarrow \mathbf{\binom{m-1}{n}}$

2. La Maria SÍ juga: Ara només ens falta triar els $n-1$ llocs restants d'entre els $m-1$ jugadors que queden $\rightarrow \mathbf{\binom{m-1}{n-1}}$

El Triangle de Tartàglia (o de Pascal)

Què passa si apilem tots els nombres combinatoris $\binom{m}{n}$ separant-los pel seu nivell $m$? Es forma una piràmide amb propietats màgiques!

m=0

$\binom{0}{0}$ 1

m=1

$\binom{1}{0}$ 1

$\binom{1}{1}$ 1

m=2

$\binom{2}{0}$ 1

$\binom{2}{1}$ 2

$\binom{2}{2}$ 1

m=3

$\binom{3}{0}$ 1

$\binom{3}{1}$ 3

$\binom{3}{2}$ 3

$\binom{3}{3}$ 1

m=4

$\binom{4}{0}$ 1

$\binom{4}{1}$ 4

$\binom{4}{2}$ 6

$\binom{4}{3}$ 4

$\binom{4}{4}$ 1

m=5

$\binom{5}{0}$ 1

$\binom{5}{1}$ 5

$\binom{5}{2}$ 10

$\binom{5}{3}$ 10

$\binom{5}{4}$ 5

$\binom{5}{5}$ 1

m=6

$\binom{6}{0}$ 1

$\binom{6}{1}$ 6

$\binom{6}{2}$ 15

$\binom{6}{3}$ 20

$\binom{6}{4}$ 15

$\binom{6}{5}$ 6

$\binom{6}{6}$ 1

m=7

$\binom{7}{0}$ 1

$\binom{7}{1}$ 7

$\binom{7}{2}$ 21

$\binom{7}{3}$ 35

$\binom{7}{4}$ 35

$\binom{7}{5}$ 21

$\binom{7}{6}$ 7

$\binom{7}{7}$ 1

El Binomi de Newton

Volem una expressió per resoldre directament $\mathbf{(a+b)^n}$.

1. Comencem per una cosa ben coneguda

$(a+b)^2 = (a+b) \cdot (a+b) = a^2 + 2ab + b^2$

Aquesta és la Identitat Notable que coneixeu de memòria.
Surt de desfer els parèntesis multiplicant-ho tot directament.

2. Què passa amb la potència 3?

$(a+b)^3 = (a+b) \cdot (a+b) \cdot (a+b)$

Per desfer aquests parèntesis, hem d'escollir una lletra de cadascun d'ells.

Ens sortiran termes amb $3\ a$'s, amb $2\ a$'s i $1\ b$, amb $1\ a$ i $2\ b$'s, i amb $3\ b$'s.
Quantes vegades surt cadascun d'ells?

$(a+b)^3 =$ ? 1 $a^3$ $+$ ? 3 $a^2b$ $+$ ? 3 $ab^2$ $+$ ? 1 $b^3$

De quantes maneres podem escollir $3\ a$'s d'entre els $3$ parèntesis?
Doncs només d'1 manera: $\binom{3}{3} = 1$.

I pel terme $a^2b$? De quantes maneres podem escollir $2\ a$'s?
Doncs de 3 maneres: $\binom{3}{2} = 3$ (o $\binom{3}{1}$ si preferim escollir la $b$, que és el mateix!).

I pel terme $ab^2$? Ens cal escollir $1\ a$ (o $2\ b$'s).
També de 3 maneres: $\binom{3}{1} = 3$.

I per tenir $b^3$? Ens cal no escollir cap $a$.
Doncs només d'1 manera: $\binom{3}{0} = 1$.

Meravellós! Els coeficients (1, 3, 3, 1) no són números arbitraris,
són Nombres Combinatoris que ens diuen de quantes maneres s'obté aquell terme!

3. Fem el salt directe a l'exponent 6!

$(a+b)^6 = (a+b)(a+b)(a+b)(a+b)(a+b)(a+b)$

Comencem amb $a^6$: hem d'escollir $6\ a$'s dels 6 parèntesis $\rightarrow \mathbf{\binom{6}{6}}$.
(És indiferent si pensem en escollir $0\ b$'s $\rightarrow \mathbf{\binom{6}{0}}$).

I el terme $a^5b$? Escollim $5\ a$'s dels 6 parèntesis $\rightarrow \mathbf{\binom{6}{5}}$.
(I per simetria, podem pensar en triar la $b$ que falta $\rightarrow \mathbf{\binom{6}{1}}$. Tant és!)

Podem construir tota la fórmula fent aquest raonament per a cada potència!

$(a+b)^6 =$ $\binom{6}{6}a^6$ $+ \binom{6}{5}a^5b$ $+ \binom{6}{4}a^4b^2 + \binom{6}{3}a^3b^3 + \binom{6}{2}a^2b^4 + \binom{6}{1}ab^5 + \binom{6}{0}b^6$

$\mathbf{=} \quad \mathbf{1}a^6 + \mathbf{6}a^5b + \mathbf{15}a^4b^2 + \mathbf{20}a^3b^3 + \mathbf{15}a^2b^4 + \mathbf{6}ab^5 + \mathbf{1}b^6$

Ciberseguretat Actual: Endevinar un Password

Tenim una contrasenya de 20 caràcters (majúscules, minúscules, nombres i símbols). Quant trigarà un ordinador de 8 nuclis a 4.5GHz?

1. Quantes combinacions possibles hi ha?

Tenim aprox. 95 caràcters disponibles al teclat i una longitud de 20 posicions. Com que els caràcters es poden repetir, calculem les Variacions amb Repetició.

$VR_{95, 20} = 95^{20} \approx 3,58 \times 10^{39} \text{ contrasenyes}$

(Això és un 3 seguit de 39 zeros!)

bruteforce_password.sh

root@pc:~# ./bruteforce_password.sh

> Objectiu: 3.580.000.000.000.000.000... (39 zeros) contrasenyes.

> Llegint maquinari: CPU 8 nuclis @ 4.5 GHz.

> Càlcul velocitat: (8 nuclis) × (4.500.000.000 cicles/s) =

> Velocitat establerta: 36.000.000.000 comprovacions/segon.

root@pc:~# Calculant temps necessari per trencar el password...

>> RESULTAT: $3,15 \times 10^{21}$ ANYS

[ ERROR CRÍTIC ] TEMPS EXCEDIT.
L'edat de l'Univers és de "només" $1,38 \times 10^{10}$ anys. L'ordinador es desintegrarà abans d'endevinar aquesta clau.

La Lliçó: La longitud és la clau

Gràcies a les potències, afegir un sol caràcter a la teva contrasenya multiplica el temps necessari per endevinar-la per 95!

💡 Consell de Ciberseguretat: Per això avui dia es recomana fer servir frases de pas (passphrases) llargues abans que paraules curtes "molt complicades". La longitud venç sempre a la força bruta.

El Càlcul Combinatori de l'Enigma

Comptem exactament quantes configuracions inicials diferents podia tenir la màquina cada matí.

[Rotors] 60

$\times$

[Posicions] 17.576

$\times$

[Plugboard] 150.738.274.937.250

1. Escollir els Rotors

Tenim 5 rotors diferents a la capsa i n'hem d'escollir 3. L'ordre en què els posem dins la màquina importa absolutament per al xifratge.
(Són Variacions sense repetició).

$V_{5,3} = 5 \cdot 4 \cdot 3 = 60$

2. La Posició Inicial

Un cop posats a la màquina, cada un dels 3 rotors es pot girar manualment per començar en qualsevol de les 26 lletres de l'alfabet.
(Són Variacions amb repetició).

$VR_{26,3} = 26 \cdot 26 \cdot 26 = 26^3 = 17.576$

3. El Cablejat del Plugboard

Posem el primer cable:
Hem d'escollir 2 lletres de les 26 disponibles. Com que l'ordre del cable no importa (connectar A-B és el mateix que B-A), fem servir combinacions.

$\binom{26}{2}$

Posem el segon cable:
Ens queden 24 lletres lliures $\rightarrow \binom{24}{2}$. Multipliquem els dos resultats...
Però ALERTA! És igual si poso primer el cable vermell i després el blau, o al revés.
Cal dividir entre l'ordre en què agafem els cables: $2!$

$\frac{\binom{26}{2} \cdot \binom{24}{2}}{2!}$

Per posar els 10 cables que manava l'exèrcit:
Seguim aquesta lògica fins a tenir 20 lletres ocupades per les parelles, i finalment dividim per l'ordre de tots els cables barrejats ($\mathbf{10!}$).

$\frac{\binom{26}{2} \cdot \binom{24}{2} \cdot \binom{22}{2} \cdots \binom{8}{2}}{10!} = 150.738.274.937.250$

Configuracions diferents

$60 \times 17.576 \times 150.738.274.937.250 =$

158.962.555.217.826.360.000

"Aproximadament 159 trilions. Trencar aquest codi va requerir combinar el cervell humà amb l'estadística matemàtica de Bletchley Park."

Ordinador Modern vs. Força Bruta

Si provéssim 1 combinació a cada cicle de rellotge, quant trigaria un PC actual a trencar l'Enigma?

bruteforce_enigma.sh

root@pc:~# ./bruteforce_enigma.sh

> Iniciant atac... Objectiu: 158.962.555.217.826.360.000 combinacions.

root@pc:~# Llegint maquinari: CPU 8 nuclis @ 4.5 GHz.

> (8 nuclis) × (4.500.000.000 cicles/s)

> Velocitat: 36.000.000.000 comprovacions/segon.

root@pc:~# Calculant temps (Combinacions ÷ Velocitat)...

> Temps estimat: 4.415.626.533 segons.

>> RESULTAT: 139,92 ANYS

[ ERROR CRÍTIC ] ATAC INVIABLE.
L'exèrcit alemany canvia la configuració de la màquina CADA 24 HORES.

La genialitat de Bletchley Park

Alan Turing no va guanyar fent servir "més potència". Va guanyar usant les Matemàtiques per trobar defectes lògics al codi (com que una lletra mai s'encriptava en ella mateixa) per descartar milions de combinacions de cop sense haver-les de comprovar.