Exercicis de combinatòria i recompte

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

Pas 2 — la fórmula.

$\frac{6!}{3!} = 120$

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 $10$ objectes en $3$ caixes, alguna caixa conté com a mínim

$\left\lceil \frac{10}{3} \right\rceil = 4$

objectes.

Per què. Si totes les caixes en tinguessin com a molt $3$, el total no passaria de $3\cdot3 = 9$, que és menys que $10$. 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{6}{3} = \frac{6!}{3!\,3!} = 20$

D'on surt la divisió. Si l'ordre importés, les tries serien $6\cdot5\cdots4 = 120$. 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{6}{3} = \binom{6}{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 $6$ 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 $7$ posicions en total i cal triar quines $1$ són barres:

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

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

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

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

Pas 2 — la fórmula.

$\frac{8!}{3! \cdot 2!} = 3360$

D'on surt la divisió. Si totes les lletres fossin diferents hi hauria $8!$ 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 $45$ objectes en $4$ caixes, alguna caixa conté com a mínim

$\left\lceil \frac{45}{4} \right\rceil = 12$

objectes.

Per què. Si totes les caixes en tinguessin com a molt $11$, el total no passaria de $4\cdot11 = 44$, que és menys que $45$. 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{6}{4} = \frac{6!}{4!\,2!} = 15$

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

Comprovació de simetria. $\binom{6}{4} = \binom{6}{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 $6$ unitats com a estrelles i posa-hi $2$ barres per repartir-les en $3$ grups. Cada disposició dona una solució i cada solució dona una disposició.

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

$\binom{6+3-1}{3-1} = \binom{8}{2} = 28$

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{5}{2} = 10$.

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: E apareix 3 vegades, N apareix 2 vegades.

Pas 2 — la fórmula.

$\frac{11!}{3! \cdot 2!} = 3326400$

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 $1000$ objectes en $365$ caixes, alguna caixa conté com a mínim

$\left\lceil \frac{1000}{365} \right\rceil = 3$

objectes.

Per què. Si totes les caixes en tinguessin com a molt $2$, el total no passaria de $365\cdot2 = 730$, que és menys que $1000$. 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.