Hur många yatzykast finns det?

Detta kanske inte är ett så svårt problem, men jag kan säga att jag själv till en början tänkte "det där är väl enkelt" och fick fel svar. Problemet lyder kort och gott:

Hur många olika yatzykast, d.v.s. kast med fem tärningar, finns det?

Ledtråd

Ordningen spelar ju ingen roll, eftersom slaget:

$\boxed{\begin{matrix}\ \bullet&&\bullet\ \&\bullet&\\ \bullet&&\bullet\ \end{matrix}}\boxed{\begin{matrix}\ \bullet&&\bullet\ \&\bullet&\\ \bullet&&\bullet\ \end{matrix}}\boxed{\begin{matrix}\ \bullet&&\bullet\ \&\bullet&\\ \bullet&&\bullet\ \end{matrix}}\boxed{\begin{matrix}\ \bullet&&\bullet\ \&\bullet&\\ \bullet&&\bullet\ \end{matrix}}\boxed{\begin{matrix}\ \bullet&&\bullet\ \\ \bullet&\color{transparent}\bullet&\bullet \\ \bullet&&\bullet\ \end{matrix}}$

är samma som slaget

$\boxed{\begin{matrix}\ \bullet&&\bullet\ \\ \bullet&\color{transparent}\bullet&\bullet \\ \bullet&&\bullet\ \end{matrix}}\boxed{\begin{matrix}\ \bullet&&\bullet\ \&\bullet&\\ \bullet&&\bullet\ \end{matrix}}\boxed{\begin{matrix}\ \bullet&&\bullet\ \&\bullet&\\ \bullet&&\bullet\ \end{matrix}}\boxed{\begin{matrix}\ \bullet&&\bullet\ \&\bullet&\\ \bullet&&\bullet\ \end{matrix}}\boxed{\begin{matrix}\ \bullet&&\bullet\ \&\bullet&\\ \bullet&&\bullet\ \end{matrix}}$

Det gäller alltså att beräkna antalet sätt att välja ut 5 valörer av 6 med återläggning men utan hänsyn till ordningen.

Lösning:

Visa spoiler

Låt $n_1, n_2, n_3, n_4, n_5, n_6$ vara antalet ettor, tvåor, treor, fyror, femmor, eller sexor som man får vid ett givet kast.

Tupeln $(n_1, n_2, n_3, n_4, n_5, n_6)$ motsvarar nu 1-till-1 varje möjligt kast och det är således tillräckligt att räkna antalet kast sådana att

$n_1 + n_2 + n_3 + n_4 + n_5 + n_6 = 5$

där talen $n_i$ måste vara ickenegativa heltal, dvs heltal mellan eller lika med 0 och 6.

Detta kan man snabbt beräkna med lite suboptimal (python)fulkod

N = 5
count = 0

for a in range(0,N+1):
for b in range(max(N + 1 - a,1)):
for c in range(max(N + 1 - a - b,1)):
for d in range(max(N + 1 - a - b - c,1)):
for e in range(max(N + 1 - a - b - c - d, 1)):
for f in range(max(N + 1 - a - b - c - d - e,1)):
sum_of_nums = a + b + c + d + e + f
if sum_of_nums == N:
count = count + 1

print("Total count is: ", count)

>>(...)

>> Total count is: 252

Men vi kan också försöka hitta ett uttryck med kombinatoriska symboler. Jag har aldrig gillat namnet stars and bars riktigt men utifrån den metoden kan vi alltså tänka oss att vi ställer ut 5 stjärnor representerandes antalet tärningar i kastet och 5st separatorer (bars) som placeras mellan stjärnorna. Om vi tänker oss en sådan sekvens som 10 tomma poster _,_,_,_,_,_,_,_,_,_ så kan vi först placera ut 5 stars ★,_,_,_,★,★,_,★,_,★ vilket kan göras på $10 \choose 5$ sätt vartefter separatorer sätts på övriga platser ★|||★★|★|★ vilket alltså representerar en tärningsekvens via steget: ★|||★★|★|★ → 1,0,0,2,1,1 → ⚀⚃⚃⚄⚅

