Lineares Gleichungssystem - Zahlpartitionen?

29/08/2010 - 19:24 von Jürgen Will | Report spam
Hallo,

kann mir jemand bei meinem nichttrivialen Problem helfen? Bin kein
Mathematiker.

Ich habe folgendes Lineares Gleichungssystem, das ein Vertreter der
Gleichungssysteme meines übergeordneten mathematischen Problems ist.
Alle Zahlen sollen nichtnegative Ganze Zahlen sein, alle f[i] und alle g[i]
seien gegeben.
Teil A:
Gl. 1.0: t[1,0]+t[2,0]+t[3,0]=f[0]
Gl. 1.1: t[1,1]+t[2,1]+t[3,1]=f[1]
Gl. 1.2: t[2,2]+t[3,2]=f[2]
Gl. 1.3: t[3,3]=f[3]
Teil B:
Gl. 2.0: t[1,1]+t[2,2]+t[3,3]=g[0]
Gl. 2.1: t[1,0]+t[2,1]+t[3,2]=g[1]
Gl. 2.2: t[2,0]+t[3,1]=g[2]
Gl. 2.3: t[3,0]=g[3]
Gesucht sind alle t[i,j], also t[1,0], t[1,1], t[2,0], t[2,1], t[2,2],
t[3,0], t[3,1], t[3,2], t[3,3].
Bei den gegebenen f[i] und g[i] ist das Gleichungssystem in nichtnegativen
Ganzen Zahlen eindeutig lösbar, es hat mindestens eine Lösung.
Ich suche einfache Ausdrücke für die einzelnen t[i,j], z. B. Terme von
Kombinatorischen Ausdrücken oder nicht allzu komplizierte
Rekursionsgleichungen.

Es geht darum, aus den f[i] und g[i] die t[i,j], aus denen sie berechnet
wurden, wieder zu rekonstruieren. Es handelt sich um das Problem, die f[i]
bzw. g[i] in die durch die zugehörige Gleichung angegebene Struktur
aufzuspalten.
In Teil B sind die Zahlen anders zusammenaddiert als in Teil A.

Man könnte z. B. alle Zahlpartitionen eines f[i] bzw. g[i] erzeugen und dann
jede dieser Partitionen einzeln hernehmen und ihre Elemente auf n Stellen
permutieren, wobei n die Anzahl der Summanden auf der linken Seite der
zugehörigen Gleichung ist. Durch Teil B wird eine Umordnung der durch Teil A
erzeugten Partitionen/Permutationen-Struktur erzeugt. Lösung sind diejenigen
Permutationen, die sowohl Teil A als auch Teil B erfüllen.

Hat jemand eine Idee?

Danke!
 

Lesen sie die antworten

#1 Josef Chmel
30/08/2010 - 22:42 | Warnen spam
On 29 Aug., 19:24, Jürgen Will wrote:
Hallo,

kann mir jemand bei meinem nichttrivialen Problem helfen? Bin kein
Mathematiker.

Ich habe folgendes Lineares Gleichungssystem, das ein Vertreter der
Gleichungssysteme meines übergeordneten mathematischen Problems ist.
Alle Zahlen sollen nichtnegative Ganze Zahlen sein, alle f[i] und alle g[i]
seien gegeben.
Teil A:
Gl. 1.0: t[1,0]+t[2,0]+t[3,0]=f[0]
Gl. 1.1: t[1,1]+t[2,1]+t[3,1]=f[1]
Gl. 1.2: t[2,2]+t[3,2]=f[2]
Gl. 1.3: t[3,3]=f[3]
Teil B:
Gl. 2.0: t[1,1]+t[2,2]+t[3,3]=g[0]
Gl. 2.1: t[1,0]+t[2,1]+t[3,2]=g[1]
Gl. 2.2: t[2,0]+t[3,1]=g[2]
Gl. 2.3: t[3,0]=g[3]
Gesucht sind alle t[i,j], also t[1,0], t[1,1], t[2,0], t[2,1], t[2,2],
t[3,0], t[3,1], t[3,2], t[3,3].
Bei den gegebenen f[i] und g[i] ist das Gleichungssystem in nichtnegativen
Ganzen Zahlen eindeutig lösbar, es hat mindestens eine Lösung.
Ich suche einfache Ausdrücke für die einzelnen t[i,j], z. B. Terme von
Kombinatorischen Ausdrücken oder nicht allzu komplizierte
Rekursionsgleichungen.

Es geht darum, aus den f[i] und g[i] die t[i,j], aus denen sie berechnet
wurden, wieder zu rekonstruieren. Es handelt sich um das Problem, die f[i]
bzw. g[i] in die durch die zugehörige Gleichung angegebene Struktur
aufzuspalten.
In Teil B sind die Zahlen anders zusammenaddiert als in Teil A.

Man könnte z. B. alle Zahlpartitionen eines f[i] bzw. g[i] erzeugen und dann
jede dieser Partitionen einzeln hernehmen und ihre Elemente auf n Stellen
permutieren, wobei n die Anzahl der Summanden auf der linken Seite der
zugehörigen Gleichung ist. Durch Teil B wird eine Umordnung der durch Teil A
erzeugten Partitionen/Permutationen-Struktur erzeugt. Lösung sind diejenigen
Permutationen, die sowohl Teil A als auch Teil B erfüllen.

Hat jemand eine Idee?

Danke!



Hallo,
wenn ich die Gleichungen in Maxima eintippe, beschwert es sich dass
die Gleichungen
inkonsistent sind. Wenn man die letzte Gleichung weglaesst kommt raus:

(%i2) e1: t10+t20+t30ð;
(%i3) e2: t11+t21+t31ñ;
(%i4) e3: t22+t32ò;
(%i5) e4: t33ó;
(%i6) e5: t11+t22+t33=g0;
(%i7) e6: t10+t21+t32=g1;
(%i8) e7: t20+t31=g2;
(%i9) e8: t30=g3;

(%i12) solve([e1,e2,e3,e4,e5,e6,e7],
[t10,t11,t20,t21,t22,t30,t31,t32,t33]);
(%o12) [
[
t10 = %r1,
t11 = g0 - f3 - f2 + %r2,
t20 = g2 + g1 + g0 - f3 - f2 - f1 - %r1,
t21 = g1 - %r2 - %r1,
t22 = f2 - %r2,
t30 = - g2 - g1 - g0 + f3 + f2 + f1 + f0,
t31 = - g1 - g0 + f3 + f2 + f1 + %r1,
t32 = %r2,
t33 = f3
]]

Wenn eine Gleichung abhaengig ist, hat man 7 Gleichungen bei 9
Unbekannten.
Dann kann man 2 Unbekannte frei waehlen. Koennte also hinhauen.

Gruss
Josef

Ähnliche fragen