Exercicis de combinatòria i recompte

Pas 1 — comptar. La paraula té $6$ lletres i les repeticions són: A apareix 3 vegades, T apareix 2 vegades.

Pas 2 — la fórmula.

$\frac{6!}{3! \cdot 2!} = 60$

D'on surt la divisió. Si totes les lletres fossin diferents hi hauria $6!$ ordenacions. Però intercanviar entre elles les lletres repetides dona la mateixa paraula, i això passa de tantes maneres com el factorial del grup. Es divideix pel sobrecomptatge de cada grup.

És exactament el mateix argument que justifica el coeficient binomial, aplicat a més d'un grup alhora.

El principi. Si reparteixes $100$ objectes en $9$ caixes, alguna caixa conté com a mínim

$\left\lceil \frac{100}{9} \right\rceil = 12$

objectes.

Per què. Si totes les caixes en tinguessin com a molt $11$, el total no passaria de $9\cdot11 = 99$, que és menys que $100$. Contradicció.

El que el principi no diu. No diu quina caixa, ni com repartir-los. Només garanteix existència, i això és precisament el que el fa útil: molts arguments només necessiten saber que alguna cosa existeix, no trobar-la.

La fórmula.

$\binom{5}{2} = \frac{5!}{2!\,3!} = 10$

D'on surt la divisió. Si l'ordre importés, les tries serien $5\cdot4\cdots4 = 20$. Però cada subconjunt s'ha comptat $2! = 2$ vegades, una per cada manera d'ordenar-lo, i per això es divideix.

Comprovació de simetria. $\binom{5}{2} = \binom{5}{3}$, perquè triar quins entren equival a triar quins queden fora. Si el teu resultat no compleix aquesta simetria, has calculat malament.

El model. Representa les $4$ unitats com a estrelles i posa-hi $4$ barres per repartir-les en $5$ grups. Cada disposició dona una solució i cada solució dona una disposició.

El recompte. Hi ha $8$ posicions en total i cal triar quines $4$ són barres:

$\binom{4+5-1}{5-1} = \binom{8}{4} = 70$

Si les variables haguessin de ser estrictament positives, el canvi que resta $1$ a cadascuna deixaria l'equació amb $-1$ a la dreta i el resultat seria $\binom{3}{4} = 0$.

Fixa't que aquest model només val per a objectes indistingibles.

Pas 1 — comptar. La paraula té $9$ lletres i les repeticions són: A apareix 2 vegades, E apareix 2 vegades, R apareix 3 vegades.

Pas 2 — la fórmula.

$\frac{9!}{3! \cdot 2! \cdot 2!} = 15120$

D'on surt la divisió. Si totes les lletres fossin diferents hi hauria $9!$ ordenacions. Però intercanviar entre elles les lletres repetides dona la mateixa paraula, i això passa de tantes maneres com el factorial del grup. Es divideix pel sobrecomptatge de cada grup.

És exactament el mateix argument que justifica el coeficient binomial, aplicat a més d'un grup alhora.

El principi. Si reparteixes $50$ objectes en $7$ caixes, alguna caixa conté com a mínim

$\left\lceil \frac{50}{7} \right\rceil = 8$

objectes.

Per què. Si totes les caixes en tinguessin com a molt $7$, el total no passaria de $7\cdot7 = 49$, que és menys que $50$. Contradicció.

El que el principi no diu. No diu quina caixa, ni com repartir-los. Només garanteix existència, i això és precisament el que el fa útil: molts arguments només necessiten saber que alguna cosa existeix, no trobar-la.

La fórmula.

$\binom{5}{3} = \frac{5!}{3!\,2!} = 10$

D'on surt la divisió. Si l'ordre importés, les tries serien $5\cdot4\cdots3 = 60$. Però cada subconjunt s'ha comptat $3! = 6$ vegades, una per cada manera d'ordenar-lo, i per això es divideix.

Comprovació de simetria. $\binom{5}{3} = \binom{5}{2}$, perquè triar quins entren equival a triar quins queden fora. Si el teu resultat no compleix aquesta simetria, has calculat malament.

El model. Representa les $5$ unitats com a estrelles i posa-hi $1$ barres per repartir-les en $2$ grups. Cada disposició dona una solució i cada solució dona una disposició.

El recompte. Hi ha $6$ posicions en total i cal triar quines $1$ són barres:

$\binom{5+2-1}{2-1} = \binom{6}{1} = 6$

Si les variables haguessin de ser estrictament positives, el canvi que resta $1$ a cadascuna deixaria l'equació amb $3$ a la dreta i el resultat seria $\binom{4}{1} = 4$.

Fixa't que aquest model només val per a objectes indistingibles.

Pas 1 — comptar. La paraula té $11$ lletres i les repeticions són: A apareix 2 vegades, I apareix 2 vegades, S apareix 2 vegades, T apareix 2 vegades.

Pas 2 — la fórmula.

$\frac{11!}{2! \cdot 2! \cdot 2! \cdot 2!} = 2494800$

D'on surt la divisió. Si totes les lletres fossin diferents hi hauria $11!$ ordenacions. Però intercanviar entre elles les lletres repetides dona la mateixa paraula, i això passa de tantes maneres com el factorial del grup. Es divideix pel sobrecomptatge de cada grup.

És exactament el mateix argument que justifica el coeficient binomial, aplicat a més d'un grup alhora.

El principi. Si reparteixes $367$ objectes en $366$ caixes, alguna caixa conté com a mínim

$\left\lceil \frac{367}{366} \right\rceil = 2$

objectes.

Per què. Si totes les caixes en tinguessin com a molt $1$, el total no passaria de $366\cdot1 = 366$, que és menys que $367$. Contradicció.

El que el principi no diu. No diu quina caixa, ni com repartir-los. Només garanteix existència, i això és precisament el que el fa útil: molts arguments només necessiten saber que alguna cosa existeix, no trobar-la.