Anzahl alternierender Matrizen < Maple < Mathe-Software < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:58 Di 20.01.2009 | | Autor: | Der_Blubb |
| Aufgabe | Eine Matrix $A = [mm] (a_{ij}) \in \mathbb Z^{n\times n}$ [/mm] heißt 1 alternierende Vorzeichen-Matrix - wir schreiben $A [mm] \in \mathcal A_n [/mm] $, wenn gilt:
1. $ [mm] a_{ij} \in$ \{1, 0, --1\}
[/mm]
2. Alle Einträge [mm] $\neq$ [/mm] 0 alternieren in jeder Reihe und Spalte.
3. Alle Einträge [mm] $\neq$ [/mm] 0 in jeder Reihe und Spalte beginnen mit 1 und enden mit 1.
4. In jeder Zeile und Spalte steht mindestens ein Eintrag [mm] $\neq$ [/mm] 0.
Hier ist ein Beispiel für $n = 4:$
5. Jede Zeilen- und Spaltensumme ergibt 1 (folgt aus 1. bis 4.)
[mm] \pmat{0&1&0&0 \\1&-1&1&0 \\0&0&0&1\\0&1&0&0}
[/mm]
Aufgabe: Finde die Anzahl der Matrizen in [mm] $\mathcal A_4$ [/mm] unter Zuhilfenahme von Maple. (Es sind nicht mehr als 50.)
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo an alle,
Ich muss diese Aufgabe für eine Hausarbeit lösen, komme jedoch einfach nicht alleine weiter. Ich dachte erst ich müsste irgendwie alle möglichen 4x4-Matrizen mit den Einträgen 0,1 und -1 in Maple erzeugen und dann die rauspicken, die die Bedingungen 1. bis 5. erfüllen. Das sind aber natürlich viel zu viele....Ich dachte ich könnte etwa so anfangen:
with(linalg):
A:= array(1..4,1..4):
for i from 1 to 4 do
for j from 1 to 4 do
A[i,j]:=?
...
Ich weiß jedoch nicht wie ich es hinbekomme alle Möglichkeiten mitzuzählen bzw. in die Matrix eintragen zu lassen. In der ersten und letzten Zeile und Spalte können z.B auch nur 0en und 1en stehen. Ich hoffe irgendjemand kann mir helfen.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:42 Sa 31.01.2009 | | Autor: | Peter_Pein |
Vieleicht hilft ![[]](/images/popup.gif) dieser Link weiter?
Leider bin ich in Maple nicht so geübt ![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]") .
Falls Du Mathematica kennst, kannst Du vieleicht
| 1: | In[1]:=
| | 2: | checkLine[{0 ..}]:=False;
| | 3: | checkLine[li_]:=Plus@@li===1&& !MatchQ[DeleteCases[li,0],{___,x_,x_,___}];
| | 4: | goodLines=Select[Tuples[{0,-1,1},4],checkLine]
| | 5: | Length[mats=
| | 6: | Select[Tuples[goodLines,4],Complement[Transpose[#],goodLines]==={}&]] |
nach Maple-Sprech übersetzen.
Viel Erfolg,
Peter
|
|
|
| |
|
Hallo Der_Blubb,
es gibt doch nur acht Möglichkeiten für das Aussehen einer Zeile:
[mm] \pmat{ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & -1 & 1 \\ 1 & 0 & -1 & 1 \\ 1 & -1 & 0 & 1 \\ 1 & -1 & 1 & 0}
[/mm]
Entsprechendes gilt für die Spalten...
Aus diesen beiden Arrays könntest Du sehr schnell die möglichen Lösungen konstruieren.
Hier ein anderer Weg:
Dein Programm geht m.E. am besten wie folgt vor:
1. Zeile füllen (4 Pos.)
1. Spalte füllen (3 Pos.)
2. Zeile füllen (3 Pos.)
2. Spalte füllen (2 Pos.)
3. Zeile füllen (2 Pos.)
3. Spalte füllen (1 Pos.)
4. Zeile füllen (1 Pos.)
Zähler um 1 erhöhen.
Wenn füllen nicht mehr möglich ist, eine Ebene zurück, ebenso nach Zählererhöhung. Ende, wenn aus der ersten Ebene (1. Zeile füllen) Rücksprung erforderlich wird.
Nach Maple kann ich es Dir nicht übersetzen, davon habe ich nicht die leiseste Ahnung. Aber als Programmskizze bzw. Hinweis zur Logik sollte es hoffentlich reichen.
"füllen" heißt natürlich: regelkonform füllen. Nach der ersten 1 gibt es ja nicht mehr so viele Möglichkeiten: 4, wenn die 1 vorne bzw. oben steht, 2, wenn sie an 2. Stelle steht, 1, wenn sie an 3. oder 4. Stelle steht. Siehe die Liste oben.
Viel Erfolg!
Grüße,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:10 Di 03.02.2009 | | Autor: | Der_Blubb |
Vielen Dank für die Hilfe. Ich habe es jetzt am Wochenende, auch dank der guten Tipps hinbekommen.
|
|
|
|
