Einmalige Muster

02.10.2020, 13:55

Ailyniae

Einmalige Muster

Meine Frage:
Es geht darum, dass wir ein X mal Y großes Feld haben, in dem Zahlen bis n vorkommen.
Nun besteht die Aufgabe darin herauszufinden, wie viele unterschiedliche Kombinationen es gibt, wenn die Kombinationen sowohl die Reihen als auch die Spalten berücksichtigen, nicht jedoch den genauen Ort.

Um es vielleicht verständlicher zu machen ein Beispiel:
Feld 2x2 mit bis zu 2 unterschiedlichen Zahlen ergibt insgesamt 7 unterschiedliche Kombinationen:

1.
0 0
0 0

2.
1 1
1 1

3.
0 0 | 0 1 | 1 0 | 0 0
0 1 | 0 0 | 0 0 | 1 0

4.
0 0 | 1 1
1 1 | 0 0

5.
0 1 | 1 0
0 1 | 1 0

6.
1 0 | 0 1
0 1 | 1 0

7.
1 1 | 1 0 | 0 1 | 1 1
1 0 | 1 1 | 1 1 | 0 1

Nun weiß ich jedoch nicht, wie ich das Problem in einer Formel ausgedrückt bekomme.
(a = 5, die Anzahl an verschiedenen Variationen mit 2 Zahlen, Nr. 3-7 aus dem Beispiel)

(ich hoffe es ist einigermaßen verständlich)

Meine Ideen:
Ich hatte bisher die Idee die Aufgabe in mehrere Schritte zu unterteilen.
Dazu wollte ich gucken, wieviele unterschiedlicher Möglichkeiten es er für 1 Zahl, dann für 2 Zahlen usw auf die Größe des Feldes gibt.
Nehmen wir z.B. wieder ein Feld 2x2 mit 7 Zahlen.
Mit nur einer Zahl, gibt es 7 Möglichkeiten, da es 7 Zahlen sind. $\begin{eqnarray*} \begin{pmatrix} 7 \\ 1 \end{pmatrix} \end{eqnarray*}$
Mit 2 Zahlen, gibt es 21 Möglichkeiten $\begin{eqnarray*} \begin{pmatrix} 7 \\ 2 \end{pmatrix} \end{eqnarray*}$
usw.
(v = 21, für die 21 Möglichkeiten, die wir gerade berechnet haben)

Das jeweilige Ergebnis muss ich dann noch mit der Anzahl an unterschiedlichen Kombinationen für die entsprechende Anzahl verschiedener Zahlen multiplizieren, also für z.B. 2 Zahlen wäre es 5*21 = 105 (a = siehe Fragestellung, v = siehe Berechnung mit Matrix).
Wenn man das nun für alle Zahlen macht, die in das 2x2 Feld passen und die Ergebnisse addiert, kommt man auf das richtige Ergebnis:
1* $\begin{eqnarray*} \begin{pmatrix} 7 \\ 1 \end{pmatrix} \end{eqnarray*}$
+ 5* $\begin{eqnarray*} \begin{pmatrix} 7 \\ 2 \end{pmatrix} \end{eqnarray*}$
+ 9* $\begin{eqnarray*} \begin{pmatrix} 7 \\ 3 \end{pmatrix} \end{eqnarray*}$
+ 6* $\begin{eqnarray*} \begin{pmatrix} 7 \\ 4 \end{pmatrix} \end{eqnarray*}$
= 637

Aber ich verstehe einfach nicht, wie man auf das 'a' (also die 1, 5, 9, 6 aus dem Beispiel) kommt.

02.10.2020, 18:22

Dopap

Auf diesen Beitrag antworten »

Ich werde nicht so richtig schlau bei der Frage.

meinst du Folgendes: ein Rechteck mit Koordinaten wird von N unterscheidbare Elementen belegt.
Beispiel: ein Schachbrett mit 64 Feldern wird von König, Dame, Turm, Läufer und Springer belegt. N=5
Wieviele Stellungen gibt es?

Antwort: $\begin{eqnarray*} 64\cdot 63\cdot 62\cdot 61\cdot 60 = \frac{64!}{59!\cdot 5!} = \binom {64}{5}\cdot 5! = 914\,941\,440 \end{eqnarray*}$

Man spricht von Variationen ohne Wiederholung bzw. von Variationen ohne Zurücklegen im Urnenmodell.

