matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete MathematikAnzahl Möglichkeiten -Rotation
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Diskrete Mathematik" - Anzahl Möglichkeiten -Rotation
Anzahl Möglichkeiten -Rotation < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Anzahl Möglichkeiten -Rotation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 02:14 Mo 15.02.2016
Autor: mmfbn

Hi,
man hat ein Quadrat mit je einer bestimmten Anzahl von Feldern auf jeder Seite. Zum Beispiel mit drei:
[mm] \vmat{\bigcirc & \bigcirc & \bigcirc \\\bigcirc & & \bigcirc \\\bigcirc & \bigcirc & \bigcirc} [/mm]
Nun will man eine bestimmte Anzahl dieser Felder ankreuzen. Zum Beispiel zwei:
[mm] \vmat{\bigcirc & \otimes& \otimes \\\bigcirc & & \bigcirc \\\bigcirc & \bigcirc & \bigcirc} [/mm]
Gesucht ist nun die Anzahl der möglichen "Ankreuzmuster", die sich gegenseitig nicht durch Rotationen (90°,180°,270°(, 360°)) und/oder Spiegelungen (Horizontal, Vertikal, Diagonal) aufeinander abbilden lassen.
zum Beispiel geht nun nicht mehr:
[mm] \vmat{\bigcirc & \bigcirc & \otimes \\\bigcirc & & \otimes \\\bigcirc & \bigcirc & \bigcirc} [/mm]
Da man dieses erhält wenn man das obere an der Diagonale spiegelt.

Mit 2 Kreuzen gibt es bei einem Quadrat mit 3 Feldern an jeder Seite insgesammt 6 "Ankreuzmuster":
[mm] \vmat{\otimes & \otimes & \bigcirc \\\bigcirc & & \bigcirc \\\bigcirc & \bigcirc & \bigcirc}\vmat{\otimes & \bigcirc & \otimes \\\bigcirc & & \bigcirc \\\bigcirc & \bigcirc & \bigcirc}\vmat{\otimes & \bigcirc & \bigcirc \\\bigcirc & & \otimes \\\bigcirc & \bigcirc & \bigcirc}\vmat{\otimes & \bigcirc & \bigcirc \\\bigcirc & & \bigcirc \\\bigcirc & \bigcirc & \otimes }\vmat{\bigcirc & \otimes & \bigcirc \\\bigcirc & & \otimes \\\bigcirc & \bigcirc & \bigcirc }\vmat{\bigcirc & \otimes & \bigcirc \\\bigcirc & & \bigcirc \\\bigcirc & \otimes & \bigcirc } [/mm]

Bei einem Kreuz sind es 2 und bei 3 Kreuzen glaube ich 10. Bei 0 und 8 gibts nur eine Möglichkeit und bei 7,6,5 ist es wie bei 1,2,3.

Speziell gesucht ist nun die Anzahl bei 4 Kreuzen. Schön zu wissen wäre auch noch wieviel es sind, wenn das Quadrat mehr als 3 Felder pro Seite hat. Die Ergebnisse oben waren mehr oder weniger ausgezählt. Das kann man bei mehr Feldern nur noch schlecht machen.
Gesucht ist eine möglichst allgemeine Lösung.

Bin nicht sicher, in welches Fachgebiet der Mathematik es genau fällt. Hoffe es passt in etwa hier rein.

-----------
Unter anderem bisher dazu überlegt:
Man kann es immer so rotieren/spieglen, dass ein Kreuz auf dem ersten Feld und/oder dem zweite liegt (außer bei 0 Kreuzen). Dann muss man nur noch die Kombinationen von einem Kreuz weniger durchprobieren.
Man könnte jedem "Ankreuzmuster" eine Zahl zuordnen (binär zu decimal), die kleinst mögliche, die durch rotation/spiegeln möglich ist. Dann zählt man die unterschiedlichen Zahlen.
Beides ist aber eher fürs auszählen gedacht, rechnen wäre gut.



        
Bezug
Anzahl Möglichkeiten -Rotation: Antwort
Status: (Antwort) fertig Status 
Datum: 11:16 Mo 15.02.2016
Autor: Teufel

