Exercicis de combinatòria — Matemàtiques 4t ESO

Principi del producte: si una elecció es pot fer de 3 maneres, una altra de 4 i una altra de 2, el total és el producte.
3 · 4 · 2 = 24 menús.
Amb un diagrama d'arbre: 3 branques per als primers, de cadascuna en surten 4 pels segons i de cada una d'aquestes 2 per les postres; són 3 · 4 · 2 = 24 camins.

El factorial és n! = n·(n - 1)·…·2·1.
5! = 5·4·3·2·1 = 120.
7!/5! = $\tfrac{(7\cdot 6\cdot 5!)}{5}$! = 7·6 = 42 (simplifiquem abans de multiplicar).
10!/(8!·2!) = $\tfrac{(10\cdot 9\cdot 8!)}{(8!\cdot 2)}$ = $\tfrac{(10\cdot 9)}{2} = 45$.
Error típic: calcular 7! i 5! per separat; amb factorials grans és molt més fàcil simplificar.

S'usen tots els elements i només importa l'ordre: són permutacions de 5 elements.
$P_{5}$ = 5! = 5·4·3·2·1 = 120.
Raonament: per al primer lloc hi ha 5 llibres, per al segon 4, per al tercer 3, per al quart 2 i per al darrer 1.

Importa l'ordre (or, plata i bronze són premis diferents) i un atleta no pot guanyar dues medalles: són variacions sense repetició de 8 elements preses de 3 en 3.
V(8, 3) = 8·7·6 = 336.
Raonament: 8 candidats per a l'or, 7 per a la plata i 6 per al bronze.

Importa l'ordre (AEI no és el mateix que EIA) i es poden repetir: són variacions amb repetició de 5 elements preses de 3 en 3.
VR(5, 3) = $5^{3}$ = 125.
Raonament: 5 possibilitats per a cada una de les 3 posicions, i 5·5·5 = 125.

L'ordre no importa (la comissió {A, B, C} és la mateixa que {C, A, B}) i no es repeteixen: són combinacions de 7 elements preses de 3 en 3.
C(7, 3) = 7!/(3!·4!) = (7·6·5)/(3·2·1) = 210/6 = 35.
Comprovació: V(7, 3) = 210 ordenacions, i cada comissió s'ha comptat 3! = 6 vegades; 210/6 = 35.

C(n, k) = n!/(k!·(n - k)!).
C(6, 2) = $\tfrac{(6\cdot 5)}{(2\cdot 1)} = 15$.
C(6, 4) = $\tfrac{(6\cdot 5\cdot 4\cdot 3)}{(4\cdot 3\cdot 2\cdot 1)} = 15$.
C(8, 0) = 1 i C(8, 8) = 1 (només hi ha una manera de no triar res o de triar-ho tot).
C(5, 1) = 5.
Observació: C(6, 2) = C(6, 4), perquè triar 2 elements per agafar és el mateix que triar els 4 que es deixen: C(n, k) = C(n, n - k).

La fila del triangle de Pascal que correspon a l'exponent 4 és 1, 4, 6, 4, 1 (cada nombre és la suma dels dos que té a sobre a la fila anterior, que és 1, 3, 3, 1).
Aquests són els coeficients de (a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴.
Amb a = x i b = 1: (x + 1)⁴ = x⁴ + 4x³ + 6x² + 4x + 1.
Comprovació: per a x = 1, 2⁴ = 16 = 1 + 4 + 6 + 4 + 1.

La paraula té 4 lletres, amb la A repetida 2 vegades: són permutacions amb repetició.
PR(4; 2) = 4!/2! = 24/2 = 12.
Per què dividim entre 2!: si féssim 4! = 24, comptaríem dues vegades cada ordenació, perquè en intercanviar les dues A la paraula no canvia.
Alguns anagrames: CASA, CAAS, CSAA, ACSA...

a) L'ordre importa (delegat i sotsdelegat són càrrecs diferents) i no hi ha repetició: variacions V(20, 2).
b) L'ordre no importa (només cal saber qui hi va) i no hi ha repetició: combinacions C(20, 2).
c) Importa l'ordre i s'utilitzen tots els elements: permutacions $P_{6}$ = 6!.
d) L'ordre importa i les xifres es poden repetir: variacions amb repetició VR(10, 4) = $10^{4}$.