Man könnte nun fragen: Wieviele Stellungen gibt es mit König und maximal 4 weiteren Schwerfiguren?
Aber dazu evtl. später mehr...

03.10.2020, 09:42

Ailyniae

Auf diesen Beitrag antworten »

Danke für die schnelle Antwort, leider geht sie glaube ich ziemlich an meiner Frage vorbei.
Denn wenn es so einfach wäre, würde ich nicht seit ca 3 Wochen dran sitzen und nicht weiter kommen Augenzwinkern

Jedes Feld des Schachbretts wäre durch eine Figur belegt. Und ich will herausfinden, wieviele unterschiedliche Varianten es gibt, wenn z.B. erst alle Reihen und dann alle Spalten betrachtet und die Reihenfolge keine wirkliche Rolle spielt. (So wie in dem Beispiel von mir ganz oben, es gibt bei 2x2 mit 2 Variablen 7 Gruppierungen, wenn man die Zeilen und Spalten betrachtet, die anderen sind jeweils nur Varianten von den Gruppierungen)

Wird es dadurch vielleicht etwas klarer, was ich meine?

03.10.2020, 11:57

URL

Auf diesen Beitrag antworten »

Wenn ich es recht verstehe, wendest du auf eine Belegungsmatrix, z.B. $\begin{eqnarray*} A=\begin{pmatrix}0&0\\1&1 \end{pmatrix} \end{eqnarray*}$ alle möglichen Zeilen- oder Spaltenvertauschungen an und willst wissen, wie viele unterschiedliche Ergebnisse du bekommst. Korrekt?
Darf man dabei entweder Zeilen oder Spalten vertauschen oder ist beides gleichzeitig erlaubt?

Idee: Zeilen- und Spaltenvertauschungen lassen sich als Elementarmatrizen schreiben. Beschränkt man sich nur auf Zeilenvertauschunge, dann geht es nach meinem Verständnis darum, die Gruppe $\begin{eqnarray*} G \end{eqnarray*}$ der Zeilenvertauschungen auf der Menge der Belegungsmatrizen operieren zu lassen. Die Mächtigkeit der Bahn $\begin{eqnarray*} G\cdot A \end{eqnarray*}$ ist dann deine gesuchte Zahl.
Edit: G muss, wenn überhaupt die von den genannten Elemantarmatrizen erzeugete Untergruppe der Gruppe der Elementarmatrizen sein.

03.10.2020, 19:09

Ailyniae

Auf diesen Beitrag antworten »

Es dürfen sowohl Spalten als auch Zeilen beliebig oft getauscht werden.

Zitat:

[...] willst wissen, wie viele unterschiedliche Ergebnisse du bekommst

Ich glaube das trifft es noch nicht ganz.

Im Grunde such ich als Endergebnis wieviele verschiedene Gruppierungen es für ein Feld (X, Y) mit N möglichen Werten für jede Position gibt. Eine Gruppierung definiert sich darüber, dass die Reihenfolgen der Zeilen und Spalten irrelevant sind, das "sortierte" Muster aber gleich bleibt.
Zur Veranschaulichung habe ich mir damit beholfen, die Werte pro Zeile sowie pro Spalte nach Größe zu sortieren, die daraus resultierenden Zeilen und Spalten ebenfalls wieder zu sortieren und diese dann aneinandergereit darzustellen.

Erläuterung auf Basis meines initialen Beispiels mit 2x2 mit 2 unterschiedlichen Werten und der 3. Gruppierung:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:

3.
0 0 | 0 1 | 1 0 | 0 0
0 1 | 0 0 | 0 0 | 1 0

Beispiel auf Basis des dritten Blocks:
10
00

Zeilen:
10
00

Spalten:
10
00

Jede Zeile und Spalte in sich lexikalisch sortiert:

Zeilen:
01
00

Spalten:
01
00

Zeilen und Spalten lexikalisch sortiert:

Zeilen:
00
01

Spalten:
00
01

Aneinanderreihung:

Zeilen:
00|01

Spalten:
00|01

Finale Darstellung:
> 00|01|00|01

Daraus ergeben sich dann aus dem initialen Beispiel (2x2 mit 2 Werten) folgende Gruppen:

1.
0 0
0 0

> 00|00|00|00

2.
1 1
1 1

