www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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.vorhilfe.de