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 "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.vorhilfe.de