Welcome to EverybodyWiki ! Nuvola apps kgpg.png Sign in or create an account to improve, watchlist or create an article like a company page or a bio (yours ?)...

Stars and bars (kombinatorik)

Från EverybodyWiki Bios & Wiki
Hoppa till navigering Hoppa till sök

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.

Användningsområden[redigera]

I grundläggande kombinatorik finns det fyra olika sätt att räkna ut antalet kombinationer det går att mixa N möjligheter i K indelningar:

  1. Upprepning tillåtet och ordning har betydelse
  2. Upprepning inte tillåtet och ordning har betydelse
  3. Upprepning tillåtet och ordning har inte betydelse
  4. Upprepning inte tillåtet och ordning har inte betydelse

Det som menas med att upprepning är tillåtet är att man får upprepa samma tal flera gånger, T.e.x, säg att Berta har 10 bollar som hon ska dela in i 2 korgar. Om hon nu skulle få dela det jämt så att korg 1 skulle kunna ha fem bollar och korg 2 de andra fem hade det räknats som att upprepning hade varit tillåtet då det i en talföljd hade skrivits: [5, 5]

"Ordningen har betydelse" handlar om att ordningen på indelningen har betydelse. Exempelvis om det skulle skrivas in ett lösenord till ett konto hade lösenordet [145] inte varit samma som lösenordet [541] eller [415] eftersom ordningen spelar roll och 1,2 inte är samma som 2,1.

Varje sätt att räkna ut kombinationerna har sina egna formler och logiska förklaringar. Stars and bars riktar sig specifikt mot det tredje alternativet [Upprepning tillåtet och Ordning har inte betydelse]. Stars and bars används därefter som en grafisk och logisk förklaring till binomialkoefficienten '"`UNIQ--postMath-00000001-QINU`"'eller '"`UNIQ--postMath-00000002-QINU`"'som man båda använder för att räkna ut antalet kombinationer genom alternativ tre. Ett exempel på ett sådant problem skulle som nämnt ovan kunna vara hur många sätt det finns att lägga '"`UNIQ--postMath-00000003-QINU`"' antal bollar i '"`UNIQ--postMath-00000004-QINU`"' antal korgar då det går lägga samma antal bollar i flera korgar[Upprepning tillåtet] och inte spelar någon roll om vilken korg som är vilken[Ordning har inte betydelse].

Visualisering/Exempel[redigera]

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.

2 | 6 | 2

(Notera att det finns tre korgar men bara två |. Eftersom antalet | som används är '"`UNIQ--postMath-00000005-QINU`"')

Stars and bars går därefter ut på att komma på antalet sätt det är möjligt att sätta ut gallret(|) på. För att komma på antalet sätt att sätta ut gallret på utnyttjar man de olika teorierna .

De olika teorierna[redigera]

Stars and bars metoden kan vanligtvis användas på två olika sätt:

Teori 1[redigera]

Den första teorin gäller när komponenterna i k-tupeln endast får bestå av positiva tal som 1 och uppåt. I det tidigare exemplet skulle detta betyda att alla korgar(komponenterna) måste ha minst en boll per korg.

Teori 2[redigera]

Den andre teorin gäller när komponenterna i k-tupeln endast får bestå av icke-negativa tal som 0 och uppåt. Skillnaden mellan positiva och icke-negativa tal ligger i att man får räkna med noll i icke-negativa tal. Så en korg i det tidigare exemplet skulle kunna ha noll bollar i sig.

Tillämpning av teorierna[redigera]

De två teorierna kan användas på "boll och korg-problemet":

Teori 1[redigera]

10 bollar representerade i Stars and Bars format:

★★★★★★★★★★

För att räkna ut antalet sätt att fördela dem i korgarna måste vi först se på hur många sätt det går att lägga ut gallret med |. Ett sätt enligt den första teorin skulle kunna vara som i det tidigare exemplet:

★★|★★★★★★|★★ => [2,6,2]

Det kan också vara:

★|★★★★★|★★★★ => [1, 5, 4]

Men det kan inte vara:

|★★★★★★★★★★| => [0, 10, 0]

.Detta beror på att den enda regeln enligt Teori 1 är att k-tupelns komponenter endast får bestå av positiva heltal, och; 0 är inte ett positivt heltal. Enligt |★★★★★★★★★★| skulle det betyda att korg 1 och korg 3 skulle ha 0 bollar i sig vilket inte är tillåtet enligt Teori 1. En | måste alltså hela tiden vara mellan två stjärnor om inte en korg ska ha noll bollar i sig. Markera alla ställen där det skulle gå att sätta en | enligt följande:

★|★|★|★|★|★|★|★|★|★

Antalet | är 9.

