Exercicis de combinatòria i recompte

La fórmula.

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

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

$\binom{5+3-1}{3-1} = \binom{7}{2} = 21$

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

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 2 vegades, L apareix 3 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 $31$ objectes en $5$ caixes, alguna caixa conté com a mínim

$\left\lceil \frac{31}{5} \right\rceil = 7$

objectes.

Per què. Si totes les caixes en tinguessin com a molt $6$, el total no passaria de $5\cdot6 = 30$, que és menys que $31$. 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}{5} = \frac{5!}{5!\,0!} = 1$

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

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

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

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

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

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

Pas 2 — la fórmula.

$\frac{6!}{2! \cdot 2!} = 180$

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

$\left\lceil \frac{200}{26} \right\rceil = 8$

objectes.

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

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

$\binom{5+5-1}{5-1} = \binom{9}{4} = 126$

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

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