📋 RESUM: Combinatòria i nombres combinatoris
• **Principis**: Suma (o), producte (i), complement, inclusió-exclusió.
• **Factorial**: n! = n·(n-1)·...·1, amb 0! = 1.
• **Coeficient binomial**: C(n,k) = n! / [k!(n-k)!], simetria i Pascal.
• **Variacions sense rep.**: V(n,m) = n!/(n-m)! (ordenades, sense repetir).
• **Variacions amb rep.**: VR(n,m) = nᵐ.
• **Permutacions**: Pₙ = n!, circulars PC = (n-1)!.
• **Perm. amb repetició**: n! / (n₁!·n₂!·...·nₖ!).
• **Combinacions sense rep.**: C(n,m) = binomial, no ordenades.
• **Combinacions amb rep.**: CR(n,m) = C(n+m-1, m).
• **Binomi Newton**: (a+b)ⁿ = Σ C(n,k)·aⁿ⁻ᵏ·bᵏ.
• **Aplicacions**: Probabilitat, grafs, criptografia, contrasenyes.
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.
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$
- 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.
Estudia este tema con OPOSGRATIS
Has leído el desarrollo del tema. Para consolidar tu aprendizaje, estudia las flashcards asociadas con repetición espaciada (algoritmo SM-2), realiza simulacros de examen, y practica el supuesto práctico. Todo gratis y sin registro previo.