Tractem A i B com un sol bloc: ara hi ha 4 «elements» (el bloc i els altres 3 amics), que es poden ordenar de 4! = 24 maneres.
Dins del bloc, A i B es poden col·locar de 2 maneres (AB o BA).
Total: 24 · 2 = 48.
Comprovació: sense la restricció hi ha 5! = 120 ordenacions; 48 és menys de la meitat, com és lògic.

Sense repetir: variacions de 5 elements de 3 en 3, V(5, 3) = 5·4·3 = 60.
Repetint: variacions amb repetició, VR(5, 3) = $5^{3}$ = 125.
Parells sense repetir: la xifra de les unitats ha de ser 2 o 4 (2 possibilitats). Per a les altres dues posicions queden 4 xifres, que es poden col·locar de V(4, 2) = 4·3 = 12 maneres.
Total de parells: 2 · 12 = 24.
Compte: cal decidir primer la posició amb la restricció (les unitats) i després la resta.

Dues eleccions independents, i en cada una l'ordre no importa.
Noies: C(12, 2) = $\tfrac{(12\cdot 11)}{2} = 66$.
Nois: C(10, 1) = 10.
Pel principi del producte: 66 · 10 = 660 comissions.

BARBARA té 7 lletres: B 2 vegades, A 3 vegades i R 2 vegades. Són permutacions amb repetició.
PR(7; 2, 3, 2) = 7!/(2!·3!·2!) = 5040/(2·6·2) = 5040/24 = 210.
Es divideix pel factorial de cada lletra repetida per no comptar com a diferents les ordenacions que només intercanvien lletres iguals.

V(n, 2) = n·(n - 1), així que n·(n - 1) = 42, és a dir, $n^{2}$ - n - 42 = 0.
n = $\tfrac{(1 \pm \sqrt{1 + 168})}{2}$ = $\tfrac{(1 \pm 13)}{2}$, d'on n = 7 o n = -6.
Com que n és un nombre d'elements, ha de ser natural: n = 7.
Comprovació: V(7, 2) = 7·6 = 42.

Desenvolupem el factorial més gran fins a arribar al més petit.
(n + 2)!/n! = ((n + 2)·(n + 1)·n!)/n! = (n + 2)(n + 1).
(n + 1)!/(n - 1)! = ((n + 1)·n·(n - 1)!)/(n - 1)! = (n + 1)·n.
Comprovació amb n = 4: 6!/4! = 720/24 = 30 = 6·5, i 5!/3! = 120/6 = 20 = 5·4.

Els coeficients de (a + b$)^{3}$ són 1, 3, 3, 1: (a + b$)^{3}$ = $a^{3}$ + 3a²b + 3ab² + $b^{3}$.
Amb a = 2x i b = -3: (2x$)^{3}$ = 8x³; 3·(2x$)^{2}$·(-3) = -36x²; 3·(2x)·(-3$)^{2}$ = 54x; (-3$)^{3}$ = -27.
Resultat: 8x³ - 36x² + 54x - 27.
Comprovació: per a x = 1, (2 - 3$)^{3}$ = -1 i 8 - 36 + 54 - 27 = -1.

El terme general de (x + 3$)^{5}$ és C(5, k)·x^{5 - k}·$3^{k}$.
Perquè l'exponent de x sigui 2: 5 - k = 2, és a dir, k = 3.
Terme: C(5, 3)·$x^{2}$·$3^{3}$ = 10·27·$x^{2}$ = 270x².
El coeficient és 270.

Un partit és una parella d'equips, i l'ordre no importa (A-B és el mateix partit que B-A): C(8, 2) = $\tfrac{(8\cdot 7)}{2} = 28$ partits.
Amb anada i tornada, cada parella juga dos partits (importa quin equip juga a casa): V(8, 2) = 8·7 = 56 partits, que és el doble de 28.

Anem franja per franja.
Primera: 5 colors possibles.
Segona: qualsevol menys el de la primera, 4 colors.
Tercera: qualsevol menys el de la segona, 4 colors (el de la primera sí que es pot repetir).
Pel principi del producte: 5 · 4 · 4 = 80 banderes.
Error típic: aplicar V(5, 3) = 60, que prohibiria també que coincidissin la primera i la tercera.

C(10, 3) = (10·9·8)/6 = 120 i C(10, 4) = (10·9·8·7)/24 = 210, així que la suma és 330.
C(11, 4) = (11·10·9·8)/24 = 7920/24 = 330. Coincideixen.
Propietat: C(n, k) + C(n, k + 1) = C(n + 1, k + 1). Al triangle de Pascal, cada nombre és la suma dels dos que té just a sobre, i per això es pot construir fila a fila sense calcular factorials.

