Combinatòria Ll 1

Aquesta lliçó analitzarà la combinatòria analitzant les construccions de les eines més habituals.

La selecció

Hi ha dos tipus de fer seleccions successives sobre un conjunt. La primera selecció sempre serà la mateixa.

Donat un recipient fosc amb 7 tipus de boles, totes diferents. Per treure la primera bola sempre hi haurà les 7 possibilitats inicials.

Exemple:

1) La quantitat de possibilitats d'escollir una bola d'una bossa fosca amb boles numerades del valor 1 al valor m sempre seran m possibilitats.

Hem de pensar que la m és el nombre màxim de boles amb el benentès que si m=2 vol dir que a tota la bossa només hi ha 2 boles. Qui diu bossa pot dir qualsevol tipus de recipient que no deixa veure l'interior d'aquest i per tant tot tipus de selecció pot ser possible.

2) La quantitat de possibilitats que apareixen en llençar un dau de 6 cares de diferent valor són 6 possibilitats.

3) La quantitat de xifres que podem fer amb una vàlvula nixie que representa xifres del 0 al 9 són 10 possibilitats.

Amb seleccions successives tenim:

Elecció o extracció d'un segon element sense restitució:

	$\to$				$\to$
Cada cop que s'extreu una bola la següent extracció té una possibilitat menys.

Elecció o extracció d'un segon element amb restitució:

	$\to$				$\to$
Cada cop que s'extreu una bola, es retorna dins, i la següent extracció té les mateixes possibilitats.

Diagrames d'arbre

Els diagrames d'arbre pretenen esquematitzar tot tipus de selecció i per tant estudia tot tipus de selecció d'elements.

Tot diagrama d'arbre comença per un nus buit. De tot nus surten tantes branques com eleccions diferents hi ha.

Exemple...

Exercici quiniela de futbol.

Variacions amb repetició

Definició: Una variació amb repetició de m elements és el nombre de variants ordenades diferents que podem fer escollint, amb restitució, n elements cada cop.

Exemple explicatius de n elements...

V R_{m, n} = \underset{n}{\underset{⏟}{m \times \dots \times m}} = m^{n}

Exercicis...

Variacions ordinàries

Definició: Una variació ordinària de m elements és el nombre de variants ordenades diferents que podem fer escollint, sense restitució, n elements cada cop.

Exemple explicatius de n elements...

V_{m, n} = \underset{n}{\underset{⏟}{m \times (m - 1) \times (m - 2) \times \dots \times (m - (n - 1))}}

Exercicis:

1) Quantes possibles variants ordenades podem obtenir agafant dos boles, sense restitució, d'una bossa amb boles de 4 colors diferents?

Suposem que els colors són vermell, verd, blau i groc, llavors el seu diagrama d'arbre és:

Arbre	Resultat

A la primera elecció hi ha 4 possibilitats.

A la segona elecció hi ha només 3 possibilitats.

Per tant el nombre total de possibilitats és $4 \times 3 = 12$ variants ordenades.

Repte...

Permutacions

Definició: Les "permutacions ordinàries" de m elements és el nombre de variants (permutacions) ordenades diferents que podem fer escollint, sense restitució, els m elements.

P_{m} = m! = V_{m}^{m}

Exemples...

Exercicis...

Permutacions amb repetició

Definició: Les "permutacions amb repetició" de m elements és el nombre de variants ordenades diferents que podem fer escollint, sense restitució i amb certs elements indistingibles, els m elements.

P_{m}^{a, b, \dots} = \frac{m!}{a! \times b! \times \dots}

Exemples...

Exercicis...

Combinatòria Ll 1

Contents