Einfaches kompliziertes Kombinatorik-Problem

21/12/2010 - 19:42 von Jürgen Will | Report spam
Hallo,

für eine Problemstellung aus der Praxis muß ich folgendes Kombinatorische
Problem lösen.

Es seien c[1], c[2], ..., c[n], k[1], k[2], ..., k[n], n vorgegebene
nichtnegative Ganze Zahlen und a[0], a[1], ..., a[n] leere Variablen.

Ferner sei A = (a[0] + a[1])^k[1] * (a[0] + a[1] + a[2])^k[2] * (a[0] + a[1]
+ a[2] + a[3])^k[3] * ... * (a[0] + a[1] + ... + a[n])^k[n].

Durch welchen Ausdruck/welche Formel kann der Koeffizient des gegebenen
Gliedes a[0]^c[0]*a[1]^c[1]*a[2]^c[2]* ... * a[n]^c[n] in A berechnet
werden? Der Ausdruck soll nach Möglichkeit gleich in Form Kombinatorischer
Formeln oder mit Hilfe Kombinatorischer Anzahlen ausgedrückt werden, z. B.
mit Hilfe von Multinomialkoeffizienten, Partitionen, Kompositionen,
Gewöhnlichen Partiellen Bell-Polynomen oder Zyklenzeigern von
zusammengesetzten Permutationsgruppen.

Die einzelnen Faktoren (a[0] + a[1] + ... + a[m])^k[m] lassen sich ja über
das Multinomialtheorem expandieren. Das ergibt einen Vorrat an
Einzelgliedern. Wie kann ich aber aus den gegebenen c[i] ermitteln, welche
der Einzelglieder miteinander kombiniert werden müssen, um das gegebene
Glied zu konstruieren?

Bin kein Mathematiker.

Danke!
 

Lesen sie die antworten

#1 Bastian Erdnuess
22/12/2010 - 03:08 | Warnen spam
Jürgen Will wrote:

Hallo,

für eine Problemstellung aus der Praxis muß ich folgendes Kombinatorische
Problem lösen.

Es seien c[1], c[2], ..., c[n], k[1], k[2], ..., k[n], n vorgegebene
nichtnegative Ganze Zahlen und a[0], a[1], ..., a[n] leere Variablen.



c[0] wird auch noch gebraucht, und ich will auch nochmal k[0] = 0 mit
dazu nehmen und ...

Ferner sei A = (a[0] + a[1])^k[1] * (a[0] + a[1] + a[2])^k[2] * (a[0] + a[1]
+ a[2] + a[3])^k[3] * ... * (a[0] + a[1] + ... + a[n])^k[n].



... A mit a[0]^k[0] * (a[0] + a[1])^k[1] * ... starten.

Es sind dann k,c e IN^(n+1) Vektoren mit n+1 nicht negativen
ganzzahligen Komponenten (0 e IN). Auf denen bezeichne ich mit |.| die
1-Norm |k| = sum[j=0..n] k[j] = k[0] + ... + k[n]. Außerdem bette ich
den IN^m in den IN^(m+l) ein, indem ich einfach l 0er an die Komponenten
des ersten Vektors anfüge.

Durch welchen Ausdruck/welche Formel kann der Koeffizient des gegebenen
Gliedes a[0]^c[0]*a[1]^c[1]*a[2]^c[2]* ... * a[n]^c[n] in A berechnet
werden? Der Ausdruck soll nach Möglichkeit gleich in Form Kombinatorischer
Formeln oder mit Hilfe Kombinatorischer Anzahlen ausgedrückt werden, z. B.
mit Hilfe von Multinomialkoeffizienten, Partitionen, Kompositionen,
Gewöhnlichen Partiellen Bell-Polynomen oder Zyklenzeigern von
zusammengesetzten Permutationsgruppen.



Ich nenne den Koeffizient von a[0]^c[0]*...*a[n]^c[n] mal g(c).
Offensichtlich muss |k| = |c| sein, damit g(c) =/= 0 sein kann. Man
kann nun g(c) als

g(c) = sum( prod( M(q(j)), j=0..n ), für all i = 0..n :
q(i) e IN^(i+1) : |q(i)| = k[i], sum_i q(i) = c )

schreiben, wobei M(q) den Multinomialkoeffizient

M(q) = (q[0] + ... + q[m])! / (q[0]! * ... * q[m]!)

bezeichnet und in sum_i q(i) = c die oben erwàhnte Einbettung des IN^m
in den IN^(m+l) gebraucht wurde.

