Barres i estreles (combinatòria)

En combinatòria, el diagrama de barres i estreles és una ajuda gràfica per a derivar certes teoremes combinatoris. Va ser popularisat per William Feller en el seu clàssic llibre sobre provabilitat. Es pot utilisar per a resoldre molts problemes de conteo simples, com a quantes formes hi ha de colocar $n$ boles indistinguibles en $k$ contenidors distinguibles.^[1]

Enunciats de teoremes

El método de les barres i les estreles a sovint s'introduïx específicament per a demostrar els següents dos teoremes d'combinatoria elemental relacionats en el kontolo de solucions d'una equació.

Primera teorema

Per a qualsevol parell de sancers positius $n$ i $k$ , el número de $k$ -tuplas de sancers positius que la seua suma és $n$ és igual al número de subconjunts de $k - 1$ elements d'un conjunt en $n - 1$ elements.

Per eixemple, si $n = 10$ i $k = 4$ , la teorema dona el número de solucions de $x_{1} + x_{2} + x_{3} + x_{4} = 10$ (en sancers $x_{1}, x_{2}, x_{3}, x_{4} > 0$ ) com el coeficient binomial

(\binom{n - 1}{k - 1}) = (\binom{10 - 1}{4 - 1}) = (\binom{9}{3}) = 84.

Açò correspon al número de composicions d'un número entero.

Segona teorema

Per a qualsevol parell de sancers positius $n$ i $k$ , el número de $k$ -tuplas de sancers no negatius que la seua suma és $n$ és igual al número de multiconjuntos de cardinalidad $n$ presos d'un conjunt de tamany $k$ , o equivalentemente, el número de multiconjuntos de cardinalidad $k - 1$ pres d'un conjunt de tamany $n + 1$ .

Per eixemple, si $n = 10$ i $k = 4$ , la teorema dona el número de solucions de $x_{1} + x_{2} + x_{3} + x_{4} = 10$ (en sancers $x_{1}, x_{2}, x_{3}, x_{4} \geq 0$ ) com:

((\binom{k}{n})) = (\binom{k + n - 1}{n}) = (\binom{13}{10}) = 286

((\binom{n + 1}{k - 1})) = (\binom{n + 1 + k - 1 - 1}{k - 1}) = (\binom{13}{3}) = 286

(\binom{n + k - 1}{k - 1}) = (\binom{10 + 4 - 1}{4 - 1}) = (\binom{13}{3}) = 286

Açò correspon al número de composicions dèbils d'un número entero.

Demostracions per mig del método d'estreles i agranes

Demostració de la primera teorema

Supongam que hi ha n objectes (representats ací per estreles) que es colocaran en k contenidors, de modo que tots els contenidors continguen a lo manco un objecte. Els contenidors són distinguibles (digam que estan numerats d'1 a k), pero les n estreles no ho són (per lo que les configuracions solament es distinguixen pel número d'estreles presents en cada contenidor). Per tant, una configuració es representa per mig d'una k-tupla de sancers positius, com en l'enunciat de la teorema (el número d'elements de cada contenidor

Per eixemple, en $n = 7$ i $k = 3$ , comença colocant les estreles en una llínea:

★ ★ ★ ★ ★ ★ ★

Fig. 1: Sèt objectes, representats per estreles

La configuració quedarà determinada una volta que se sàpia quin és la primera estrela que va al segon contenidor, quin és la primera estrela que va al tercer contenidor, etc. Açò s'indica colocant $k - 1$ barres entre les estreles (separadores entre contenidors). Degut a que no es permet que cap contenidor estiga buit (totes les variables són positives), hi ha com a màxim una barra entre qualsevol parell d'estreles.

Per eixemple:

★ ★ ★ ★ | ★ | ★ ★

Fig. 2: Les dos barres donen lloc a tres contenidors en, respectivament, 4, 1 i 2 objectes.

Hi ha $n - 1$ espais entre estreles. S'obté una configuració elegint $k - 1$ d'estos espais per a contindre una barra. El número de formes d'elegir $k - 1$ espais d'entre un total de $n - 1$ és el número de subconjunts de $k - 1$ elements d'un de $n - 1$ . Per lo tant, per definició, hi ha $(\binom{n - 1}{k - 1})$ possibles combinacions. $◻$

Demostració de la segona teorema

En este cas, es debiliten les restriccions: es demana la no negatividad en lloc de la positividad. Açò significa, utilisant les barres i estreles anteriors, que podem colocar múltiples barres entre estreles, abans de la primera estrela i despuix de l'última estrela (permetem contenidors buits).

Per eixemple, quan $n = 7$ i $k = 5$ , la 5-tupla (4, 0, 1, 2, 0) es pot representar per mig del següent diagrama:

★ ★ ★ ★ | | ★ | ★ ★ |

Fig. 3: Quatre barres donen lloc a cinc contenidors en 4, 0, 1, 2 i 0 objectes, respectivament.

Per a vore que hi ha $(\binom{n + k - 1}{k - 1})$ possibilitats, observem que qualsevol disposició d'estreles i barres consta d'un total de $n + k - 1$ objectes, n dels quals són estreles i $k - 1$ dels quals són barres. Per lo tant, solament necessitem elegir $k - 1$ de les $n + k - 1$ posicions per a que siguen barres (o, de manera equivalent, elegir n de les posicions per a que siguen estreles), puix el restant quedaran determinades a ser estreles (o, equivalentemente, barres). $◻$

La primera teorema es pot ara reformular en térmens del segon, perque el requisit de que totes les variables són positives equival a assignar prèviament a cada variable un 1 i preguntar el número de solucions quan cada variable no és negativa.

Per eixemple:

x_{1} + x_{2} + x_{3} + x_{4} = 10

en $x_{1}, x_{2}, x_{3}, x_{4} > 0$

és equivalent a:

x_{1} + x_{2} + x_{3} + x_{4} = 6

en $x_{1}, x_{2}, x_{3}, x_{4} \geq 0$

Referències

↑ Feller, William (1950). An Introduction to Probability Theory and Its Applications, 3rd edició, Wiley, p. 38.

Bibliografia

Pitman, Jim (1993). Probability, Berlin: Springer-Verlag. ISBN 0-387-97974-3.
Weisstein. «Multichoose». Mathworld -- A Wolfram Web Resource. Consultat el 2012-11-18.

Este artícul conté una traducció derivada de «Barras y estrellas (combinatoria)» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Feller, William (1950). An Introduction to Probability Theory and Its Applications, 3rd edició, Wiley, p. 38.

[1]