matematikk.net

(Fra boka Counting: The art of enumerative combinatorics av G. Martin, Springer)

How many ways are there to stack n poker chips, each of which can be red, white, blue, or green, under the following condition?

(a) No green chip is (directly) on top of any red chip.

(b) A green chip is never (anywhere) above some red chip

a) La det være [tex]G[/tex] grønne, [tex]R[/tex] røde, [tex]W[/tex] hvite og [tex]B[/tex] blå chips. Vi legger først alle de røde i en bunke. Deretter putter vi inn de hvite. Det kan gjøres på [tex] {R+W-1 \choose W}[/tex] måter. Nå legger vi inn de blå. Dette kan gjøres på [tex]{R+W+B-1 \choose B}[/tex] måter. Nå legger vi inn de grønne. Dette kan gjøres på [tex]{W+B+G-1 \choose G}[/tex] måter. Så det totale antallet måter å gjøre dette på er [tex]{R+W-1 \choose W} {R+W+B-1 \choose B} {W+B+G-1 \choose G}[/tex]. Hvor selvfølgelig [tex]R+W+G+B=n[/tex].

b) Jeg tror svaret er dette:

[tex]\sum_{k=0}^B\sum_{s=0}^W {R-1+B-k \choose B-k}{k+s-1 \choose s}{R+B+W-k-s-1 \choose W-s}{k+s+G-1 \choose G} [/tex] hvor vi lar [tex]{-1 \choose 0}= {0 \choose 0}=1[/tex] når de inntreffer. Men jeg er ikke sikker, og jeg har det ikke på lukket form.

plutarco skrev:(a) No green chip is (directly) on top of any red chip.

(b) A green chip is never (anywhere) above some red chip

Inkluderer ikke betingelse (b) betingelse (a)? Altså, hvis det aldri er en grønn chip over en rød, så vil det jo aldri være en grønn chip direkte over en rød heller.

Det er vel ett eller annet poeng her jeg ikke forstår i det hele tatt, tenker jeg.

I a) kan en grønn chip være over en rød så lenge det er andre farger i mellom. Det går ikke i b).