> 11|11|11|11

3.
0 0 | 0 1 | 1 0 | 0 0
0 1 | 0 0 | 0 0 | 1 0

> 00|01|00|01

4.
0 0 | 1 1
1 1 | 0 0

> 00|11|01|01

5.
0 1 | 1 0
0 1 | 1 0

> 01|01|00|11

6.
1 0 | 0 1
0 1 | 1 0

> 01|01|01|01

7.
1 1 | 1 0 | 0 1 | 1 1
1 0 | 1 1 | 1 1 | 0 1

> 01|11|01|11

Bei der Suche nach einer Lösung bin ich dann bei folgender Formel angekommen:

$\begin{eqnarray*} <br /> \sum\limits_{k=1}^{n} \! f(k) \begin{pmatrix} n \\ k\end{pmatrix} <br /> \end{eqnarray*}$

Weiß jedoch nicht, wie die Formel hinter $\begin{eqnarray*} \! f(k) \end{eqnarray*}$ lauten könnte. Durch probieren / abzählen weiß ich nur, dass für das Beispiel 2x2 mit n=7 unterschiedlichen Werten folgende Werte für $\begin{eqnarray*} \! f(k) \end{eqnarray*}$ "korrekt" wären:

k = 1 => 1
k = 2 => 5
k = 3 => 9
k = 4 => 6
k > 4 => 0 oder n = 2x2 statt 7

Es kann natürlich sein, dass ich hier nur in eine Sackgasse gelaufen bin und die Lösung für das Gesamtergebnis garnicht über diese Summenformel zu ermitteln ist.

PS: Die Beispiele sind immer quadratisch, es sollte aber auch mit nicht quadratischen Feldern zu lösen sein.

03.10.2020, 21:52

Dopap

Auf diesen Beitrag antworten »

RE: Einmalige Muster

Zitat:

Original von Ailyniae
Meine Frage:
Es geht darum, dass wir ein X mal Y großes Feld haben, in dem Zahlen bis n vorkommen.
Nun besteht die Aufgabe darin herauszufinden, wie viele unterschiedliche Kombinationen es gibt, wenn die Kombinationen sowohl die Reihen als auch die Spalten berücksichtigen, nicht jedoch den genauen Ort.[...]

Die Frage präzise zu stellen ist der erste Weg zu einer möglichen Lösung.

1.) es kommen alle Zahlen $\begin{eqnarray*} 1,2,3,\cdots,n \end{eqnarray*}$ vor?
1.a) wenn ja dann $\begin{eqnarray*} X\cdot Y > n \quad \text{oder}\quad X\cdot Y = n \end{eqnarray*}$ ?
2.) wenn nein, eine echte Teilmenge aus $\begin{eqnarray*} 1,2,3,\cdots,n \end{eqnarray*}$
2.a) ...?
2.b) ... ?

Wenn schon Beispiele, dann wenigstens von ausreichender Größe.
Warum kannst du das am Schachbrett oder Sudoku nicht demonstrieren?

$\begin{eqnarray*} \begin{array}{|c|c|c|c|c|c|c|}\hline 11&12&13&14&15&16&&18&19\\ \hline 20&22&23&24&25&26&27&28&29 \\ \hline 30&32&33&34&35&&37&38&39 \\ \hline 40&42&43&44&45&46&47&48&49 \\ \hline 52&62&53&54&55&56&57&58&59 \\ \hline 1&2&3&4&5&66&67&68&69 \\ \hline 71&72&73&74&75&76&77&78&79 \\ \hline &&&&&86&87&88&89 \\ \hline &92&&94&&&97&98&99 \\\hline\end{array} \end{eqnarray*}$

hier eine Belegung eines arrays mit X=9,Y=9 und Zahlen ohne Wiederholung aus $\begin{eqnarray*} 1,2,3, \cdots,99 \end{eqnarray*}$
--------------------------------------
edit: mit ZITAT kannst du das array editieren und/oder verkleinern

04.10.2020, 11:02

Ailyniae

Auf diesen Beitrag antworten »

Ich glaube der Ansatz von URL geht schon eher in die richtige Richtung. Ich weiß nur noch nicht, wie ich damit auf die gesuchten Zahlen komme. Also, wie käme ich denn auf das A und das G?

