Kombinatorik: På hur många sätt kan vi måla en karusell
Jag har stött på följande problem i kursen Algebra och kombinatorik:
På hur många sätt kan man måla 10 identiska hästar i en karusell så att tre av dem är bruna, tre är blå och fyra är svarta? Eftersom karusellen roterar räknas uppställningar som kan överföras till varandra genom rotation som lika.
Jag misstänker att det totala antalet sätt att måla karusellen på är då det är 10 hästar totalt och tre bruna respektive blåa samt fyra svarta. Men hur räknar man sedan ut antalet sätt som uppställningarna räknas lika vid?
Rotationen borde identifiera färgläggningar tio och tio.
Om vi antar att vi dessutom målar dit ett nummer från 1 till 10 på hästarna så försvinner likheten vid rotation.
Att i sådant fall välja ut tre av tio att vara bruna kan ske på 10 över 3 vis.
Att sedan välja ut tre av kvarvarande sju att vara blå kan ske på 7 över 3 vis.
Att sedan välja ut fyra av kvarvarande fyra att vara svarta kan ske på 4 över 4 vis, vilket multiplicerat samman ger det du säger, dvs 4200.
En gångbar kombination ges då av(om vi använder vokalen i färgnamnet för att beteckna färgen):
uuuåååaaaa
Om vi nu roterar karusellen så kommer vi se följande kombinationer dyka upp:
uuåååaaaau
uåååaaaauu
åååaaaauuu
ååaaaauuuå
åaaaauuuåå
aaaauuuååå
aaauuuåååa
aauuuåååaa
auuuåååaaa
Med andra ord kan man från en färgsättning bilda 10 stycken färgsättningar genom rotation. Eftersom att alla färgsättningarna jag skrev ovan finns med bland de 4200 trots att de bör räknas som en färgsättning innebär det att endast var tionde färgsättning verkligen är ett unikt sätt att måla hästarna på, vilket borde ge att det riktiga svaret är 4200/10= 420 kombinationer.
Det skulle vara ett roligare problem om det fanns rotationer mindre än ett helt varv som avbildar en färgläggning på sig själv. Om det var 12 hästar skulle det hända lättare.
det borde finnas rotationer på 2 eller 5 steg som avbildar en färgsättning på en annan, för vissa färgsättningar. Jag tror att detta måste med i svaret på nåt sätt.
Hilda skrev:det borde finnas rotationer på 2 eller 5 steg som avbildar en färgsättning på en annan, för vissa färgsättningar. Jag tror att detta måste med i svaret på nåt sätt.
Om man roterar 5 steg byter man ut en grupp på 5 hästar mot den andra gruppen av 5 hästar. Men det kan omöjligt finnas lika många bruna eller blå hästar i båda grupperna, eftersom det finns ett udda antal sådana. Så hur skulle en sådan färgsättning se ut?
Om n hästar målas i k färger så att det finns n_1, n_2, n_3,...,n_k hästar av färg i så uppstår situationen att en rotation avbildar en färgsättning på sig själv om och endast om sgd(n_1,n_2,...,n_k)>1.
Om man exvis har 10 hästar och målar 5 röda, 5 vita, så finns färgläggningen med varannan röd varannan vit som stöter på detta problem.
Antag att en rotation med d steg avbildar färgläggningen på sig själv, då finns lika många hästar av en viss färg i varje spann av d hästar. Det finns n/d sådana spann. Så varje n_i är delbart med n/d.
I vårt fall är SGD(4,3,3)=1 och det n/d som delar 1 är 1, dvs d=10, dvs endast hela varvet avbildar färgläggningen på sig själv.
