Llibre de probabilitat
Combinatòria i tècniques de recompte
La combinatòria és la part de les matemàtiques que estudia els problemes que es plantegen quan volem conèixer el nombre d’agrupacions o configuracions que es poden formar a partir d’un determinat col·lectiu d’elements (conjunt d’objectes, persones...). Les dues característiques que haurem de tenir en compte a l’hora d’estudiar els diferents tipus d’agrupacions possibles són:
- Els elements del conjunt que hauran d’aparèixer en cada configuració
- L’ordre dels elements en les configuracions
Disposem de diversos mètodes per calcular el nombre total d’agrupacions possibles:
- Els diagrames d’arbre
- Les fórmules combinatòries
Els diagrames en arbre
Exemple 1
En un restaurant ens deixen triar entre 3 primers plats, 2 segons i 4 postres. Volem saber de quantes formes diferents els podem escollir per fer un menú de 1r plat, 2n plat i postre.
Podem escollir entre 3 primers plats; per a cada primer plat, poden escollir entre 2 segons; i per a cada segon, poden escollir entre 4 postres. Podem fer el recompte de la manera següent:
- Suposem que els 3 primers plats són: a, b i c
- Suposem que els 2 segons plats són: d i e
- Suposem que els 4 postres són: f, g, h i i
i fem el diagrama en arbre següent:
En aquest arbre, de cadascuna de les 3 branques inicials, en surten 2 branques i, de cadascuna d'aquestes 2, en surten 4. Per tant, hi haurà, encara que no les dibuixem totes, 3·2·4 = 24 branques finals, que vol dir que hi haurà 24 menús possibles.
Combinatòria
Els arbres són d'utilitat per resoldre problemes de combinatòria quan la complexitat del problema no és molt gran, o quan ens conformem amb fer-nos un esquema, de vegades incomplet, que ens condueixi a la solució.
En la majoria de problemes, però, els arbres són inaplicables quan el nombre de branques esdevé immensa. Aleshores, cal utilitzar les fórmules combinatòries.
Distingirem cinc tipus de problemes:
- Combinacions sense repetició
- Permutacions sense repetició
- Permutacions amb repetició
- Variacions amb repetició
- Variacions sense repetició
Exemple 2
Disposem de 4 llapis de colors diferents: vermell, verd, blau i groc.
Volem fer dibuixos de 3 franges verticals, cada franja d'un sol color i sense repetir cap color, quants dibuixos diferents podrem fer?
Exemple 3
Disposem de 4 sucs de fruites: maduixa, préssec, raïm i taronja. Els volem barrejar de 2 en 2 per fer diferents còctels de fruites (sense alcohol, eh?). De quantes maneres diferents ho podem fer?
Exemple 4
Tenim 3 tampons amb les lletres a, m i u. Volem saber quantes paraules de 3 lletres podem estampar amb aquests 3 tampons, tinguin o no significat.
Exemple 5
A casa tenim tres animals: un gat, un ocell i una tortuga. Volem saber de quantes maneres diferents podem escriure una llista dels noms de les nostres mascotes.
En aquest esquema queda recollit el procediment general:
Seguint aquest procediment amb els exemples anteriors:
- Combinacions sense repetició → exemple 3
- Permutacions sense repetició → exemple 5
- Permutacions amb repetició
- Variacions amb repetició → exemple 4
- Variacions sense repetició → exemple 2