Disjunkte Mengen

Neue Frage »

Index Auf diesen Beitrag antworten »
Disjunkte Mengen
Hallo liebes Forum,

Gegeben sei eine endliche, nichtleere Menge M,
Bezeichne K die Menge der k-elementigen Teilmengen von M.

Gesucht sind nun nichtleere, disjunkte Teilmengen mit folgenden Eigenschaften:

1.) , so daß

2.) In jeder Teilmenge befinden sich genau diejenigen Elemente aus K für die gilt:

so daß für alle -elementigen Teilmengen , diejenigen enthält , für die und gilt.
soll also aus genau denjenigen Elementen aus K bestehen, die mit einem gewissen Element aus K eine -elementige Teilmenge gemeinsam haben und nicht bereits in enthalten sind.

3.) Für jede andere Unterteilung mit gilt .

Das eine solche Unterteilung existiert ist klar, denn ich kann sie sukzessive konstruieren.
Da K endlich ist , bin ich nach endlich vielen Schritten fertig.
Da es nur endlich viele Möglichkeiten gibt, solche Unterteilungen zu konstruieren, gibt es unter all diesen auch eine, die Eigenschaft 3.) hat.
Die Frage ist nur, ob ein solches Vorgehen immer zur gleichen Anzahl von Mengen führt, oder ob etwas über die kleinstmöglich benötigte Anzahl ausgesagt werden kann.

Liebe Grüße

Der besseren Lesbarkeit wegen am 16.3.07, um 01:00 editiert.
WebFritzi Auf diesen Beitrag antworten »
RE: Disjunkte Mengen
Zitat:
Original von Index
Gegeben sei eine endliche, nichtleere Menge M.
Bezeichne K die Menge der k-elementigen Teilmengen von M.

Gesucht sind nun disjunkte Teilmengen mit folgenden Eigenschaften:

1.)

Erstens: Was ist k? Was ist n? verwirrt
Zweitens: Wovon sollen die T_i Teilmengen sein? Auch von M? Dann ist



Quatsch, denn links steht wieder eine Teilmenge von M und rechts eine Menge von Teilmengen von M. Das kann nicht gleich sein.
AD Auf diesen Beitrag antworten »

@WebFritzi

Ich denke, du hast den Beitrag von Index noch nicht ganz verstanden. Geht mir aber ähnlich, vor allem weil da ein und dieselben Symbole in verschiedenen Bedeutungen gebraucht werden, inbesondere :

Zitat:
Original von Index
Gegeben sei eine endliche, nichtleere Menge M.
Bezeichne K die Menge der k-elementigen Teilmengen von M.

Hier ist eine natürliche Zahl.

Zitat:
Original von Index
diejenigen enthält , für die und gilt.

Hier ist plötzlich eine Teilmenge von , einen Halbsatz vorher war mit (k-1) noch die natürliche Zahl gemeint...

Sowas fördert nicht gerade das Verständnis, am besten du formulierst nochmal neu, Index. Abgesehen von solchen Doppelbedeutungen ist man ja eigentlich frei in der Symbolwahl, trotzdem hilft die Einhaltung gewisser Konventionen beim Verständnis. So könntest du z.B. sowas einhalten:

Kleinbuchstaben wie = natürliche Zahlen

Großbuchstaben wie = Teilmengen von

Kalligraphische Namen wie = Mengen von Teilmengen von

Muss nicht diese Konvention sein, aber irgendwas in der Art...


EDIT: Ach ja, nochwas: Hängen die beiden Zahlen und irgendwie zusammen? Müssen eigentlich, den für beliebige n ist die Aussage sicher falsch, dass eine solche Zerlegung existiert.
Leopold Auf diesen Beitrag antworten »

Jaja! Big Laugh Je älter Big Laugh die Leute werden, desto dogmatischer Big Laugh werden sie ...

Und wenn man dann ganz alt wird, dann kann man sogar noch Papst werden. Da ist man dann so Dogmatiker, daß einem niemand mehr widersprechen darf. Wenn man es nicht ganz so weit bringt, so kann es immerhin noch für den SPD-Vorsitz reichen, bekanntlich das zweitschönste Amt nach dem Papst. Wenn man es in heutiger Zeit auch nicht lange genießen kann ...
AD Auf diesen Beitrag antworten »

