Método bóla trazo

En combinatoria, o método bóla trazo (tamén chamado estrelas e barras , paus e pedras,, bólas e barras e puntos e divisores) é unha axuda gráfica para deducir certos teoremas combinatorios. Pode empregarse para resolver diversos problemas de contaxe, como por exemplo determinar cantas formas hai de colocar  bólas indistinguíbeis en  caixas distinguíbeis.  A solución a este problema concreto vén dada polo coeficiente binomial , que é o número de subconxuntos de tamaño  que se poden formar a partir dun conxunto de tamaño .

Por exemplo, se hai dúas bólas e tres caixas, o número de formas de colocar as bólas é . A táboa amosa as seis formas posíbeis de distribuír as dúas bólas, as cadeas de estrelas e barras que as representan (coas estrelas indicando bólas e as barras separando unhas caixas doutras), e os subconxuntos que corresponden a esas cadeas. Como se precisan dúas barras para separar tres caixas e hai dúas bólas, cada cadea contén dúas barras e dúas estrelas. Cada subconxunto indica cales dos catro símbolos na cadea correspondente son barras.
+ Seis configuracións de dúas bólas en tres caixas e a súa representación con estrelas e barras Caixa 1  Caixa 2  Caixa 3  Cadea  Subconxunto de {1,2,3,4} 2  0  0  ★ ★ | |  {3,4} 1  1  0  ★ | ★ |  {2,4} 1  0  1  ★ | | ★  {2,3} 0  2  0  | ★ ★ |  {1,4} 0  1  1  | ★ | ★  {1,3} 0  0  2  | | ★ ★  {1,2}

Notas

Categoría:Combinatoria