(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
kombinatorikk
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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.
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.
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.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
Det er vel ett eller annet poeng her jeg ikke forstår i det hele tatt, tenker jeg.