Hi!

Das Thema passt hier gut hin. :)

Kennst du das []Lemma von Burnside (bzw Cauchy)? Damit kann man Sachen zählen, die invariant unter Gruppenoperationen bleiben (z.B. Rotationen und Spiegelungen in deine Fall).

Für $n=3$ und 2 Kreuze in deinem Fall:
$G$ = Gruppe der Drehungen und Spiegelungen (Anmerkung: du brauchst nur eine Spiegelung, z.B. horizontal, weil man die vertikale auch durch die horizontale + Rotation simulieren kann)
$X$ = Menge der verschiedenen Ankreuzmuster ohne die Drehungen/Spiegelungen zu beachten [mm] ($\left|X\right|=\vektor{8 \\ 2}$) [/mm]
$|X/G|$ = Anzahl der verschiedenen Orbits von $X$ unter $G$ = Zahl, die du suchst
[mm] $X^g$ [/mm] = Anzahl der verschiedenen Ankreuzmuster, die unter der Gruppenoperation $g$ gleich bleiben, z.B. alle Ankreuzmuster, die unter einer 90°-Rotation in sich selbst übergehen.

Eingesetzt:
$|G|=8$ (4 Rotationen + 4 Rotationen mit Spiegelung)

Jetzt muss man noch [mm] $|X^g|$ [/mm] für alle [mm] $g\in [/mm] G$ bestimmen. Nehmen wir mal $g=0°=360°$, also wenn man nichts dreht oder spiegelt. Da bleibt natürlich jedes Ankreuzmuster so, wie es ist, jedes der $|X|$ geht in sich selbst über.

90°: Nichts bleibt, wie es ist.
180°: 4 Muster bleiben gleich (welche?)
270°: Nichts.
Spiegelung + 0°: 4
Spiegelung + 90°: 4
Spiegelung + 180°: 4
Spiegelung + 270°: 4

Nach Formel gilt [mm] $|X/G|=\frac{1}{|G|}\sum\limits_{g\in G}|X^g|=\frac{1}{8}(\vektor{8 \\ 2}+0+4+0+4+4+4+4)=\frac{48}{8}=6. [/mm]

Das kannst du auch verallgemeinern, aber du kannst es ja erstmal für n=2 und 1 oder 2 Kreuze üben. Dann kannst du dich mal an 4 wagen. Es ist natürlich trotzdem anstrengend zu schauen, dass man wirklich alle Muster findet, die unter irgendwelchen Operationen gleich bleiben, aber besser als alles durchzuprobieren ist es allemal, besonders wenn $n$ wächst.

Bezug
                
Bezug
Anzahl Möglichkeiten -Rotation: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:08 Mo 15.02.2016
Autor: mmfbn

Hallo Teufel,
danke für die Antwort. Von dem Lemma habe ich noch nichts gehört (leider viel zu wenig Mathe gehabt) aber das passt ja perfekt. Hätte nicht gedacht, dass es für genau dieses Problem einen Lösungweg gibt.

Ich habe mal mit 4 Kreuzen durchprobiert. (mit horizontaler Spiegelung)
bei 0° bilden [mm] \vektor{8 \\ 4} [/mm] Möglichkeiten auf sich ab
bei 90°: 2
bei 180°: 6
bei 270°: 2
Spiegelung + 0°: 6
Spiegelung + 90°: 6
Spiegelung + 180°: 6
Spiegelung + 270°: 6

[mm] $|X/G|=\frac{1}{|G|}\sum\limits_{g\in G}|X^g|=\frac{70+34}{8}=13 [/mm]

Ich habe auch mal ein Programm geschrieben, welches jeder Konfiguration die kleinst mögliche Zahl zuordnet, die es durch Drehungen und/oder Spiegelungen erreichen kann. Da kommt auch 13 raus.

Der Lösungsweg mit dem Lemma ist aber mathematisch schöner :), jedoch kommt man bei beiden Lösungswegen nicht so einfach um auszählen drum rum.


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]