Links útils i referències externes
Vídeo útil per guanyar intuïció (a partir del minut 23:18)
Entendre ‘Stars and Bars’ (combinacions amb repetició)
Més coses
Beggar’s Method
Principi multiplicatiu
Per completar
Recursos que es poden utilitzar per explicar combinatoria
Altres
‣
Fórmules
Permutacions, variacions i combinacions (sense i amb repetició)
Coefficient binomial
Fórmula de Stirling
Identitats del coefficient binomial
Sempre tindrem que
Overview conceptual
Introducció
Al principi el tema de combinatòria pot resultar una mica frustrant si el que es vol és intentar entendre’l.
Els enunciats, poden semblar molt senzills, però moltes vegades no és trivial saber quina expressió utilitzar, i posar-se a contar manualment tots els casos favorables i casos totals pot ser poc pràctic.
El que farem doncs aquí, per ser pràctics, serà intentar pensar els exercicis com si fossin versions d’un model que ja coneixem.
Anem a considerar les següents dues circumstàncies.
- Posar boles dins de caixes
- Triar elements d’un total, havent-hi tipus.
L’objectiu serà doncs entendre i donar un significat intuitiu a les expressions de combinatòria per aquests dos models i després, aprendre aplicar-los a enunciats diversos (alumnes i classes, digits d’una contrasenya, daus…).
El que farem serà centrar-nos conceptualment en el model 1, i després en el model 2, i veurem que són equivalents. Un cop entesos, podrem aplicar el que ens sigui més útil a cada exercici.
Al final d’aquesta pàgina s’hi troben un seguit de problemes de la col·lecció i problems d'exàmens resolts seguint aquesta filosofia.
Resum del que veurem
Posar boles dins de caixes
- Boles diferents = Variacions | Boles idèntiques = Combinacions
- Sense restriccions = “Amb repetició” | Màxim 1 bola per caixa = “Sense repetició”
Seqüència obtinguda de triar elements d’una bossa amb il·limitats elements de tipus diferents.
- Importa l’ordre de la seqüència = Variacions
- Només ens importa quins elements obtenim i no en quin ordre = Combinacions
- Un cop agafem un número aquest torna a estar disponible dins la bossa = “Amb repetició”
- Un cop agafem un número aquell ja no pot tornar a sortir = “Sense repetició”
Nota
Per les variacions i combinacions amb repetició, podem prendre com el número gran i com el petit o al revés segons convingui.
En canvi per variacions i combinacions sense repetició sempre tindrem que .
Model 1 - posar boles a dins de caixes
Nota prèvia
Sempre considerem que
- Les caixes estan fixes en la seva posició (caixa 1, caixa 2, caixa 3…)
- Que l’ordre amb el que posees les boles a dins de la caixa no és important (només quines hi ha i si es poden distingir entre elles).
- Que poden quedar caixes buides i no passa res
Podríem no fer aquestes restriccions però aquí ens centrarem sols en la combinatòria més elemental.
Per si es vol comprovar
Podeu comprovar resultats si voleu amb la següent simulació del Wolfram Demonstrations Project.
‣
Per tal que funcioni fluidament és millor i provar la versió d’escriptori de la simulació.
Previ: Permutacions
Les permutacions és simplement agafar un grup (de boles de diferents colors per exemple) i mirar de quantes maneres podem col·locar-les.
Per exemple si tenim 3 elements diferents, els podrem ordenar de maneres
Previ: Permutacions amb repetició
Imaginem directament un exemple: tenim 7 boles de diferents colors (grups). D’aquestes set boles 2 són blaves, 3 són vermelles, 1 és lila i 1 és verda.
Fent permutacions estaríem contant de més, ja que , és a dir que si tenim per exemple 2 boles blaves, hi haurà 2 casos que seran el mateix, si tenim 3 boles vermelles hi haurà 3!=6 casos que seran el mateix, etc. Així doncs per trobar els casos possibles d’ordenació que tenim haurem de fer les permutacions totals i dividir per les permutacions de cada subgrup.
En el nostre exemple això seria
Exemple amb la paraula MISSISSIPI
Això sol sortir en paraules que repeteixen lletres al estil
I et pregunten quina és la probabilitat que si tenim aquestes lletres concretament i les barregem aleatòriament obtinguem la paraula “mississippi”, doncs els casos totals seran el total de permutacions si tinguéssim 11 lletres diferents (11!) dividit per les permutacions entre lletres repetides (4! per la S, 2! per la P i 4! per la I). I els casos favorables serà la paraula ‘missisipi’ (1 cas).
Nota: exemple que utilitzarem
Anirem repetint al inici de cada secció dos exemples, un en què posarem boles dins de caixes, i un altre on posem boles a dins de caixes.
El que canviarà és si aquestes boles són idèntiques (mateix color) o diferents, i si tenim alguna restricció (màxim 1 bola per caixa) o no en tenim cap.
Variacions amb repetició (tots els casos possibles)
Exemples desglossats - Variacions amb repetició
Per i
Anem a veure els 9 casos.
Tindrem primer els casos en què hi ha més d’una bola per caixa
I després els que només hi ha una bola per caixa
Nota: Fixar-se que en el nostre model importa quines boles hi ha a cada caixa, però no en quin ordre han entrat .
Per i
Anem a veure els 64 casos. Vinga!
Primer els que hi ha 3 boles per caixa —> 4 casos
I ara els que hi ha 2 boles en una caixa —> 3 × 3 × 4 = 36 casos
I ara els que màxim hi ha una bola per caixa —> 4 × 3! = 24 casos
Deducció lògica fórmula
Podríem pensar-ho així:
“Per la primera bola tenim opcions, per la 2a bola també tenim opcions, i per la 3a, la 4a… per totes podem triar entre caixes a on posar-les. Aleshores si tenim boles tindrem casos possibles diferents.”
Variacions sense repetició (màx 1 bola per caixa)
Exemples desglossats - Variacions sense repetició
Per i
Anem a veure els 6 casos.
Seran els mateixos que abans (variacions amb repetició), però ara hem de descomptar els 3 casos en què teníem més d’una bola per caixa, quedant doncs els 6 corresponents.
Per i
Anem a veure els 24 casos.
Seran els mateixos que els totals (variacions sense repetició) però ara hem de descontar 4 els casos en què hi havia tres boles per caixa i els 36 casos en què hi havia dues boles en una caixa, quedant doncs només els 24 en què hi ha màxim una bola per caixa
Deducció lògica fórmula
“Per la primera bola tens opcions, per la 2a bola tens opcions, per la 3a bola tens opcions, per la 4a tens que si ens fixem és , per la 5a tindrem … i per la bola número tindrem opcions”
Els casos possibles seran doncs
Veiem-ho amb un exemple: 3 boles i 7 caixes
Permutacions
Fixar-se que si les variacions són permutacions
Combinacions sense repetició (boles idèntiques, màx 1 per caixa)
Exemples desglossats - Combinacions sense repetició
Per i
Anem a veure els 3 casos.
Ara tenim que les boles són indistingibles , així que dels 6 casos de variacions sense repetició, ens queden amb només 3.
Per i
Els 4 casos seran
Deducció lògica fórmula
“És equivalent a variacions sense repetició però ara hem de descontar el ‘double counting’, ja que posar una bola vermella, una blava i una lila és equivalent a posar una blava, una lila i una vermella, o bé una lila una vermella i una blava, etc. Les 6 permutacions d’aquestes 3 boles són equivalents així que s’han de descontar.”
Simetria de les combinacions
Triar 4 plats d’un menú d’un total de 6 és equivalent a preguntar-se quins 2 plats no vols triar.
Si ens fixem en la fórmula, veurem que triar o triar d’un total de són equivalents.
Això és útil ja que si per exemple tenim molècules, separades en dos grups, i , preguntar-nos quantes combinacions hi ha per tenir d’un total de és el mateix que fer-ho per .
Combinacions amb repetició (boles idèntiques)
Exemples desglossats - Combinacions amb repetició
Per i
Anem a veure els 6 casos.
Tindrem primer els 3 casos en què hi ha més d’una bola per caixa
I després els altres 3 en què només hi ha una bola per caixa
Per i
Anem a veure els 20 casos.
Primer els que hi ha 3 boles per caixa —> 4 casos
I ara els que hi ha 2 boles en una caixa —> 3 × 4 = 12 casos
I ara els que màxim hi ha una bola per caixa (combinacions sense repetició).
Stars and Bars
Aquest cas és segurament el més difícil d’entendre. Podríem pensar que hem d’agafar les variacions amb repetició i dividir per les permutacions, però com ja veurem això no funciona.
La manera fàcil d’entendre-ho és amb el que s’anomena “Stars & Bars”.
Aquí un vídeo que ho explica prou bé. Anem a explicar-ho nosaltres també però.
Exemple inicial
Si tenim 3 boles (idèntiques) a posar entre 3 caixes tindrem casos.
Els 10 casos són
Molt bé, la clau està en fixar-se que ho podem representar mitjançant “stars and bars” o si volem també li podem dir “boles i separadors”.
Quina és la gràcia? Doncs si ens fixem els separadors realment els podem considerar com a caixes buides
Així doncs el nostre problema de ‘3’ boles en ‘3’ caixes sense restriccions és equivalent a ‘3’ boles en ‘3+3-1=5’ caixes amb la restricció de màxim una bola per caixa.
Generalització
Procés mental
- Si tenim caixes, tindrem doncs separadors.
- Aquests separadors els hem de contar com a caixes buides
- Tindrem doncs en total caixes
- I les hem d’omplir amb boles
Així doncs tenim que
Model 2 - Triar elements d’un total il·limitat amb tipus
Exemple
Tenim en una bossa il·limitats elements de tipus diferents i n’escollim .
Per exemple tenim un gran bombo amb molts i molts números de loteria però totes les boles són o un 1, o un 2, o un 3 o un 4, és a dir .
Podem denotar aquesta gran bossa així
Si ara n’agafem de manera aleatòria , per ordre. Podem obtenir diferents seqüències (números), anirem veient aquest exemple detallat a cada secció.
Variacions amb repetició
Seqüències que podríem tenir si tenim il·limitats elements de tipus diferents, i n’escollim .
Seqüències possibles exemple - Variacions amb repetició
En el cas més general, a la bossa de loteria hi ha 4 tipus de boles o però en hi ha il·limitades de cada tipus.
Hi hauran doncs seqüències possibles.
Primer de tot si són totes iguals —> 4 casos
Si tenim dues repetides i una de diferent —> 3 × 3 × 4 = 36 casos
Si són totes diferents —> 4 × 3! = 24 casos
En total doncs, sumen 64 casos. És equivalent a l’exemple de boles de colors en caixes.
Equivalència
Per exemple la seqüència seria equivalent a .
Ho podríem pensar com que la primera posició de la seqüència t’indica a on està la bola blava, la segona posició t’indica a on està la bola vermella i la tercera posició t’indica a on està la bola lila.
Variacions sense repetició
Seqüències que podríem obtenir si només tinguéssim elements, cada un de un tipus diferent.
Seqüències possibles exemple - Variacions sense repetició
Si tenim en compte que a la bossa no es reponen (només tenim 4 boles enlloc de il·limitades boles de cada tipus) tindrem variacions sense repetició.
Hi hauran doncs seqüències possibles.
Equivalència
Com ja hem, l’equivalència en posar boles de colors en caixes, seria que la posició de la seqüència t’indica quina bola és (1a posició = blava, 2a posició = vermella, 3a posició = lila), i el número t’indica que aquella bola hauria d’anar a la caixa 3.
De manera que és equivalent a .
Així doncs imposar que no hi hagi números repetits (que no hi hagi reposició al agafar un número de la bossa) i per tant que si ha ha sortit un no pugui tornar a sortir, és equivalent a imposar que no hi pugui haver dues boles en una mateixa caixa, així que si la caixa número ja està plena, cap més bola podrà anar a la caixa .
Combinacions sense repetició
Grups que podríem obtenir si de elements, cadascun d’un tipus diferent i n’escollim .
Aquí diem grup perquè l’ordre de la seqüència no importa. Per exemple les dues seqüències són el mateix grup .
Grups possibles exemple - Combinacions sense repetició
Ara tenim els mateixos casos que en variacions sense repetició (), però hem de descomptar els casos en què tenim la mateixa seqüència ordenada de maneres diferents.
Hi hauran doncs casos possibles.
Equivalència
Que l’ordre de la seqüència no importi, és equivalent a que les boles siguin indistingibles.
És a dir si el color de la bola és la posició i el seu número la caixa, girar posicions en una seqüència equival a intercanviar les boles (o els seus colors) en l’altre model.
.
En els dos casos, per obtenir les combinacions a partir de les variacions hem de dividir per les permutacions que són equivalents , en un cas equival a girar posicions, en l’altre equival a que les boles siguin idèntiques.
Combinacions amb repetició
Grups que podríem obtenir si tenim il·limitats elements i n’escollim .
Diem ‘grups’ en el sentit que dues seqüències que tenen els mateixos elements però ordenats de maneres diferents, són el mateix grup.
“Un grup format per en Miquel, la Sara i en Joan és el mateix grup que un format per en Joan, en Miquel i la Sara”.
Recordem que la lògica és ‘Stars and Bars’. És a dir si tenim tipus, tindrem separadors que considerarem com números buits (tipus no utilitzats), i per tant serà equivalent a triar d’entre tipus diferents i escollir-ne sense que es puguin repetir.
Seqüències possibles exemple - Combinacions amb repetició
Tenim que l’ordre de la seqüència aquí no importa i tenim il·limitats elements de tipus.
Pel nostre exemple sabem que hi han d’haver grups diferents. Anem a veure’ls!
Primer de tot si obtenim el mateix número per les tres, tindrem 4 casos
Si tenim dues repetides i una de diferent —> 3 × 4 = 12 casos
Si són totes diferents —> 4 casos
En total doncs, tenim efectivament casos.
Permutacions amb repetició
Molt bé, sabem que si triem elements, d’un total il·limitat i tipus tenim variacions amb repetició. I que si tenim sols un element de cada tipus ( tipus), i en treim tenim variacions sense repetició.
Però què passaria si triem elements, de tipus diferents, però no en tenim un de cada tipus, sinó que en podem tenir d’un tipus d’un altre tipus, d’un altre…
Doncs ja hem vist que això ho contem amb permutacions amb repetició
Exemple
Considerem la següent paraula
Aquesta té lletres, de tipus diferents (la no és important pel càlcul però és per què quedi clar).
Tindrem elements del tipus , elements del tipus , del tipus i del tipus .
Així doncs, si en preguntem, agafant aleatòriament aquestes lletres disponibles quina és la probabilitat d’obtenir la paraula ‘MISSISSIPI’ la probabilitat serà 1 entre els casos totals.
On els casos totals seran
Exercicis resolts
Exercicis de la col·lecció
Exercici 1 (que de 24 persones ningú comparteixi aniversari)
Casos totals
Tenim estudiants, cadascun pot néixer en dies diferents. Això és equivalent a posar 24 boles diferents en 365 caixes.
Per què diferents i no idèntiques?
Podríem pensar que ja que només ens importa el nombre d’estudiants que han nascut cada dia i no quin nom tenen, hauríem de considerar que els estudiants són “iguals” o “idèntics” però realment no és així.
Fixem-nos que no és el mateix que en Martí i la Júlia facin l’aniversari el 23 d’abril (i ningú més sigui d’aquell dia), a que en Martí i l’Oriol el facin el 23 d’abril, o que en Joan i la Berta el facin aquell dia. En tots els casos, el 23 d’abril tenim dues persones que hi fan anys. Però fent combinacions estaríem contant tots aquests casos com un de sol. I no, la realitat és que són casos diferents.
Això és així ja que el total de casos és que cada persona pot fer anys el dia que vulgui. Aleshores tenim dies possibles per en Martí, dies possibles per la Berta, etc.
Aquests són els casos totals, i no pas el de combinacions amb repetició, ja que el de combinacions amb repetició ‘seria stars and bars’ i seria equivalent a dir que [???]
Si ens fixem té tot el sentit del món ja que per cada estudiant tenim dies possibles i si són estudiants els casos possibles seran .
Casos favorables
L’enunciat ens demana la probabilitat que dos estudiants NO hagin nascut el mateix dia, és a dir volem saber els casos en què màxim hi ha un estudiant per dia (màxim una bola per caixa).
Probabilitat
La probabilitat serà
Si ens fixem també ho podem expressar així
Càlcul aproximat
Si posem a la calculadora obtindrem un nombre de l’ordre de , si provem de posar automàticament la majoria de calculadores ens donaran un “Math Error”, al haver-nos passat del nombre .
Molt bé, aleshores per xifres tan grans com no podem fer el càlcul computacional amb la calculadora (amb un ordinador i un petit codi en python realment no tardaríem gaire però a l’examen no tindrem ordinador). Com hauríem de procedir?
Doncs una manera de procedir que es sol utilitzar és prendre el logaritme de la probabilitat (després al final el desfarem) i utilitzar la aproximació de Stirling.
Nota: Realment en les solucions oficials fan el pas llarg, separen les multiplicacions dins del logaritme en una suma de logaritmes, i després fan el pas al continu convertint el sumatori en una integral que resolen tal que , que és en efecte l’aproximació de Stirling.
Així doncs
Desfent el logaritme tenim
Nota: segons la solució oficial hauria de donar , però si fem el càlcul exacte amb un ordinador obtenim és a dir que no ens hem equivocat gaire, i que les dues solucions són realment aproximacions que presenten un error relatiu similar.
Exercici 2 (encertar contrasenya de 10 dígits en binari)
Aquest a priori és bastant fàcil però ens podríem arribar a confondre.
Fixem-nos que és diferent pensar en cada digit de la contrasenya com una caixa, on hi poden anar números diferents (0 o 1), que pensar en el 0 i el 1 com dues caixes, on hi poden anar a parar els diferents dígits (boles de 10 colors diferents).
En qualsevol dels casos estarem doncs en variacions (boles diferents) amb repetició (sense restriccions), però és molt diferent fer que .
Perquè és i no ?
Per cada dígit tenim dues possibilitats, 0 o 1. Aleshores pel primer dígit tenim 2 casos, pel 2n també… en total tindrem . Que seria equivalent a tenir boles de colors diferents i preguntar-se, la de color lila on va? a la caixa 1 o a la caixa 2? la de color blau?, etc.
En canvi si consideréssim cada digit una caixa on hi pot anar una de les dues boles (blava o vermella per exemple), fixem-nos que hauríem d’imposar que màxim 1 bola per caixa i que tenim il·limitades boles blaves i boles vermelles.
Pensant-ho en el model 2, estem triant 10 elements de 2 tipus diferents, hi ha il·limitades boles dels dos tipus i ens importa l’ordre de la seqüència. Així doncs directament tenim variacions amb repetició on tenim tipus d’objectes i en triem
La manera correcta és efectivament (en el model 1) pensar els resultats 0 o 1 com a dues grans caixes on hi posem 10 boles de diferents colors, malgrat pugui semblar poc intuitiu al principi. En el model dos en canvi és immediat veure que la manera correcta és
D’aquí la gràcia de disposar dels dos models.
Si tenim que els casos totals són 1024, i els casos favorables és encertar la contrasenya exacta (1 cas), la probabilitat serà doncs
Exercici 3 (tirar 3 daus)
Estem tirant 3 daus. Cada un té 6 casos. Pel primer dau tenim 6 possibilitats, pel 2n dau també 6 i pel 3r també 6, així doncs tenim 6×6×6=216 casos totals. D’aquests els favorables seran:
- Que surti almenys un ‘1’
- Ho podem pensar com a 216 - casos favorables per tal que NO surti un 1. Per un dau que els casos favorables per tal que NO surti un 1 són 5, aleshores per 3 daus són (5)^3=125. Els casos favorables seran doncs 216-125=91.
- També ho podem pensar segons el nostre model. Estem posant 3 boles en 6 caixes diferents. Poden sortir dos 4’s per exemple així que sempre és amb repetició.
- Els casos totals són considerant els daus diferents és a dir variacions amb repetició .
- Els casos favorables seran ??? . Ni serveix. Pff I tampoc. Ben bé que no es pot explicar des del model de les boles i les caixes. Hi ha alguna manera???
- Que no hi hagi dos daus amb el mateix resultat
- Els casos favorables seran ara les variacions però sense repetició (no pot haver-hi dos daus en la caixa del ‘4’ per exemple). . Aleshores la probabilitat serà
Ens podríem preguntat que per què no podem considerar els daus idèntics? si només ens importa la seva suma no? però la clau està en que ens fan preguntes particulars seves, és a dir que surti un 1, que no surtin dos iguals, etc. Aleshores els hem de poder distingir.
Exercicis d’examen