Combinatòria i tècniques de recompte: variacions, estrelles i barres, inclusió-exclusió

Comptar sembla fàcil fins que et poses. La dificultat de la combinatòria no és calcular factorials: és triar el model correcte, i per fer-ho cal respondre sempre les mateixes tres preguntes. Importa l'ordre? Es pot repetir? Els objectes són distingibles? Amb aquestes tres respostes, la fórmula ve sola; sense elles, no hi ha fórmula que et salvi.

Els dos principis bàsics

Si dues alternatives són disjuntes, se sumen les quantitats. Si una construcció té etapes i cada elecció inicial admet el mateix nombre d'extensions, es multipliquen. Aquesta condició de «el mateix nombre» és essencial: quan el nombre d'extensions depèn del que hagis triat abans, no pots multiplicar directament i cal separar en casos i sumar.

Amb això ja surten les fórmules bàsiques. Les llistes ordenades de longitud $k$ sobre $n$ símbols són $n^{k}$ si es pot repetir i $n!/(n-k)!$ si no. I els subconjunts de mida $k$ són

$$\binom{n}{k} = \frac{n!}{k!\,(n-k)!},$$

perquè cada subconjunt s'ha comptat $k!$ vegades a la llista ordenada, una per cada manera d'ordenar-lo. Aquesta divisió per corregir un sobrecomptatge és el mecanisme més reutilitzat de tota la combinatòria.

Si hi ha repeticions prescrites, amb $n_1 + \cdots + n_r = n$ còpies de cada tipus, les ordenacions diferents són $n!/(n_1!\cdots n_r!)$: mateix argument, dividint pel sobrecomptatge de cada grup d'iguals.

Estrelles i barres

El nombre de solucions enteres no negatives de $x_1 + \cdots + x_k = n$ és

$$\binom{n+k-1}{k-1}.$$

La imatge que ho explica: representa les $n$ unitats com a estrelles en fila i posa-hi $k-1$ barres per separar-les en $k$ grups. Cada disposició de $n$ estrelles i $k-1$ barres dona una solució i viceversa; per tant només cal triar on van les barres entre les $n+k-1$ posicions.

Si totes les variables han de ser estrictament positives i $n \geq k$, fes el canvi que resta $1$ a cadascuna i queda la mateixa fórmula amb $n-k$ en comptes de $n$, és a dir $\binom{n-1}{k-1}$.

Inclusió-exclusió

Quan els conjunts que vols comptar se superposen, restar els casos prohibits directament sobrecorregeix. La fórmula que ho arregla és

$$\left|\bigcup_{i=1}^{m}A_i\right| = \sum_i |A_i| - \sum_{i<j}|A_i\cap A_j| + \cdots + (-1)^{m+1}|A_1\cap\cdots\cap A_m|.$$

La demostració és elegant: un element que pertany a exactament $r$ dels conjunts es compta, en total, $\sum_{j=1}^{r}(-1)^{j+1}\binom{r}{j}$ vegades, i aquesta suma val exactament $1$ pel binomi de Newton. Cada element del cantó esquerre es compta una vegada i cap element de fora es compta.

Una aplicació directa: el nombre d'aplicacions exhaustives d'un conjunt de $n$ elements sobre un de $k$ és

$$\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}.$$

Es llegeix com «totes les aplicacions, menys les que ometen algun valor, corregint les que n'ometen dos, i així successivament».

El principi del colomar

Si reparteixes $N$ objectes en $k$ caixes, alguna caixa conté com a mínim $\lceil N/k\rceil$ objectes. És gairebé trivial d'enunciar i sorprenentment potent: garanteix existència sense dir quina caixa, que és exactament el que es necessita en molts arguments.

Exemple clàssic: en un grup de $13$ persones, almenys dues fan anys el mateix mes. No cal saber res més sobre les persones.

Funcions generadores

Una successió es pot codificar com una sèrie formal de potències, on el coeficient de cada grau és el terme corresponent. En context formal no cal parlar de convergència: es manipulen coeficients.

La propietat que ho fa útil és que multiplicar sèries correspon a convolucionar successions, i això converteix problemes de recompte amb restriccions en càlculs de coeficients. Per exemple, el coeficient de $z^{10}$ en $(1+z+z^{2})^{5}$ compta les solucions de $x_1+\cdots+x_5 = 10$ amb cada variable entre $0$ i $2$: cada factor representa una variable i les potències disponibles són els valors que pot prendre.

Exercici resolt: aplicacions exhaustives

Quantes aplicacions exhaustives hi ha d'un conjunt de $4$ elements sobre un de $3$?

Total sense restriccions: cada element tria lliurement entre $3$ imatges, o sigui $3^{4} = 81$.

Restem les que ometen algun valor. Hi ha $3$ maneres de triar el valor omès, i llavors queden $2^{4} = 16$ aplicacions: $3\cdot 16 = 48$.

Corregim. Les aplicacions que ometen dos valors s'han restat dues vegades, o sigui que cal tornar-les a sumar: $3$ maneres de triar els dos omesos, i $1^{4} = 1$ aplicació cada vegada, o sigui $3$.

$$81 - 48 + 3 = 36.$$

Comprovació independent. Amb $4$ elements i $3$ imatges totes assolides, la distribució de mides ha de ser $2+1+1$. Tries quins dos elements van junts ($\binom{4}{2} = 6$) i després assignes els tres grups als tres valors ($3! = 6$): $6\cdot 6 = 36$. Coincideix.

Exercici resolt: paraules amb lletres repetides

Quants anagrames diferents té la paraula MATEMATICA?

Té $10$ lletres. Comptem les repeticions: A apareix $3$ vegades, M i T dues cadascuna, i E, I, C una sola vegada.

$$\frac{10!}{3!\,2!\,2!} = \frac{3\,628\,800}{6\cdot 2\cdot 2} = \frac{3\,628\,800}{24} = 151\,200.$$

D'on surt la divisió. Si les deu lletres fossin totes diferents hi hauria $10!$ ordenacions. Però intercanviar les tres A entre elles dona la mateixa paraula, i això passa de $3!$ maneres; igual amb les dues M i les dues T. Es divideix pel sobrecomptatge de cada grup.

És exactament el mateix argument que justifica el coeficient binomial, aplicat a més d'un grup alhora.