Hab ich mir fastgedacht, dass sowas kommt. Daher ja auch mein Hinweis:
Zitat:
Original von Arthur Dent
Abgesehen von solchen Doppelbedeutungen ist man ja eigentlich frei in der Symbolwahl, trotzdem hilft die Einhaltung gewisser Konventionen beim Verständnis.
Index Auf diesen Beitrag antworten »
Disjunkte Mengen
So, jetzt ist´s aber gut zu lesen,
ich habe den Beitrag eben editiert.

@Arthur Dent Hast Recht, so etwas kann natürlich nicht existieren. Die Existenz eines solchen n reicht schon.
 
 
AD Auf diesen Beitrag antworten »

Wenn ich richtig durchzähle, dann ist



denn jedes Element unterscheidet sich ja um höchstens ein Element von : Der Fall liefert den ersten Summanden 1. Im Fall gibt es genau einen Unterschied, auf Seite von ist das eines der Elemente dieser Menge. Das fehlende, andere Element in stammt natürlich aus der Elemente umfassenden Restmenge .

Da die eine disjunkte Zerlegnung von bilden sollen, muss notwendig die Bedingung



gelten. Da ist zunächst schon mal festzustellen, dass es für beliebige nicht immer gibt, die überhaupt erstmal die notwendige Bedingung (*) erfüllen, Beispiel:

, kein n erfüllt diese Gleichung.


Insofern interessiert mich schon mal, wie du das anstellen willst:

Zitat:
Original von Index
Dass eine solche Unterteilung existiert ist klar, denn ich kann sie sukzessive konstruieren.
Index Auf diesen Beitrag antworten »

Zitat:
Wenn ich richtig durchzähle, dann ist

@Arthur
Müssen alle Teilmengen gleichmächtig sein ?

Zitat:
Da ist zunächst schon mal festzustellen, dass es für beliebige nicht immer gibt, die überhaupt erstmal die notwendige Bedingung (*) erfüllen


Wenn nicht, kann man nicht mehr mit (*) argumentieren.


Zitat:
Insofern interessiert mich schon mal, wie du das anstellen willst:


Ich beginne mit einem beliebigen Element aus und bilde , indem ich zu alle Elemente aus mit Eigenschaft 2) hinzunehme. In befindet sich nun kein Element mehr, welches mit eine -elementige Teilmenge gemein hat. Ist nicht leer , wähle ich usw.
Ich bin fertig, wenn leer ist.
Per Konstruktion sind alle paarweise disjunkt.
Da K endlich ist , gibt es auch nur endlich viele Möglichkeiten verschiedene Zerlegungen von zu konstruieren, also auch eine mit einer kleinstmöglichen Anzahl von Teilmengen, so daß Eigenschaft 3) erfüllt ist.
Für gilt dann auch :
AD Auf diesen Beitrag antworten »

Zitat:
Original von Index
Müssen alle Teilmengen gleichmächtig sein ?

Allerdings, und zwar gemäß deiner obigen Formulierung:

Zitat:
Original von Index
2.) In jeder Teilmenge befinden sich genau diejenigen Elemente aus K für die gilt:

so daß für alle -elementigen Teilmengen , diejenigen enthält , für die und gilt.
soll also aus genau denjenigen Elementen aus K bestehen, die mit einem gewissen Element aus K eine -elementige Teilmenge gemeinsam haben und nicht bereits in enthalten sind.

Wenn du das nicht so meinst, dass also ein paar Teilmengen von M, die das auch erfüllen "weggelassen" werden können (deine beschriebene Prozedur verrät, dass du sowas wahrscheinlich zulässt), dann musst du das umformulieren! Insbesondere müssen diese "genau" dann weg!!!


EDIT: Oder aber du ersetzt

Zitat:
Original von Index
soll also aus genau denjenigen Elementen aus K bestehen, die mit einem gewissen Element aus K eine -elementige Teilmenge gemeinsam haben

durch

Zitat:
Original von Index
soll also aus genau denjenigen Elementen aus bestehen, die mit einem gewissen Element aus eine -elementige Teilmenge gemeinsam haben

