T53. Combinatòria. Aplicacions

Desarrollo del tema

# COMBINATÒRIA. NOMBRES COMBINATORIS. APLICACIONS

## 1. Introducció

La **combinatòria** és la branca de les matemàtiques que estudia les diferents maneres d'agrupar elements d'un conjunt. Es tracta de comptar possibilitats sense haver-les d'enumerar totes. Té aplicacions fonamentals en probabilitat, teoria de grafs, criptografia, informàtica i estadística.

## 2. Principis Fonamentals del Recompte

### 2.1 Principi de la suma (o addició)

Si una tasca es pot fer de $n_1$ maneres o bé de $n_2$ maneres (mútuament excloents), llavors es pot fer de $n_1 + n_2$ maneres en total.

**Exemple:** Si hi ha 3 carreteres per anar de A a B i 2 carreteres per anar de A a C, hi ha $3 + 2 = 5$ maneres d'anar de A a B o a C.

**Forma general:** Si $A_1, A_2, \ldots, A_k$ són conjunts disjunts: $$|A_1 \cup A_2 \cup \cdots \cup A_k| = |A_1| + |A_2| + \cdots + |A_k|$$

### 2.2 Principi del producte (o multiplicació)

Si una tasca es pot descompondre en dues etapes, la primera de les quals es pot fer de $n_1$ maneres i la segona de $n_2$ maneres (per a cada elecció de la primera), llavors la tasca es pot fer de $n_1 \cdot n_2$ maneres.

**Exemple:** Si hi ha 3 pantalons i 5 camises, hi ha $3 \cdot 5 = 15$ conjunts possibles.

**Forma general:** Per a $k$ etapes: $$n_1 \cdot n_2 \cdot \ldots \cdot n_k$$

### 2.3 Principi del complement

Per comptar els elements que satisfan una propietat, pot ser més fàcil comptar els que NO la satisfan: $$|A| = |U| - |A^c|$$

### 2.4 Principi d'inclusió-exclusió

Per a dos conjunts: $$|A \cup B| = |A| + |B| - |A \cap B|$$

Forma general per a $n$ conjunts: $$\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots$$

## 3. Factorial i Nombres Combinatoris

### 3.1 Factorial

El **factorial** de $n$ (enter no negatiu) es defineix: $$n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$$

Per conveni: $0! = 1$

**Propietats:** - $n! = n \cdot (n-1)!$ (definició recursiva) - Creixement molt ràpid: $10! = 3.628.800$

### 3.2 Nombres combinatoris (coeficients binomials)

El **nombre combinatori** o coeficient binomial es defineix: $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

on $0 \leq k \leq n$.

**Propietats:** 1. $\binom{n}{0} = \binom{n}{n} = 1$ 2. $\binom{n}{1} = \binom{n}{n-1} = n$ 3. **Simetria:** $\binom{n}{k} = \binom{n}{n-k}$ 4. **Fórmula de Pascal:** $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ 5. **Suma per files:** $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ 6. **Suma alternada:** $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$

### 3.3 Triangle de Pascal

Disposició dels nombres combinatoris on cada nombre és la suma dels dos superiors:

``` 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 ```

## 4. Variacions

### 4.1 Variacions ordinàries (sense repetició)

Agrupacions **ordenades** de $m$ elements triats d'un conjunt de $n$ elements, **sense repetir**.

$$V_{n,m} = \frac{n!}{(n-m)!} = n(n-1)(n-2)\cdots(n-m+1)$$

**Exemple:** Quantes paraules de 3 lletres diferents es poden formar amb A, B, C, D, E? $$V_{5,3} = 5 \cdot 4 \cdot 3 = 60$$

### 4.2 Variacions amb repetició

Agrupacions ordenades de $m$ elements triats d'un conjunt de $n$, **podent repetir**.

$$VR_{n,m} = n^m$$

**Exemple:** Quantes paraules de 3 lletres (podent repetir) amb A, B, C, D, E? $$VR_{5,3} = 5^3 = 125$$

## 5. Permutacions

### 5.1 Permutacions ordinàries

Agrupacions ordenades que contenen **tots** els $n$ elements d'un conjunt (cas particular de variacions amb $m = n$):

$$P_n = n!$$

**Exemple:** De quantes maneres es poden ordenar 5 persones en una fila? $$P_5 = 5! = 120$$

### 5.2 Permutacions amb repetició

Si tenim $n$ objectes amb $n_1$ iguals d'un tipus, $n_2$ d'un altre, etc., on $n_1 + n_2 + \cdots + n_k = n$:

$$PR_n^{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1! \cdot n_2! \cdots n_k!}$$

**Exemple:** Quants anagrames té MISSISSIPPI? - 11 lletres: M(1), I(4), S(4), P(2) $$PR_{11}^{1,4,4,2} = \frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{39916800}{1 \cdot 24 \cdot 24 \cdot 2} = 34650$$

