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
StartseiteMatheForenKombinatorikErweiterte Permutation?
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Kombinatorik" - Erweiterte Permutation?
Erweiterte Permutation? < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Erweiterte Permutation?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:36 Di 30.08.2016
Autor: zarkus

Aufgabe
Es gibt 100 Stühle (die im Kreis aufgebaut sind) für 100 Personen. Wieviele Möglichkeiten gibt es, wenn jede Person jedesmal auf einem anderen Stuhl sitzt und jedes mal einen anderen Nachbarn hat. (jede Person darf nie den gleichen Nachbarn haben)

Mir ist gar nicht klar wie ich die Nachbarn mit einbeziehen kann.
...jede Person auf anderem Stuhl würde bedeuten 100! aber das kann bedeuten, dass es Wiederholungen in den Nachbarn gibt?

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Erweiterte Permutation?: Antwort
Status: (Antwort) fertig Status 
Datum: 17:01 Di 30.08.2016
Autor: Al-Chwarizmi


> Es gibt 100 Stühle (die im Kreis aufgebaut sind) für 100
> Personen. Wieviele Möglichkeiten gibt es, wenn jede Person
> jedesmal auf einem anderen Stuhl sitzt und jedes mal einen
> anderen Nachbarn hat. (jede Person darf nie den gleichen
> Nachbarn haben)
>  Mir ist gar nicht klar wie ich die Nachbarn mit
> einbeziehen kann.
> ...jede Person auf anderem Stuhl würde bedeuten 100! aber
> das kann bedeuten, dass es Wiederholungen in den Nachbarn
> gibt?



Guten Tag zarkus

          [willkommenmr]

ich denke, dass du mit diesen Angaben keine klar definierte
Aufgabe beschrieben hast. Mindestens bleiben da bei mir gewisse
Zweifel.

Die Sache mit den 100 im Ring aufgestellten Sitzplätzen scheint
zwar klar und ist bei derartigen Kombinatorik-Aufgaben sogar
recht häufig.

Als "Möglichkeiten" sollen wohl Sitzordnungen für die 100
Personen gemeint sein, also bijektive Zuordnungen von der
Menge der 100 Personen zu den 100 verfügbaren Plätzen.
Diese insgesamt 100!  Zuordnungen entsprechen anzahlmäßig
den sämtlichen Permutationen einer Menge von 100 Elementen.

Die Forderung, dass jede Person bei jeder zulässigen Anordnung
auf einem anderen Stuhl sitzen soll, schränkt die gesamte
Anzahl der zulässigen Sitzordnungen sofort auf maximal 100
(hundert, nicht etwa 100!) ein.  

Die Einschränkung, dass jede der 100 Personen bei keiner
neuen Sitzordnung einen Nachbarn von einer anderen Sitzordnung
haben darf, ist dann vielleicht gar nicht mehr so sehr einschränkend,
wie man sich zunächst denken könnte. Beachte dabei aber, dass
jede der Personen in der ringförmigen Anordnung nicht nur einen,
sondern stets zwei Sitznachbarn hat (einen links und einen rechts).

Ich könnte mir vorstellen, dass es möglich sein könnte, eine Menge von
100 Sitzordnungen mit den geforderten Eigenschaften zu finden.
Dabei lasse ich mich aber gern eines besseren belehren. Je kleiner
die mögliche Maximalzahl der Sitzordnungen, umso mehr werde
ich die Aufgab als "interessant" würdigen ....

LG  ,   Al-Chwarizmi  



Bezug
                
Bezug
Erweiterte Permutation?: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 21:00 Di 30.08.2016
Autor: zarkus

Hallo Al-Chwarizmi!

Danke für deine Antwort!

um es noch mal zu erklären: jede Person soll an allen möglichen Plätzen sitzen - Einschränkung ist nur, dass die Nachbarn nie dieselben sind.

Wenn A auf Platz 1 und B auf Platz 2 und C auf Platz 3 sitzt, dann in der nächsten Möglichkeit zB A auf Platz 2 rutscht dürfen B und C nie mehr die Nachbarn sein...

Vllt ist es jetzt etwas "interessanter"? :-) Danke schon mal für eure Hilfe

Bezug
                        
Bezug
Erweiterte Permutation?: Antwort
Status: (Antwort) fertig Status 
Datum: 22:58 Di 30.08.2016
Autor: Al-Chwarizmi


> Hallo Al-Chwarizmi!
>  
> Danke für deine Antwort!
>
> um es noch mal zu erklären: jede Person soll an allen
> möglichen Plätzen sitzen - Einschränkung ist nur, dass
> die Nachbarn nie dieselben sind.
>  
> Wenn A auf Platz 1 und B auf Platz 2 und C auf Platz 3
> sitzt, dann in der nächsten Möglichkeit zB A auf Platz 2
> rutscht dürfen B und C nie mehr die Nachbarn sein...

(Beachte zunächst einmal, dass C gar kein "Nachbar" von A
ist, wenn C auf Platz 3 und A auf Platz 1 ist !  ...... )


Naja, erst mal geht es mir auch nur darum, deine eigentliche
Frage richtig zu verstehen. Zu diesem Zweck möchte ich
einmal vorschlagen, die Anzahl der Sitzplätze auf 26
(anstatt 100) zu setzen. Grund: Unser Alphabet hat 26
Buchstaben.

Es soll also genau 26 Plätze geben. Nummerieren wir sie mit den
Zahlen 1 bis und mit 26. Der Platz 1 hat dann die Nachbarn
2 und 26. Sind in der "Grundanordnung"auf den Plätzen 1, 2
und 3  die Personen A, B und C und auf dem letzten Platz
(Nr. 26) die Person Z, dann hat z.B.  B die Nachbarn A und C.
Die Person A hat aber die Nachbarn Z und B.

