Exercicis de combinatòria i recompte

La fórmula.

$\binom{6}{5} = \frac{6!}{5!\,1!} = 6$

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

Comprovació de simetria. $\binom{6}{5} = \binom{6}{1}$, 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 $3$ barres per repartir-les en $4$ grups. Cada disposició dona una solució i cada solució dona una disposició.

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

$\binom{6+4-1}{4-1} = \binom{9}{3} = 84$

Si les variables haguessin de ser estrictament positives, el canvi que resta $1$ a cadascuna deixaria l'equació amb $2$ a la dreta i el resultat seria $\binom{5}{3} = 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: A apareix 5 vegades, B apareix 2 vegades, R apareix 2 vegades.

Pas 2 — la fórmula.

$\frac{11!}{5! \cdot 2! \cdot 2!} = 83160$

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

$\left\lceil \frac{17}{4} \right\rceil = 5$

objectes.

Per què. Si totes les caixes en tinguessin com a molt $4$, el total no passaria de $4\cdot4 = 16$, que és menys que $17$. 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{7}{2} = \frac{7!}{2!\,5!} = 21$

D'on surt la divisió. Si l'ordre importés, les tries serien $7\cdot6\cdots6 = 42$. 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{7}{2} = \binom{7}{5}$, 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 $4$ barres per repartir-les en $5$ grups. Cada disposició dona una solució i cada solució dona una disposició.

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

$\binom{6+5-1}{5-1} = \binom{10}{4} = 210$

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

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

Pas 1 — comptar. La paraula té $10$ lletres i les repeticions són: I apareix 4 vegades, S apareix 4 vegades.

Pas 2 — la fórmula.

$\frac{10!}{4! \cdot 4!} = 6300$

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

$\left\lceil \frac{60}{11} \right\rceil = 6$

objectes.

Per què. Si totes les caixes en tinguessin com a molt $5$, el total no passaria de $11\cdot5 = 55$, que és menys que $60$. 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{7}{3} = \frac{7!}{3!\,4!} = 35$

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

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

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

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