### 5.3 Permutacions circulars

Ordenacions al voltant d'una taula rodona (es considera la mateixa ordenació si només difereix en una rotació):

$$PC_n = (n-1)!$$

**Exemple:** De quantes maneres es poden asseure 6 persones en una taula rodona? $$PC_6 = 5! = 120$$

## 6. Combinacions

### 6.1 Combinacions ordinàries

Agrupacions **no ordenades** de $m$ elements triats de $n$, sense repetició:

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

**Exemple:** Quants comitès de 3 persones es poden formar amb 10 candidats? $$C_{10,3} = \binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120$$

### 6.2 Combinacions amb repetició

Agrupacions no ordenades de $m$ elements triats de $n$, **podent repetir**:

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

**Exemple:** De quantes maneres es poden repartir 10 caramels idèntics entre 4 nens? $$CR_{4,10} = \binom{4+10-1}{10} = \binom{13}{10} = 286$$

## 7. Taula Resum

| Tipus | Repetició | Ordre | Fórmula | |-------|-----------|-------|---------| | Variacions | No | Sí | $V_{n,m} = n!/(n-m)!$ | | Variacions | Sí | Sí | $VR_{n,m} = n^m$ | | Permutacions | No | Sí | $P_n = n!$ | | Permutacions | Sí | Sí | $PR = n!/(n_1! \cdots n_k!)$ | | Combinacions | No | No | $C_{n,m} = \binom{n}{m}$ | | Combinacions | Sí | No | $CR_{n,m} = \binom{n+m-1}{m}$ |

## 8. Binomi de Newton

### 8.1 Teorema del binomi

Per a qualsevol $a, b \in \mathbb{R}$ i $n \in \mathbb{N}$:

$$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$$

**Terme general:** $$T_{k+1} = \binom{n}{k} a^{n-k} b^k$$

### 8.2 Casos particulars

$$(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k = 1 + nx + \binom{n}{2}x^2 + \cdots + x^n$$

Si $x = 1$: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Si $x = -1$: $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$

### 8.3 Trinomi i multinomi

$$(a+b+c)^n = \sum_{i+j+k=n} \frac{n!}{i!j!k!} a^i b^j c^k$$

Els coeficients $\frac{n!}{n_1! n_2! \cdots n_k!}$ són els **coeficients multinomials**.

## 9. Aplicacions

### 9.1 Probabilitat

Si tots els resultats són equiprobables: $$P(A) = \frac{\text{casos favorables}}{\text{casos possibles}}$$

La combinatòria permet comptar ambdós sense enumerar.

**Exemple:** Probabilitat de pòquer (4 cartes iguals + 1): $$P = \frac{\binom{13}{1} \cdot \binom{4}{4} \cdot \binom{12}{1} \cdot \binom{4}{1}}{\binom{52}{5}} = \frac{13 \cdot 1 \cdot 12 \cdot 4}{2598960} \approx 0.00024$$

### 9.2 Teoria de grafs

- Nombre de grafs simples amb $n$ vèrtexs: $2^{\binom{n}{2}}$ (cada aresta pot existir o no) - Nombre de camins hamiltonians: $(n-1)!/2$ en un graf complet

### 9.3 Informàtica i criptografia

- Nombre de subconjunts d'un conjunt de $n$ elements: $2^n$ - Contrasenyes de $k$ caràcters d'un alfabet de $n$ símbols: $n^k$

## 10. Problemes Clàssics

### 10.1 Problema del repartiment

Repartir $n$ objectes idèntics en $k$ urnes: $CR_{k,n} = \binom{k+n-1}{n}$

### 10.2 Nombres de Stirling

- **Primera espècie $s(n,k)$:** Nombre de permutacions de $n$ elements amb $k$ cicles - **Segona espècie $S(n,k)$:** Nombre de maneres de particionar $n$ elements en $k$ subconjunts no buits

### 10.3 Nombres de Catalan

$$C_n = \frac{1}{n+1} \binom{2n}{n}$$

Compten: parèntesis correctament aparellats, camins de Dyck, triangulacions d'un polígon, arbres binaris...

## 11. Aplicacions Didàctiques

### 11.1 A l'ESO

- Problemes de recompte amb diagrames d'arbre - Loteries i jocs de cartes senzills - Contrasenyes i codis PIN

### 11.2 Al Batxillerat

- Formalització amb fórmules - Demostració del binomi de Newton - Connexió amb probabilitat - Programació d'algorismes combinatoris

## 12. Conclusions

La combinatòria proporciona eines potents per comptar sense enumerar. Els principis fonamentals (suma, producte) i les fórmules de variacions, permutacions i combinacions permeten resoldre una gran varietat de problemes de recompte, amb aplicacions directes en probabilitat, informàtica i moltes altres àrees.