Det betyder att det går att sätta ut | på 9 olika ställen, vilket motsvarar '"`UNIQ--postMath-00000006-QINU`"'. Det är möjligt att lägga ut en | efter varje stjärna utom den sista eftersom den sista | då bara skulle ha en stjärna bredvid sig.

Teori 2[redigera]

Den enda regeln enligt teori 2 är att k-tupelns komponenter endast får bestå av icke-negativa tal. Det betyder att en korg även får ha noll bollar i sig. Så följande arrangemang:

|★★★★★★★★★★| => [0, 10, 0]

där korg 1 och 3 skulle haft noll bollar i sig är tillåtet. En | måste hela tiden vara mellan en 0-a eller en annan |. Om vi nu markerar ut alla ställen där vi skulle kunna sätta en | skulle det se ut så här:

|★|★|★|★|★||★|★|★|★|★|

Man kan alltså lägga ut två | precis bredvid varandra då en tom korg skulle finnas mellan dem:

|★||★ => [1, 0, 1]

Det betyder att antalet ställen vi skulle kunna lägga ut | på är 12, vilket stämmer motsvarar formeln '"`UNIQ--postMath-00000007-QINU`"'. Enda skillnaden mot den förra formeln '"`UNIQ--postMath-00000008-QINU`"' är att man lägger till k eftersom man nu kan lägga ut en extra | för varje ny | vi får. Och '"`UNIQ--postMath-00000009-QINU`"' är samma som antalet korgar och '"`UNIQ--postMath-0000000A-QINU`"' antalet | vi har. Varje gång vi får en ny | så lägger vi det bara bredvid en annan |:

Ex.

Vi återigen 10 bollar:

★|★|★|★|★|★|★|★|★|★ => '"`UNIQ--postMath-0000000B-QINU`"'

★|★|★|★|★|★|★|★|★|★|||||||| => '"`UNIQ--postMath-0000000C-QINU`"'

Formlerna[redigera]

Formlerna för att räkna ut antalet kombinationer är:

  • '"`UNIQ--postMath-0000000D-QINU`"'=> Teori 1
  • '"`UNIQ--postMath-0000000E-QINU`"'=> Teori 2

Två | får inte hamna på samma ställe vilket reducerar antalet möjligheter. För varje ny | måste vi ta bort ett av ställena vi kan sätta den nya på då en annan | redan täcker den enligt följande:

★★★★★|★★★★★ => När vi bara har en | kan vi lägga den varsomhelst.

★★★★★|★|★★★★ => Lägger vi dit en ny | kan vi lägga den på alla ställen förutom var den förra var

★★|★★★|★|★★★★ => Lägger vi dit en till | kan vi lägga den på alla ställen utom där de två andra är.

och så vidare.

Problemlösning/boll-till korg problem[redigera]

Sture har 10 bollar som han vill fördela mellan 5 korgar. Hur många möjliga fördelningar finns det om varje korg måste ha minst en boll i sig? Flera korgar får ha lika många bollar och ordningen har ingen betydelse.

Från "Flera korgar får ha lika många bollar" går det dra slutsatsen att upprepning är tillåten och från den sista frasen att ordningen inte har någon betydelse. Dessutom från "varje korg måste minst ha en boll i sig" att Stars and bars teori 1 kan tillämpas.

10 bollar och 5 korgar betyder att '"`UNIQ--postMath-0000000F-QINU`"' och '"`UNIQ--postMath-00000010-QINU`"'. Ett möjligt utfall skulle då kunna vara ★|★★★|★★|★★★|★ vilket då skulle representera [1, 3, 2, 3, 1]. Formeln för att räkna ut antal möjliga utfall:

'"`UNIQ--postMath-00000011-QINU`"'= '"`UNIQ--postMath-00000012-QINU`"'= '"`UNIQ--postMath-00000013-QINU`"' = '"`UNIQ--postMath-00000014-QINU`"'= '"`UNIQ--postMath-00000015-QINU`"' = '"`UNIQ--postMath-00000016-QINU`"' = '"`UNIQ--postMath-00000017-QINU`"' = '"`UNIQ--postMath-00000018-QINU`"'

Svar: 126 möjligheter.

Se också[redigera]

  • Tolvfaldiga vägen
  • Binomialkoefficient
  • Permutation
  • Kombinatorik

Referenser[redigera]

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

[1] [2] [3]

[4]


Do you like this article ? You can add up to 5 stars (you must be logged in) ! See the most liked articles.

0.00
(0 röster)

Den här artikeln "Stars and bars (kombinatorik)" är från wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Stars and bars (kombinatorik).


Compte Twitter EverybodyWiki Follow us on https://twitter.com/EverybodyWiki !

Farm-Fresh comment add.png You have to Sign in or create an account to comment this article !