Ich habe nun deine Aufgabe folgendermassen verstanden:

Eine Grundmenge G hat 26 (oder allgemeiner: g) Elemente.

Gesucht ist eine (maximale) Menge M von Permutationen der 26
(oder allgemein g) Elemente mit folgenden Eigenschaften:

(1.)  Jedes der g Elemente nimmt jeden der g möglichen
Plätze (die von 1 bis g nummeriert sind) höchstens in
einer einzigen der in der Menge M vorkommenden Permutationen
ein.
(2.)  Zwei der g Elemente der Grundmenge G dürfen in
höchstens einer der in M enthaltenen Permutationen
"benachbart" sein.

Aus der Bedingung (1.) ergibt sich nun, wie ich schon
ausgeführt habe, dass die Menge M auch höchstens g
Elemente (=Permutationen der Menge G) enthalten kann.

Eventuell willst du aber (unter dieser neuen Betrachtungs-
weise) auf die Forderung (1.) verzichten. Du würdest dann
also nur nach der maximalen Anzahl der "zyklischen
Permutationen" einer Menge von g Elementen fragen,
welche untereinander "nachbarfremd" sind.

LG   ,     Al-Chw.

    

Bezug
                                
Bezug
Erweiterte Permutation?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:33 Do 01.09.2016
Autor: zarkus

Ja, soweit richtig Bedingung 1 kann unter Umständen vernachlässigt werden bzw is zweitrangig - mir ist klar das A nicht auf allen Plätzen sitzen kann wenn die Bedingung 2 zutreffen soll - genau so war die Aufgabe gemeint... sorry wg meiner schlechten Aufgabenstellung...

Bezug
                                        
Bezug
Erweiterte Permutation?: Neuformulierung, Obergrenze
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:56 Do 01.09.2016
Autor: Al-Chwarizmi


> Ja, soweit richtig Bedingung 1 kann unter Umständen
> vernachlässigt werden bzw is zweitrangig - mir ist klar
> das A nicht auf allen Plätzen sitzen kann wenn die
> Bedingung 2 zutreffen soll - genau so war die Aufgabe
> gemeint... sorry wg meiner schlechten Aufgabenstellung...


Guten Abend !

So können wir also die Aufgabe neu so formulieren:

Wir betrachten eine (endliche) Grundmenge G von 100
(oder allgemein g) Elementen.
P sei die Menge aller  g!  Permutationen von G.

Gesucht ist eine Teilmenge M von P mit möglichst vielen
Elementen, welche jedoch folgende Eigenschaft besitzen
soll:  

   (E)  je zwei Elemente x,y von G  (mit x≠y) dürfen in
        höchstens einer der in M enthaltenen Permutationen
        "zyklisch benachbart" (modulo g) sein.


Für die weitere Bearbeitung der Frage ist es sinnvoll, einem
bestimmten ausgewählten Element von G jeweils einen
bestimmten Platz in der zyklischen Anordnung zuzuordnen,
also etwa Person A stets auf Platz 1.

Leicht kann man nun eine Obergrenze für die maximale
Anzahl der "zyklisch nachbarfremden" Permutationen
anzugeben. Im Fall g=100 hat z.B. die Person A jedesmal
genau 2 Nachbarn. Da insgesamt nur 99 Personen als
mögliche Sitznachbarn zur Verfügung stehen, kann es
höchstens  [mm] $\lfloor 99/2\rfloor\ [/mm] =\ 49$  Permutationen geben,
die "zyklisch nachbarfremd" sind.


LG  ,    Al-Chwarizmi  

Bezug
                                                
Bezug
Erweiterte Permutation?: Vermutung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:07 Fr 02.09.2016
Autor: Al-Chwarizmi


> Leicht kann man nun eine Obergrenze für die maximale
>  Anzahl der "zyklisch nachbarfremden" Permutationen
>  anzugeben. Im Fall g=100 hat z.B. die Person A jedesmal
>  genau 2 Nachbarn. Da insgesamt nur 99 Personen als
> mögliche Sitznachbarn zur Verfügung stehen, kann es
>  höchstens  [mm]\lfloor 99/2\rfloor\ =\ 49[/mm]  Permutationen
> geben,
>  die "zyklisch nachbarfremd" sind.



Nach etwas Ausprobieren bin ich zur Vermutung gekommen,
dass die angegebene Obergrenze wohl auch wirklich erreichbar
ist. Jedenfalls trifft dies für kleine Werte von g offenbar zu.
Für die Werte g = 1, 2 ist nicht einmal eine einzige Permutation
"zyklisch nachbarfremd". Für g = 3 oder 4 jeweils eine einzige,
wovon man sich leicht überzeugen kann. Für g=5 gibt es 2,
z.B. ABCDE und ACEBD . Auch für g=6 gehen maximal 2, zum
Beispiel ABCDEF und ACEBFD.
Für g=7 kommen z.B. in Frage:  ABCDEFG, ACEGBDF, ADGCFBE.
Mehr als 3 kommen aber ja sicher nicht in Frage.
Nun wäre meine Vermutung, dass die Maximalzahl

    $\ m\ =\ [mm] \lfloor\,g\,/2\ [/mm] -\ [mm] 1\,\rfloor$ [/mm]

an "zyklisch nachbarfremden Permutationen" stets auch erreichbar
ist.

Für die anfänglich vorgegebenen Anzahl g=100 (von Stühlen
im Kreis und Personen) käme man also auf  

   $\ m\ =\ [mm] \lfloor\,100\,/2\ [/mm] -\ [mm] 1\,\rfloor\ [/mm] =\ 49$

LG  ,   Al-Chwarizmi





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


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