Exercicis de conjunts, aplicacions i relacions

El raonament. El primer element tria entre $7$ imatges; el segon, entre les $6$ que queden lliures; i així fins a acabar:

$7\cdot6\cdots3 = 2520$

Comparació. Aplicacions totals n'hi ha $16807$, o sigui que només una fracció són injectives. I si el conjunt de sortida fos més gran que el d'arribada, no n'hi hauria cap: aquest és el principi del colomar en la seva forma més bàsica.

Cas particular. Quan els dos conjunts tenen la mateixa mida, injectiva, exhaustiva i bijectiva són el mateix, i el recompte dona el factorial.

La fórmula i el seu perquè.

$|A\cup B| = |A| + |B| - |A\cap B| = 12 + 18 - 5 = 25$

En sumar $12$ i $18$, els $5$ elements comuns s'han comptat dues vegades, una en cada conjunt. Restar-los una vegada els deixa comptats exactament un cop.

Comprovacions de coherència. El resultat ha de quedar entre el més gran dels dos ($18$) i la suma ($30$). I la intersecció mai no pot superar el més petit dels dos conjunts.

Amb tres conjunts la fórmula segueix alternant signes: se sumen les tres mides, es resten les tres interseccions dos a dos i es torna a sumar la triple. Aquest és el principi d'inclusió i exclusió general.

El raonament. Construir un subconjunt és prendre $20$ decisions independents, una per element: hi entra o no hi entra. Dues opcions cada vegada, i es multipliquen:

$|\mathcal{P}(A)| = 2^{20} = 1048576$

Comprovació amb casos petits. Un conjunt buit té $1$ subconjunt (ell mateix). Un conjunt d'un element en té $2$. Un de dos elements en té $4$: el buit, els dos unitaris i el total.

Un avís. Els elements de $\mathcal{P}(A)$ són conjunts, no elements d'$A$. El conjunt buit i el mateix $A$ hi són sempre, i és fàcil oblidar-se'n en comptar a mà.

El raonament. Una aplicació assigna a cada element de sortida exactament una imatge, i les eleccions són independents:

$n^{m} = 4^{5} = 1024$

Compte amb l'ordre dels exponents. La base és la mida del conjunt d'arribada (les opcions) i l'exponent és la del de sortida (les decisions). Intercanviar-los dona $625$, que és una resposta diferent.

De pas: injectives n'hi ha zero, perquè amb $5$ elements de sortida no pots anar a $4$ imatges diferents, i bijectives només si els dos conjunts tenen la mateixa mida.

El raonament. El primer element tria entre $8$ imatges; el segon, entre les $7$ que queden lliures; i així fins a acabar:

$8\cdot7\cdots4 = 6720$

Comparació. Aplicacions totals n'hi ha $32768$, o sigui que només una fracció són injectives. I si el conjunt de sortida fos més gran que el d'arribada, no n'hi hauria cap: aquest és el principi del colomar en la seva forma més bàsica.

Cas particular. Quan els dos conjunts tenen la mateixa mida, injectiva, exhaustiva i bijectiva són el mateix, i el recompte dona el factorial.

La fórmula i el seu perquè.

$|A\cup B| = |A| + |B| - |A\cap B| = 12 + 18 - 7 = 23$

En sumar $12$ i $18$, els $7$ elements comuns s'han comptat dues vegades, una en cada conjunt. Restar-los una vegada els deixa comptats exactament un cop.

Comprovacions de coherència. El resultat ha de quedar entre el més gran dels dos ($18$) i la suma ($30$). I la intersecció mai no pot superar el més petit dels dos conjunts.

Amb tres conjunts la fórmula segueix alternant signes: se sumen les tres mides, es resten les tres interseccions dos a dos i es torna a sumar la triple. Aquest és el principi d'inclusió i exclusió general.

El raonament. Una aplicació assigna a cada element de sortida exactament una imatge, i les eleccions són independents:

$n^{m} = 5^{5} = 3125$

Compte amb l'ordre dels exponents. La base és la mida del conjunt d'arribada (les opcions) i l'exponent és la del de sortida (les decisions). Intercanviar-los dona $3125$, que és una resposta diferent.

De pas: injectives n'hi ha $5\cdot4\cdots$, és a dir $120$, i bijectives només si els dos conjunts tenen la mateixa mida.

La fórmula i el seu perquè.

$|A\cup B| = |A| + |B| - |A\cap B| = 12 + 22 - 3 = 31$

En sumar $12$ i $22$, els $3$ elements comuns s'han comptat dues vegades, una en cada conjunt. Restar-los una vegada els deixa comptats exactament un cop.

Comprovacions de coherència. El resultat ha de quedar entre el més gran dels dos ($22$) i la suma ($34$). I la intersecció mai no pot superar el més petit dels dos conjunts.

Amb tres conjunts la fórmula segueix alternant signes: se sumen les tres mides, es resten les tres interseccions dos a dos i es torna a sumar la triple. Aquest és el principi d'inclusió i exclusió general.

El raonament. Una aplicació assigna a cada element de sortida exactament una imatge, i les eleccions són independents:

$n^{m} = 6^{5} = 7776$

Compte amb l'ordre dels exponents. La base és la mida del conjunt d'arribada (les opcions) i l'exponent és la del de sortida (les decisions). Intercanviar-los dona $15625$, que és una resposta diferent.

De pas: injectives n'hi ha $6\cdot5\cdots$, és a dir $720$, i bijectives només si els dos conjunts tenen la mateixa mida.

La fórmula i el seu perquè.

$|A\cup B| = |A| + |B| - |A\cap B| = 12 + 22 - 5 = 29$

En sumar $12$ i $22$, els $5$ elements comuns s'han comptat dues vegades, una en cada conjunt. Restar-los una vegada els deixa comptats exactament un cop.

Comprovacions de coherència. El resultat ha de quedar entre el més gran dels dos ($22$) i la suma ($34$). I la intersecció mai no pot superar el més petit dels dos conjunts.

Amb tres conjunts la fórmula segueix alternant signes: se sumen les tres mides, es resten les tres interseccions dos a dos i es torna a sumar la triple. Aquest és el principi d'inclusió i exclusió general.