Permutacions
De quantes maneres poden arribar a la meta 7 corredors, sense empats? És una pregunta d'ordenar: col·locar tots els elements d'un conjunt, un darrere l'altre. Això s'anomena permutació, i és el cas més simple (i més utilitzat) de la combinatòria.
Permutacions de n elements diferents
Per al primer lloc hi ha $n$ opcions; triada aquesta, per al segon en queden $n-1$; per al tercer, $n-2$; i així fins que només queda $1$ opció per a l'últim.
$$P_n = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1 = n!$$Un grup de $6$ amics va al teatre i compren entrades per a seients consecutius a la mateixa fila. De quantes maneres diferents es poden seure a gaudir de l'obra?
Un grup de $6$ amics va al teatre i compren entrades per a seients consecutius a la mateixa fila. De quantes maneres diferents es poden seure a gaudir de l'obra?
Durant una competició d'atletisme escolar, $7$ corredors arriben a la meta sense que es produeixi cap empat. Quantes classificacions diferents es poden donar al final de…
Durant una competició d'atletisme escolar, $7$ corredors arriben a la meta sense que es produeixi cap empat. Quantes classificacions diferents es poden donar al final de la cursa?
Permutacions amb restriccions de posició
Moltes vegades una part de l'ordenació està fixada per endavant: dues persones que han de seure juntes, un element que ha d'anar primer o últim... En aquests casos no s'aplica $n!$ directament: cal raonar primer la restricció i ordenar després allò que queda lliure.
Cinc amics van al cinema i se seuen en butaques contigües. Dos d'ells, la Amina i en Unai, volen seure junts per compartir les crispetes. De quantes maneres es poden…
Cinc amics van al cinema i se seuen en butaques contigües. Dos d'ells, la Amina i en Unai, volen seure junts per compartir les crispetes. De quantes maneres es poden acomodar els cinc amics complint sempre aquesta condició?
A la final d'una cursa de natació dels Jocs Olímpics participen $8$ nedadors. Si sabem amb certesa quin nedador ha guanyat la medalla d'or i quin ha arribat en últim…
A la final d'una cursa de natació dels Jocs Olímpics participen $8$ nedadors. Si sabem amb certesa quin nedador ha guanyat la medalla d'or i quin ha arribat en últim lloc a causa d'una lesió, de quantes maneres diferents s'han pogut classificar els altres participants en les posicions intermèdies?
Permutacions amb elements repetits
Quantes paraules diferents es poden formar amb les lletres d'ANA? Si tractessis les dues lletres A com a distingibles ($A_1$ i $A_2$) sortirien $3!=6$ ordenacions, però la meitat són indistingibles en llegir-les: $A_1NA_2$ i $A_2NA_1$ són, en realitat, la mateixa paraula.
Quantes paraules diferents, tinguin o no sentit al diccionari, es poden formar ordenant totes les lletres de la paraula "MUNDO"?
Quantes paraules diferents, tinguin o no sentit al diccionari, es poden formar ordenant totes les lletres de la paraula "MUNDO"?
Un vaixell es comunica amb altres navilis mitjançant banderes de colors izades verticalment en un màstil. Si disposa de $3$ banderes vermelles, $2$ banderes blaves i $1$…
Un vaixell es comunica amb altres navilis mitjançant banderes de colors izades verticalment en un màstil. Si disposa de $3$ banderes vermelles, $2$ banderes blaves i $1$ bandera groga, totes de la mateixa mida, quants senyals diferents pot enviar usant totes les banderes alhora?
Un enginyer informàtic vol formar codis numèrics de sis xifres utilitzant exactament els dígits següents en cada codi: $2, 2, 3, 3, 3, 4$. Quants codis diferents pot…
Un enginyer informàtic vol formar codis numèrics de sis xifres utilitzant exactament els dígits següents en cada codi: $2, 2, 3, 3, 3, 4$. Quants codis diferents pot programar el sistema?
Permutacions circulars i camins en una quadrícula
En una fila, el primer i l'últim lloc són diferents. En una taula rodona no hi ha «primer seient»: només importa l'ordre relatiu. Girar tot el grup un seient sencer no compta com una col·locació nova.
Una altra situació amb el mateix tipus de recompte, encara que no sigui circular: un repartidor que només es pot moure cap a la dreta o cap amunt en una quadrícula. Cada camí mínim és una seqüència de passos «dreta» (D) i «amunt» (A), i comptar camins equival a ordenar aquesta seqüència amb lletres repetides.
Una família de $6$ membres se seuta a sopar al voltant d'una taula circular en un restaurant. De quantes maneres diferents es poden ubicar si només importa la posició…
Una família de $6$ membres se seuta a sopar al voltant d'una taula circular en un restaurant. De quantes maneres diferents es poden ubicar si només importa la posició relativa entre ells i no la cadira exacta que ocupen a la sala?
En el plànol d'una ciutat amb carrers disposats en quadrícula, un repartidor en bicicleta ha d'anar des del punt $A$ fins al punt $B$ desplaçant-se únicament cap a la…
En el plànol d'una ciutat amb carrers disposats en quadrícula, un repartidor en bicicleta ha d'anar des del punt $A$ fins al punt $B$ desplaçant-se únicament cap a la dreta i cap amunt. Quants camins diferents de longitud mínima pot agafar per realitzar el lliurament?