Exercicis de combinatòria i recompte

La fórmula.

$\binom{4}{2} = \frac{4!}{2!\,2!} = 6$

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

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

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

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: A apareix 3 vegades, M apareix 2 vegades, T apareix 2 vegades.

Pas 2 — la fórmula.

$\frac{10!}{3! \cdot 2! \cdot 2!} = 151200$

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

$\left\lceil \frac{13}{12} \right\rceil = 2$

objectes.

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

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

$\binom{4+3-1}{3-1} = \binom{6}{2} = 15$

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

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

$\left\lceil \frac{25}{7} \right\rceil = 4$

objectes.

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

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

$\binom{4+4-1}{4-1} = \binom{7}{3} = 35$

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

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