Comptem totes les comissions i restem les que no compleixen la condició (mètode del complementari).
Totes: C(8, 4) = 70.
Cap dona (4 homes entre els 5): C(5, 4) = 5.
Almenys una dona: 70 - 5 = 65.
Comptar directament (1 dona, 2 dones, 3 dones) també dona 65, però exigeix tres càlculs en lloc d'un.

Un múltiple de 5 acaba en 0 o en 5. Separem els dos casos.
Acaben en 0: les altres tres xifres són diferents entre elles i de 0, triades entre les 9 restants: 9·8·7 = 504.
Acaben en 5: la primera xifra no pot ser ni 0 ni 5 (8 possibilitats); la segona pot ser qualsevol menys el 5 i la primera (8 possibilitats, perquè el 0 ara sí que hi val); la tercera, 7 possibilitats: 8·8·7 = 448.
Total: 504 + 448 = 952.

Hi ha 9 llocs. Com que hi ha més nois que noies, l'única manera d'alternar és començar i acabar per noi: N G N G N G N G N.
Els 5 nois ocupen els llocs 1, 3, 5, 7 i 9: es poden ordenar de 5! = 120 maneres.
Les 4 noies ocupen els llocs 2, 4, 6 i 8: es poden ordenar de 4! = 24 maneres.
Pel principi del producte: 120 · 24 = 2880.

El desenvolupament té 6 + 1 = 7 termes, així que el central és el quart (k = 3).
Terme general: C(6, k)·(2x)^{6 - k}·$y^{k}$.
Per a k = 3: C(6, 3)·(2x$)^{3}$·$y^{3}$ = 20·8x³·$y^{3}$ = 160x³$y^{3}$.
Comprovació: C(6, 3) = $\tfrac{(6\cdot 5\cdot 4)}{(3\cdot 2\cdot 1)} = 20$ i $2^{3}$ = 8.

Tres boles del mateix gust: 4 copes (una per gust).
Dues boles d'un gust i una d'un altre: 4 maneres d'escollir el gust repetit i 3 d'escollir l'altre, 4·3 = 12 copes.
Tres gustos diferents: C(4, 3) = 4 copes.
Total: 4 + 12 + 4 = 20 copes.
(Són combinacions amb repetició: CR(4, 3) = C(4 + 3 - 1, 3) = C(6, 3) = 20.)

V(n, 3) = n·(n - 1)·(n - 2) i C(n, 2) = n·$\tfrac{(n - 1)}{2}$.
L'equació queda n(n - 1)(n - 2) = 6·n(n - 1)/2 = 3n(n - 1).
Com que n ≥ 3, el factor n(n - 1) no és zero i el podem simplificar: n - 2 = 3, d'on n = 5.
Comprovació: V(5, 3) = 5·4·3 = 60 i 6·C(5, 2) = 6·10 = 60.

Total: $26^{2}$·$10^{3}$ = 676·1000 = 676000 codis (variacions amb repetició a cada part).
Tot diferent: 26·25 per a les lletres i 10·9·8 per als dígits: 650·720 = 468000 codis.
Almenys una repetició (de lletra o de dígit): és el complementari, 676000 - 468000 = 208000 codis.

a) Certa. De cada combinació de k elements es poden fer k! ordenacions, i cada una és una variació diferent. Exemple: V(5, 2) = 20 i 2!·C(5, 2) = 2·10 = 20.
b) Certa. Triar k elements és el mateix que triar els n - k que es deixen.
c) Falsa. (a + b$)^{2}$ = $a^{2}$ + 2ab + $b^{2}$: amb a = b = 1 dona 4, no 1 + 1 = 2. Falten els termes intermedis del binomi.
d) Certa. V(3, 2) = 3·2 = 6 i $P_{3}$ = 3! = 6: en triar 2 de 3 elements ordenats, el tercer queda determinat.

Les lletres són L, L, I, B, R, E: 6 lletres, amb la L repetida 2 vegades. Les vocals són la I i la E.
Si l'anagrama comença per I, queden 5 lletres (L, L, B, R, E) per ordenar, amb la L repetida: 5!/2! = 60.
El mateix si comença per E: 60.
Total: 60 + 60 = 120.
Comprovació: el total d'anagrames és 6!/2! = 360, i 120 és un terç, que coincideix amb la proporció de vocals (2 de 6).