Ich würde gerne größere Beispiele anbringen, aber um sie vollständig darzustellen, bräuchte es zu viel Platz.
Für ein Feld von 2x2 mit 3 Zahlen (0,1,2) gibt es zB schon 81 Permutationen, von denen 27 einmalig (und damit gesucht) sind. Ich wüsste nicht, wie ich die alle hier reinschreiben sollte und auch nicht, wie es zum besseren Verständnis beitragen sollte.
Und ich würde die Frage gerne präziser stellen, ich weiß aber wirklich nicht, wie ich das Problem deutlicher erklären kann.

04.10.2020, 12:29

URL

Auf diesen Beitrag antworten »

Ich dachte an die Bahnformel.
Dazu müsste man den Stabilisator einer Matrix A kennen, d.h. alle Zeilenvertauschungen Z und alle Spaltenvertauschungen S, für die ZAS=A gilt.
Momentan sehe ich nicht, wie man den in diesem allgemeinen Fall bekommen soll. Beschränkt man sich auf die Fälle mit ZA=A und AS=A sehe ich Chancen.
Aber im allgemeinen Fall betrachte etwa $\begin{eqnarray*} A=\begin{pmatrix} 1&0\\0&1\end{pmatrix} \end{eqnarray*}$ . Vertauscht man die Zeilen, bekommt man eine andere Matrix, vertauscht man dann aber noch die Spalten, landet man wieder bei A.

Evtl. hilft dieses geheimnisvolle "sortierte" Muster, dessen Bildungsgesetz du bisher verschwiegen hast.

04.10.2020, 13:36

Ailyniae

Auf diesen Beitrag antworten »

Ich glaube ich habe versucht das sortierte Muster die ganze Zeit zu beschreiben (unter anderem in dem Code weiter oben) und nicht 'verschwiegen', aber irgendwie schaffe ich es scheinbar nicht, es für andere verständlich darzustellen.
Aber die Bahnformel kenne ich noch nicht, ich schaue sie mir mal an und hoffe, dass es hilft.
Ist denn die Grundidee dahinter ein bisschen deutlich geworden, oder kann man gar nicht verstehen, was ich letztlich herausfinden möchte?

04.10.2020, 14:07

URL

Auf diesen Beitrag antworten »

Aufgrund deiner Formulierung "Zur Veranschaulichung habe ich mir damit beholfen" ging ich davon aus, das wäre nicht das eigentliche Muster.

05.10.2020, 08:28

Ailyniae

Auf diesen Beitrag antworten »

Es ist das Muster für den ganz einfachen Fall 2x2 mit 2 Zahlen. Mit 3 Zahlen sieht es schon wieder ganz anders aus.
Deswegen meinte ich, dass es ein Beispiel ist. Es gibt ja aber viele verschiedene Varianten, je nach dem welche der der Variablen wie verändert.

Ich hab mir die Bahnformel mal angeschaut, muss aber gestehen, dass ich sie nicht verstehe oder nicht verstehe, wie ich sie hier anwenden kann. (Ich sollte vielleicht dazu schreiben, dass ich kein Mathematiker bin und mich deswegen nicht immer richtig ausdrücken kann und vielleicht nicht alles gleich verstehe...)

08.10.2020, 11:47

Ailyniae

Auf diesen Beitrag antworten »

Ich habe noch immer keine Lösung gefunden, also falls es jemand versteht und einen weiteren Ansatz (oder eine Lösung) hat, wäre ich sehr dankbar.

08.10.2020, 21:13

URL

Auf diesen Beitrag antworten »

Zitat:

Original von Ailyniae
Es ist das Muster für den ganz einfachen Fall 2x2 mit 2 Zahlen. Mit 3 Zahlen sieht es schon wieder ganz anders aus.
Deswegen meinte ich, dass es ein Beispiel ist. Es gibt ja aber viele verschiedene Varianten, je nach dem welche der der Variablen wie verändert.

Schon wieder diese Herumgeier um das Muster. Aber bitte, es bleibt dir überlassen, welche Informationen du preisgeben willst.
Vertauschungen innerhalb einer Zeile und anschließende Vertauschung von Zeilen kann man wohl noch als Gruppenoperation beschreiben, die lexikographische Anordnung aber nicht. Von daher würde die die Bahnformel auch nichts nützen.

Neue Frage »

Antworten »

Einmalige Muster

Verwandte Themen