Alltså:

${10 \choose 5}= 252$

Fördelar med programmering är ju dock att man kan göra en lista över alla kasten och representera dem i unicode:

Visa spoiler

⚀⚀⚀⚀⚀, ⚀⚀⚀⚀⚁, ⚀⚀⚀⚁⚁, ⚀⚀⚁⚁⚁, ⚀⚁⚁⚁⚁, ⚁⚁⚁⚁⚁, ⚀⚀⚀⚀⚂, ⚀⚀⚀⚁⚂, ⚀⚀⚁⚁⚂, ⚀⚁⚁⚁⚂, ⚁⚁⚁⚁⚂, ⚀⚀⚀⚂⚂, ⚀⚀⚁⚂⚂, ⚀⚁⚁⚂⚂, ⚁⚁⚁⚂⚂, ⚀⚀⚂⚂⚂, ⚀⚁⚂⚂⚂, ⚁⚁⚂⚂⚂, ⚀⚂⚂⚂⚂, ⚁⚂⚂⚂⚂, ⚂⚂⚂⚂⚂, ⚀⚀⚀⚀⚃, ⚀⚀⚀⚁⚃, ⚀⚀⚁⚁⚃, ⚀⚁⚁⚁⚃, ⚁⚁⚁⚁⚃, ⚀⚀⚀⚂⚃, ⚀⚀⚁⚂⚃, ⚀⚁⚁⚂⚃, ⚁⚁⚁⚂⚃, ⚀⚀⚂⚂⚃, ⚀⚁⚂⚂⚃, ⚁⚁⚂⚂⚃, ⚀⚂⚂⚂⚃, ⚁⚂⚂⚂⚃, ⚂⚂⚂⚂⚃, ⚀⚀⚀⚃⚃, ⚀⚀⚁⚃⚃, ⚀⚁⚁⚃⚃, ⚁⚁⚁⚃⚃, ⚀⚀⚂⚃⚃, ⚀⚁⚂⚃⚃, ⚁⚁⚂⚃⚃, ⚀⚂⚂⚃⚃, ⚁⚂⚂⚃⚃, ⚂⚂⚂⚃⚃, ⚀⚀⚃⚃⚃, ⚀⚁⚃⚃⚃, ⚁⚁⚃⚃⚃, ⚀⚂⚃⚃⚃, ⚁⚂⚃⚃⚃, ⚂⚂⚃⚃⚃, ⚀⚃⚃⚃⚃, ⚁⚃⚃⚃⚃, ⚂⚃⚃⚃⚃, ⚃⚃⚃⚃⚃, ⚀⚀⚀⚀⚄, ⚀⚀⚀⚁⚄, ⚀⚀⚁⚁⚄, ⚀⚁⚁⚁⚄, ⚁⚁⚁⚁⚄, ⚀⚀⚀⚂⚄, ⚀⚀⚁⚂⚄, ⚀⚁⚁⚂⚄, ⚁⚁⚁⚂⚄, ⚀⚀⚂⚂⚄, ⚀⚁⚂⚂⚄, ⚁⚁⚂⚂⚄, ⚀⚂⚂⚂⚄, ⚁⚂⚂⚂⚄, ⚂⚂⚂⚂⚄, ⚀⚀⚀⚃⚄, ⚀⚀⚁⚃⚄, ⚀⚁⚁⚃⚄, ⚁⚁⚁⚃⚄, ⚀⚀⚂⚃⚄, ⚀⚁⚂⚃⚄, ⚁⚁⚂⚃⚄, ⚀⚂⚂⚃⚄, ⚁⚂⚂⚃⚄, ⚂⚂⚂⚃⚄, ⚀⚀⚃⚃⚄, ⚀⚁⚃⚃⚄, ⚁⚁⚃⚃⚄, ⚀⚂⚃⚃⚄, ⚁⚂⚃⚃⚄, ⚂⚂⚃⚃⚄, ⚀⚃⚃⚃⚄, ⚁⚃⚃⚃⚄, ⚂⚃⚃⚃⚄, ⚃⚃⚃⚃⚄, ⚀⚀⚀⚄⚄, ⚀⚀⚁⚄⚄, ⚀⚁⚁⚄⚄, ⚁⚁⚁⚄⚄, ⚀⚀⚂⚄⚄, ⚀⚁⚂⚄⚄, ⚁⚁⚂⚄⚄, ⚀⚂⚂⚄⚄, ⚁⚂⚂⚄⚄, ⚂⚂⚂⚄⚄, ⚀⚀⚃⚄⚄, ⚀⚁⚃⚄⚄, ⚁⚁⚃⚄⚄, ⚀⚂⚃⚄⚄, ⚁⚂⚃⚄⚄, ⚂⚂⚃⚄⚄, ⚀⚃⚃⚄⚄, ⚁⚃⚃⚄⚄, ⚂⚃⚃⚄⚄, ⚃⚃⚃⚄⚄, ⚀⚀⚄⚄⚄, ⚀⚁⚄⚄⚄, ⚁⚁⚄⚄⚄, ⚀⚂⚄⚄⚄, ⚁⚂⚄⚄⚄, ⚂⚂⚄⚄⚄, ⚀⚃⚄⚄⚄, ⚁⚃⚄⚄⚄, ⚂⚃⚄⚄⚄, ⚃⚃⚄⚄⚄, ⚀⚄⚄⚄⚄, ⚁⚄⚄⚄⚄, ⚂⚄⚄⚄⚄, ⚃⚄⚄⚄⚄, ⚄⚄⚄⚄⚄, ⚀⚀⚀⚀⚅, ⚀⚀⚀⚁⚅, ⚀⚀⚁⚁⚅, ⚀⚁⚁⚁⚅, ⚁⚁⚁⚁⚅, ⚀⚀⚀⚂⚅, ⚀⚀⚁⚂⚅, ⚀⚁⚁⚂⚅, ⚁⚁⚁⚂⚅, ⚀⚀⚂⚂⚅, ⚀⚁⚂⚂⚅, ⚁⚁⚂⚂⚅, ⚀⚂⚂⚂⚅, ⚁⚂⚂⚂⚅, ⚂⚂⚂⚂⚅, ⚀⚀⚀⚃⚅, ⚀⚀⚁⚃⚅, ⚀⚁⚁⚃⚅, ⚁⚁⚁⚃⚅, ⚀⚀⚂⚃⚅, ⚀⚁⚂⚃⚅, ⚁⚁⚂⚃⚅, ⚀⚂⚂⚃⚅, ⚁⚂⚂⚃⚅, ⚂⚂⚂⚃⚅, ⚀⚀⚃⚃⚅, ⚀⚁⚃⚃⚅, ⚁⚁⚃⚃⚅, ⚀⚂⚃⚃⚅, ⚁⚂⚃⚃⚅, ⚂⚂⚃⚃⚅, ⚀⚃⚃⚃⚅, ⚁⚃⚃⚃⚅, ⚂⚃⚃⚃⚅, ⚃⚃⚃⚃⚅, ⚀⚀⚀⚄⚅, ⚀⚀⚁⚄⚅, ⚀⚁⚁⚄⚅, ⚁⚁⚁⚄⚅, ⚀⚀⚂⚄⚅, ⚀⚁⚂⚄⚅, ⚁⚁⚂⚄⚅, ⚀⚂⚂⚄⚅, ⚁⚂⚂⚄⚅, ⚂⚂⚂⚄⚅, ⚀⚀⚃⚄⚅, ⚀⚁⚃⚄⚅, ⚁⚁⚃⚄⚅, ⚀⚂⚃⚄⚅, ⚁⚂⚃⚄⚅, ⚂⚂⚃⚄⚅, ⚀⚃⚃⚄⚅, ⚁⚃⚃⚄⚅, ⚂⚃⚃⚄⚅, ⚃⚃⚃⚄⚅, ⚀⚀⚄⚄⚅, ⚀⚁⚄⚄⚅, ⚁⚁⚄⚄⚅, ⚀⚂⚄⚄⚅, ⚁⚂⚄⚄⚅, ⚂⚂⚄⚄⚅, ⚀⚃⚄⚄⚅, ⚁⚃⚄⚄⚅, ⚂⚃⚄⚄⚅, ⚃⚃⚄⚄⚅, ⚀⚄⚄⚄⚅, ⚁⚄⚄⚄⚅, ⚂⚄⚄⚄⚅, ⚃⚄⚄⚄⚅, ⚄⚄⚄⚄⚅, ⚀⚀⚀⚅⚅, ⚀⚀⚁⚅⚅, ⚀⚁⚁⚅⚅, ⚁⚁⚁⚅⚅, ⚀⚀⚂⚅⚅, ⚀⚁⚂⚅⚅, ⚁⚁⚂⚅⚅, ⚀⚂⚂⚅⚅, ⚁⚂⚂⚅⚅, ⚂⚂⚂⚅⚅, ⚀⚀⚃⚅⚅, ⚀⚁⚃⚅⚅, ⚁⚁⚃⚅⚅, ⚀⚂⚃⚅⚅, ⚁⚂⚃⚅⚅, ⚂⚂⚃⚅⚅, ⚀⚃⚃⚅⚅, ⚁⚃⚃⚅⚅, ⚂⚃⚃⚅⚅, ⚃⚃⚃⚅⚅, ⚀⚀⚄⚅⚅, ⚀⚁⚄⚅⚅, ⚁⚁⚄⚅⚅, ⚀⚂⚄⚅⚅, ⚁⚂⚄⚅⚅, ⚂⚂⚄⚅⚅, ⚀⚃⚄⚅⚅, ⚁⚃⚄⚅⚅, ⚂⚃⚄⚅⚅, ⚃⚃⚄⚅⚅, ⚀⚄⚄⚅⚅, ⚁⚄⚄⚅⚅, ⚂⚄⚄⚅⚅, ⚃⚄⚄⚅⚅, ⚄⚄⚄⚅⚅, ⚀⚀⚅⚅⚅, ⚀⚁⚅⚅⚅, ⚁⚁⚅⚅⚅, ⚀⚂⚅⚅⚅, ⚁⚂⚅⚅⚅, ⚂⚂⚅⚅⚅, ⚀⚃⚅⚅⚅, ⚁⚃⚅⚅⚅, ⚂⚃⚅⚅⚅, ⚃⚃⚅⚅⚅, ⚀⚄⚅⚅⚅, ⚁⚄⚅⚅⚅, ⚂⚄⚅⚅⚅, ⚃⚄⚅⚅⚅, ⚄⚄⚅⚅⚅, ⚀⚅⚅⚅⚅, ⚁⚅⚅⚅⚅, ⚂⚅⚅⚅⚅, ⚃⚅⚅⚅⚅, ⚄⚅⚅⚅⚅, ⚅⚅⚅⚅⚅

Snyggt!

Det du gjorde med stars and bars var i princip lösningen jag hade i åtanke, men jag brukar skippa 'härledningen' med stars and bars och direkt använda formeln:

$\begin{pmatrix}n+k-1\\k\end{pmatrix}$

som ger antalet sätt att välja ut $k$ element ur $n$ med återläggning och utan hänsyn till ordningen.

Men du gick dessutom steget längre och tog fram alla kombinationer med hjälp av programmering. Jag önskar att jag själv kommit på det där med unicode-tärningarna!

Svara Avbryt