Stars and bars

Stars and bars är ett grafiskt hjälpmedel som används för att lösa kombinatoriska problem. Det kan bland annat användas till att beräkna antalet sätt man kan lägga n bollar i k korgar.

Stars and bars används inom kombinatorikfallet [Upprepning tillåtet och Ordning har inte betydelse]. Stars and bars används som en grafisk och logisk förklaring till binomialkoefficienten ${\bigl (}{\begin{smallmatrix}n-1\\k-1\end{smallmatrix}}{\bigr )}$eller ${\bigl (}{\begin{smallmatrix}k+n-1\\k-1\end{smallmatrix}}{\bigr )}$som man båda använder för att räkna ut antalet kombinationer

Visualisering

Säg att det finns 10 bollar som ska fördelas i 3 korgar. På hur många sätt kan bollarna fördelas?

Ett sätt att lägga ut bollarna skulle kunna vara: |Korg 1, 2 bollar| |Korg 2, 6 bollar| |Korg 3, 2 bollar|.

Skulle man sen lägga in det i en talföljd [2, 6, 2] kan det även representeras i Stars and Bars:

★★|★★★★★★|★★ ⇒ Varje ny korg representeras av ett |- tecken.

Se även

• Tolvfaldiga vägen
• Permutation

Källor

• ”Stars and Bars Questions | Permutations and Combinations” (på engelska). https://www.youtube.com/watch?v=qvqPZkPURCo. Läst 31 augusti 2019. 
• ”Integer Equations - Stars and Bars | Brilliant Math & Science Wiki” (på amerikansk engelska). brilliant.org. https://brilliant.org/wiki/integer-equations-star-and-bars/. Läst 31 augusti 2019. 
• ”Kombinationer (Matte 5, Kombinatorik)”. Matteboken. https://www.matteboken.se/lektioner/matte-5/kombinatorik/kombinationer. Läst 31 augusti 2019. 
• ”combinatorics - How to use stars and bars?”. Mathematics Stack Exchange. https://math.stackexchange.com/questions/910809/how-to-use-stars-and-bars. Läst 31 augusti 2019. 

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Stars and bars (combinatorics), 14 augusti 2019.