Die einzelnen Faktoren (a[0] + a[1] + ... + a[m])^k[m] lassen sich ja über
das Multinomialtheorem expandieren. Das ergibt einen Vorrat an
Einzelgliedern. Wie kann ich aber aus den gegebenen c[i] ermitteln, welche
der Einzelglieder miteinander kombiniert werden müssen, um das gegebene
Glied zu konstruieren?

Bin kein Mathematiker.



Dann mal ein Beispiel. Sei n = 2 und k = (0,3,1). Es ist dann

A = a[0]^0 * (a[0] + a[1])^3 * (a[0] + a[1] * a[2])^1
= (a[0]^3 + 3*a[0]^2*a[1] + 3*a[0]*a[1]^2 + a[1]^3) *
(a[0] + a[1] + a[2])
= a[0]^4 + 4*a[0]^3*a[1] + a[0]^3*a[2] + 6*a[0]^2*a[1]^2 +
3*a[0]^2*a[1]*a[2] + 4*a[0]*a[1]^3 + 3*a[0]*a[1]^2*a[2] +
a[1]^4 + a[1]^3*a[2]

Zunàchst fàllt auf, dass sich tatsàchlich in jedem Summanden die
Exponenten der a[i] zu 4 summieren. Gesucht sei nun g(c) für
c = (1,3,0), also der Koeffizient von a[0]^3*a[1].

Laut obiger Formel gilt

g(c) = sum( prod( M(q(j)), j=0..2 ), für all i = 0..2 :
q(i) e IN^(i+1) : |q(i)| = k[i], sum_i q(i) = (1,3,0) )
= sum( M(q(0)) * M(q(1) * M(q(2)),
q(0) e IN, q(1) e IN^2, q(2) e IN^3 :
q(0) = 0, |q(1)| = 3, |q(2)| = 1, sum_i q(i) = (1,3,0) )
= sum( M(q(1) * M(q(2)),
q(1) e IN^2, q(2) e IN^3 :
|q(1)| = 3, |q(2)| = 1, sum_i q(i) = (1,3,0) )

Dafür gibt es nur die beiden Möglichkeiten

q(1) = (1,2,0) und q(2) = (0,1,0) => M(q(1)) * M(q(2)) = 3 und
q(1) = (0,3,0) und q(2) = (1,0,0) => M(q(1)) * M(q(2)) = 1

Daher ergibt sich richtig

g(c) = 3 + 1 = 4 .

Etwas intuitiver làsst sich obige Summe vielleicht verstehen, wenn man
sie so betrachtet: Gesucht sind alle unteren Dreiecks
(n+1)x(n+1)-Matrizen über IN, bei denen sich die i-te Zeile zu k[i]
summiert und die j-te Spalte zu c[j] (jeweils von 0 an zàhlend).

Dann werden für jede solche Matrix die Multinomialkoeffizienten über die
Zeilen gebildet und miteinander multipliziert. Die Produkte, die sich
so für jede solche Matrix ergeben werden aufsummiert und geben so den
gesuchten Koeffizienten.

Im obigen Beispiel waren die beiden Matrizen

1 3 0 1 3 0
0 [0 O O] 1 0 [0 O O] 1
3 [1 2 O] 3 und 3 [0 3 O] 1
1 [0 1 0] 1 1 [1 0 0] 1

3 1 --> 4

Links stehen jeweils die Zeilensummen (bzw. k), oben stehen die
Spaltensummen (bzw. c), rechts stehen die Multinomialkoeffizenten,
unten deren Produkt und ganz rechts das Ergebnis. Die 0er, die in den
Matrizen wegen der Dreiecksgestalt dastehen müssen hab ich als O statt
als 0 geschrieben.

Alternativ kann man übrigens auch für jede Matrix die
Multinomialkoeffizienten über die Spalten bilden und miteinander
multiplizieren. Wenn man die dann alle aufsummiert, muss man die
Summe nur noch mit M(c)/M(k) multiplizieren und kommt so auch zum
richtigen Ergebnis.

Das eigentliche kombinatorische Problem liegt jetzt noch daran, wie man
all diese Matrizen Q bekommt. Wenn man es aber mal an ein paar
Beispielen ausprobiert, sieht man, dass sie sich relativ einfach
systematisch aufzàhlen lassen.

Ich hoff ich hab keine allzu groben Fehler gemacht. Wenn irgendwas
nicht passt oder nicht aufgeht, kann es auch daran liegen, dass es
einfach nicht stimmt. Ich hab das nàmlich nirgendswo abgeschrieben.

Gruß,
Bastian

Ähnliche fragen