Das wäre dann nämlich was anderes als das, was du oben geschrieben hast, und würde zu deinem rekursiven Vorgehen passen.

Dann ist der Nachweis, dass so ein existiert, allerdings trivial und schon durch die Prozedur gegeben.


Verschoben - gehört ja doch ziemlich eindeutig zu Kombinatorik.
Index Auf diesen Beitrag antworten »

@Arthur
Deine Begründung, warum das "genau" weggelassen werden muß, verstehe ich nicht.

Zunächst mal ging es doch nur darum, nachzuweisen ob eine Zerlegung von in disjunkte Teilmengen mit den genannten Eigenschaften überhaupt existiert.
Da ich eine Zerlegung konstruiert habe , die meinen Bedingungen 1.) ,2.), 3.) entspricht,inbesondere jede Teilmenge Bedingung 2) erfüllt, kann meine Formulierung mit "genau" doch gar nicht so falsch sein, denn jedes enthält doch genau die die eine (k-1) elementige Teilmenge von enthalten in keiner anderen Teilmenge enthalten sind.

In diesem Sinne ist das Ganze jedenfalls von mir gemeint, und die Existenz einer Zerlegung von war ja auch nicht die eigentliche Frage.


Die Frage ist, ob ein solches Vorgehen immer zur gleichen Anzahl von Teilmengen führt, oder ob etwas über die kleinstmöglich benötigte Anzahl ausgesagt werden kann.
AD Auf diesen Beitrag antworten »

Deine Konstruktion ist rekursiv angelegt, deine Beschreibung oben aber nicht! Da sprichst du nur von den "anderen" , richtigerweise hättest du von den "bisherigen" , also die für sprechen müssen.

Daher ja meine Empfehlung (im EDIT meines letzten Beitrages) für eine Umformulierung, die du leider ignoriert hast.
Index Auf diesen Beitrag antworten »

Hallo ,

aber meine Beschreibung der Zerlegung von wird dadurch doch nicht falsch, sie passt auch für meine rekursive Konstruktion,oder kann jemand einen Widerspruch zur Eigenschaft 2.) feststellen ?
AD Auf diesen Beitrag antworten »
RE: Disjunkte Mengen
Ich formuliere mal 2.) um, so wie du es vermutlich meinst. Ist außerdem kürzer als deine Variante

Zitat:
2.) Zu jeder Teilmenge gibt es ein mit folgender Eigenschaft:

Für alle gilt .

Dass die disjunkt voneinander sind, hattest du vorher schon gesagt, muss man nicht wiederholen.

Symbolisch formuliert kann man dann Eigenschaft 2.) durch



ausdrücken. Es ist eine Eigenschaft, keine Definition - dazu fehlt die Eindeutigkeit.


Das 2.) in deinem ersten Beitrag verstehe ich nun aber wegen des "genau" ganz klar als

,

und das klappt eben i.a. nicht, wie für m=4,k=2 deutlich gezeigt. Kannst einem Mathematiker schon mal vertrauen, deine Formulierung oben ist ganz einfach missverständlich.
Index Auf diesen Beitrag antworten »
RE: Disjunkte Mengen
Hallo,


selbst wenn Du die zusammen mit der Disjunktheitforderung so wie in Deinem letzten Beitrag beschreibst, kann ich immer noch nicht erkennen, warum meine Beschreibung der Eigenschaften nicht richtig sein soll.
Es wäre daher nett, mir doch aufzuzeigen , wo die Konstruktion der Zerlegung meiner Beschreibung widerspricht .

Es ging mirauch nicht darum, mit den geforderten Eigenschaften ein Verfahren für eine Rekursion zu beschreiben ,welches i.A. immer funktioniert, sondern ,sobald man sichergestellt hat, daß eine Zerlegung mit diesen Eigenschaften existiert,
danach fragt, ob es verschiedene Zerlegungen von \K gibt die alle die gleiche Anzahl an Teilmengen benötigt oder nicht.
AD Auf diesen Beitrag antworten »

Du kannst meine Hinweise annehmen oder es bleiben lassen. Ich habe meine Hinweise mehrfach klar dargelegt, und habe jetzt wirklich keine Lust mit dir zu streiten.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »