Anzahl der Permutationen, die Nebenbedingungen erfüllen

16/10/2008 - 13:38 von Lars Rohwedder | Report spam
Hallo,

beim Brüten über eine inkrementelle Grafikübertragung (bzw. wahlweise:
verlustbehaftete Kodierung, wenn man die "Übertragung" vorzeitig
abbricht) bin ich auf ein interessantes Problem gestoßen, für das mir
so spontan keine Lösung eingefallen ist, vielleicht habt ihr da ja
Ideen dazu.

Als mathematische Problemstellung auf das Relevante eingedampft:

Ich habe eine 24-elementige Menge:

{ y_0, y_1, y_2, ..., y_7, s_0, s_1, ..., s_7, d_0, ..., d_7 }.

(Wen es interessiert:
Es sind 3 Farbkanàle Y, S, D mit jeweils den Bits 0...7 :-)
)

Die Anzahl aller möglichen Permutationen ist 24!. Nun möchte ich aber
nur die Permutationen, die gewisse Nebenbedingungen erfüllen:

y_i < y_{i-1} für alle i \in {0,1,2,3,4,5,6}
s_i < s_{i-1} für alle i \in {0,1,2,3,4,5,6}
d_i < d_{i-1} für alle i \in {0,1,2,3,4,5,6}
y_i < s_i für alle i \in {0,1,2,3,4,5,6,7}
s_i < d_i für alle i \in {0,1,2,3,4,5,6,7}

"<" meint hierbei: das linke Element kommt in der Liste vor dem rechten
Element.
(Soll heißen: für jeden Farbkanal soll ein höherwertiges Bit vor den
niederwertigeren des gleichen Kanals drankommen, und bei gleicher
Bitwertigkeit soll das Y-Bit vor dem zugehörigen S- und dieses vor dem
zugehörigen D-Bit drankommen.)

Zwei naheliegende Reihenfolgen wàren also:

A) y_7, y_6, y_5, ... y_0, s_7, s_6, ... s_0, d_7, ... d_0.
B) y_7, s_7, d_7, y_6, s_6, d_6, ... , y_0, s_0, d_0.

Wie viele Permutationen, die die obigen 5 Bedingungen erfüllen, gibt
es insgesamt?

Lars R.
 

Lesen sie die antworten

#1 Hero
17/10/2008 - 18:32 | Warnen spam
Lars wrote:


Als mathematische Problemstellung auf das Relevante eingedampft:

Ich habe eine 24-elementige Menge:

 { y_0, y_1, y_2, ..., y_7, s_0, s_1, ..., s_7, d_0, ..., d_7 }.

(Wen es interessiert:
 Es sind 3 Farbkanàle Y, S, D mit jeweils den Bits 0...7 :-)
)

Die Anzahl aller möglichen Permutationen ist 24!. Nun möchte ich aber
nur die Permutationen, die gewisse Nebenbedingungen erfüllen:

        y_i < y_{i-1}  für alle i \in {0,1,2,3,4,5,6}
        s_i < s_{i-1}  für alle i \in {0,1,2,3,4,5,6}
        d_i < d_{i-1}  für alle i \in {0,1,2,3,4,5,6}
        y_i < s_i      für alle i \in {0,1,2,3,4,5,6,7}
        s_i < d_i      für alle i \in {0,1,2,3,4,5,6,7}

"<" meint hierbei: das linke Element kommt in der Liste vor dem rechten
Element.
(Soll heißen: für jeden Farbkanal soll ein höherwertiges Bit vor den
niederwertigeren des gleichen Kanals drankommen, und bei gleicher
Bitwertigkeit soll das Y-Bit vor dem zugehörigen S- und dieses vor dem
zugehörigen D-Bit drankommen.)

Zwei naheliegende Reihenfolgen wàren also:

  A)  y_7, y_6, y_5, ... y_0, s_7, s_6, ... s_0, d_7, ... d_0.
  B)  y_7, s_7, d_7, y_6, s_6, d_6, ... , y_0, s_0, d_0.

Wie viele Permutationen, die die obigen 5 Bedingungen erfüllen, gibt
es insgesamt?




Vielleicht hilft ein analoges Problem. Du baust drei Reihen á acht
würfelförmigen Bauklötze auf und zwar in einem offenen Karton in einer
seiner Ecken. Nun stellst Du den Karton hochkant und drehst ihn
vorsichtig auf eine Kante.
Jede Permutation entspricht nun einer Reihenfolge, in der Du die
Bauklötze einzeln entfernen kannst, ohne daß die anderen tiefer
rutschen. Die Plàtze der Würfel kann man ja vorher schachbrettartig
entsprechend mit s,y und d und den Ziffern beschriften.
Mit freundlichen Grüßen
Hero

Ähnliche fragen