Exercicis de conjunts, aplicacions i relacions

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

$6\cdot5\cdots3 = 360$

Comparació. Aplicacions totals n'hi ha $1296$, 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 + 8 - 7 = 13$

En sumar $12$ i $8$, 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 ($12$) i la suma ($20$). 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 $15$ decisions independents, una per element: hi entra o no hi entra. Dues opcions cada vegada, i es multipliquen:

$|\mathcal{P}(A)| = 2^{15} = 32768$

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} = 5^{4} = 625$

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 $1024$, 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.

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

$7\cdot6\cdots4 = 840$

Comparació. Aplicacions totals n'hi ha $2401$, 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 + 14 - 3 = 23$

En sumar $12$ i $14$, 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 ($14$) i la suma ($26$). 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 $16$ decisions independents, una per element: hi entra o no hi entra. Dues opcions cada vegada, i es multipliquen:

$|\mathcal{P}(A)| = 2^{16} = 65536$

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} = 6^{4} = 1296$

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 $4096$, que és una resposta diferent.

De pas: injectives n'hi ha $6\cdot5\cdots$, és a dir $360$, 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\cdots5 = 1680$

Comparació. Aplicacions totals n'hi ha $4096$, 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 + 14 - 5 = 21$

En sumar $12$ i $14$, 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 ($14$) i la suma ($26$). 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.