Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Bijektion zwischen zwei Binomialkoeffizienten

Bijektion zwischen zwei Binomialkoeffizienten

Universität / Fachhochschule

Binomialkoeffizienten

Tags: Binomialkoeffizient

Clemensum aktiv_icon

10:31 Uhr, 27.09.2012

Finden Sie eine Bijektion zwischen

(\binom{[45]}{6})

und

(\binom{[40]}{6})

und zeigen Sie damit, dass die Anzahl der Mengen in

(\binom{[45]}{6})

wo keine zwei Zahlen in ihrer natürlichen Reihenfolge aufeinanderfolgen gleich

(\binom{40}{6})

ist.

Ich sehe hier leider keine Bijektion und müsste mir die Zusammenhänge durch mühsames Probieren verschiedener Fälle suchen. Kann mir da jemand ein paar Tipps geben, wäre sicher sehr hilfreich! :-)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

Bummerang

10:43 Uhr, 27.09.2012

Hallo,

Danke dass ich Dir hier schon des öfteren helfen durfte, so wie in diesen beiden Fällen in den letzten Tagen:

www.onlinemathe.de/forum/Anzahl-der-Monome-mit-deg-15

www.onlinemathe.de/forum/Rechteck-mit-Kachelungen

Als Dank dafür hast Du immerhin meinem Profil einen Besuch abgestattet!

Welchen Grund sollte man haben, jemandem erneut zu helfen, dem es so offensichtlich an den minimalen Höflichkeitsformen mangelt...

Clemensum aktiv_icon

11:31 Uhr, 27.09.2012

Hallo Bummerang!

Ich möchte mich bei dir dafür entschuldigen! Leider ist es nicht möglich dich als Entschuldigung (eigentlich sollte ich das schon aufgrund deiner längeren Erklärungen) auf ein Essen oder gute Getränke einzuladen, aber du solltest sehen, dass ich nicht wirklich undankbar bin!

Ich verstehe, wenn du mir nun hier nicht helfen willst! Manchmal hilft eine gewisse Strafe (nächstes Mal stelle ich dann also nur noch Fragen, wenn ich sicher bin, dass ich dem Antworter gleich respondieren kann und ein Minimum an dankbaren Worten unmittelbar ausdenke)

Herzliche Grüße,
Clemensum

Bummerang

11:06 Uhr, 28.09.2012

Hallo,

vielleicht solltest Du besser Dichter werden, Deine Fähigkeiten auf diesem Gebiet scheinen mir größer als Deine mathematischen Fähigkeiten, ohne diese in irgendeiner Weise klein reden zu wollen. Auch erkenne ich die darin liegende Satire. Auch ist es sicher nicht ernst gemeint, wenn Du schreibst, dass Du nicht einmal die Zeit hast, auf "Antworten" zu drücken. Sollte dem doch so sein, wärst Du ein typischer Kandidat für einen Laptop und eine elektrische Zahnbürste. Während Du Dir die Zähne putzt, hast Du dann immer eine Hand frei, den "normalen Routinekram" zu erledigen und das sogar zwei Mal am Tag. Und gutes Benehmen zeigt sich nicht durch viele blumige Worte sondern eher durch die Stetigkeit, mit der man die guten Umgangsformen anwendet. Trotzdem sollst Du nicht dumm sterben müssen:

Es steht nicht da, wofür die Ausdrücke mit den eckigen Klammern stehen sollen, es erschließt sich aber aus dem Kontext für mich eine Möglichkeit, bei der die Lösung sehr einfach ist. Wenn

(\begin{matrix} [n] \\ k \end{matrix})

für die Menge aller möglichen Kombinationen stehen soll und nicht wie der Binomialkoeffizient, der nur die Anzahl darstellt, einfach eine Zahl ist, dann ist die einfachste Bijektion die, bei der einem Element aus

(\begin{matrix} [40] \\ 6 \end{matrix}),

das als 6-Tupel in der Form

(n_{1}, n_{2}, n_{3}, n_{4}, n_{5}, n_{6})

mit

1 \leq n_{1} < n_{2} < n_{3} < n_{4} < n_{5} < n_{6} \leq 40

dargestellt werden kann, auf genau das Element aus

(\begin{matrix} [45] \\ 6 \end{matrix})

abbildet, welches durch

(n_{1}, n_{2} + 1, n_{3} + 2, n_{4} + 3, n_{5} + 4, n_{6} + 5)

dargestellt werden kann. Offensichtlich sind in diesen Kombinationen aus

(\begin{matrix} [45] \\ 6 \end{matrix})

keine Kombinationen dabei, in denen zwei aufeinanderfolgende Zahlen enthalten sind. Und andersherum kann man auch jede Kombination aus

(\begin{matrix} [45] \\ 6 \end{matrix}),

in der es keine aufeinanderfolgende Zahlen gibt, eindeutig auf eine Kombination aus

(\begin{matrix} [40] \\ 6 \end{matrix})

abbilden, indem man bei den Zahlen einfach

1, 2, . .

, 5

abzieht. Durch die geschickte Wahl der Obergrenzen

40

und

45

und dazu passend die

6,

ist diese Bijektion dafür brauchbar um den geforderten Beweis anzutreten.

Clemensum aktiv_icon

12:46 Uhr, 29.09.2012

Hallo Bummerang!

Dankeschön für deinen trotzdem ausgeführten verständlichen Beweis!

Ich hoffe, wir sind wieder gut, was mein Missverhalten anbelangt! :-)

Mit lieben Grüßen,
Clemensum

Clemensum aktiv_icon

23:31 Uhr, 01.10.2012

So, nun zu einem kreativeren Ansatz (ohne Bijektion), den ich mir ausgedacht habe:
Ich frage zuerst wie viele Elemente aus

(\binom{[45]}{6})

mindestens zwei unmittelbar aufeinander folgende Zahlen besitzen und ziehe dieses Ergebnis dann von ALLEN Kombinationen ab.
Sei dazu

T_{i, i + 1} = {(a_{1}, \dots, a_{6}) : a_{i + 1} = a_{i} + 1}

für diese

i .

Jetzt habe ich jedoch zu bedenken; wenn zwei aufeinanderfolgen, können es auch mehr tun, also muss ich Schnitte geeignet abziehen und hinzufügen (die Idee war also eine geschickte Voraussetzungabänderung für eine Möglichkeit der Anwendung der Siebformel)

∣ T_{1, 2} \cup T_{3, 4} \cup T_{5, 6} ∣ = ∣ T_{1, 2} ∣ + ∣ T_{3, 4} ∣ + ∣ T_{5, 6} ∣ - (∣ T_{1, 2} \cap T_{3, 4} ∣ + \dots + ∣ T_{3, 4} \cup T_{5, 6} ∣) + ∣ T_{1, 2} \cap T_{3, 4} \cap T_{5, 6} ∣

So, was ist nun etwa

∣ T_{1, 2} ∣

Ich habe es mir so überlegt:
Ich betrachte einfach die Paare

(1, 2), (2, 3), \dots (44, 45)

, welches genau 44 Paare sind. Gleichzeig sind damit aber 2 Elemente weniger in der Muttermenge. Also habe ich hier

∣ T_{1, 2} ∣ = (\binom{43}{4}) \cdot 44

. Jetzt kommt aber die Herausforderung, was ist denn etwa

∣ T_{1, 2} \cap T_{3, 4} ∣

? Nun, offenbar habe ich hier

∣ {(a_{1}, \dots, a_{6}) : a_{2} = a_{1} + 1 \land a_{4} = a_{3} + 1} ∣

zu betrachten. Es sollte jedoch für jeder der 42 Möglichkeiten des ersten Paares 42 Möglichkeiten für das andere Paar geben, also insgesamt

4 2^{2}

Möglichkeiten. Wenn ich dies analog weiterführe und zusammenzähle, erhalte ich eine Summe, die die Anzahl aller Kombinationen deutlich übersteigt. Daraus ist zu schließen, dass ich einen Denkfehler gemacht habe. Die Frage ist nur, wo? Ich sehe ihn leider nicht! :-(

Sieht jemand meinen Fehler?

Bummerang

10:31 Uhr, 02.10.2012

Hallo,

ich verstehe Deine Notationen nicht ganz, insofern kann ich Deinen Denkfehler auch nicht finden, aber wenn ich es ohne DIESE Bijektion machen sollte, dann würde ich das mit meinem Bild mit den Kugeln und den Bleistiften machen:

Ich habe 6 Bleistifte, deren Position in einer Reihenfolge aus

45

Objekten für die 6 Zahlen aus der Kombination stehen und ich habe

39

Kugeln, deren Position in einer Reihenfolge aus

45

Objekten für die

39

Zahlen stehen, die nicht in der Kombination enthalten sind. Jetzt muß ich idese

45

Objekte nur geeignet anordnen. Dazu lege ich zunächst die

39

Kugeln nebeneinander auf einen Tisch, in einem Abstand, dass da noch ein Bleistift zwischen benachbarte Kugeln paßt. Jetzt verteile ich die Bleistifte auf die

40

Stellen vor der ersten Kugel, nach der letzten Kugel und die

38

Stellen zwischen jeweils 2 Kugeln. Dabei darf an jede der

40

Stellen nur maximal ein Bleistift liegen, es gibt also keine Wiederholungen in der Auswahl der 6 Stellen aus den

40

möglichen Positionen. Die Anzahl der Möglichkeiten ergibt sich demzufolge durch die Auswahl von 6 Stellen aus den

40

Positionen, wobei es nicht auf die Reihenfolge der Stellen ankommt. Also hat man

(\begin{matrix} 40 \\ 6 \end{matrix})

Möglichkeiten, die Stifte zu verteilen. Umgekehrt, kann man jede Kombination in eine Reihenfolge aus Bleistiften und Kugeln abbilden und wenn es keine aufeinanderfolgenden Zahlen in der Kombination gibt, dann liegt auch immer eine Kugel zwischen zwei Bleistiften. Jetzt hat man eine ANDERE Bijektion, die einem natürlich das selbe Ergebnis liefert.

Man kann dieses Problem sicher auch noch mittels einer Iteration lösen, denn alle gesuchten Möglichkeiten kann man in 2 disjunkte Fälle zerlegen:

Fall 1: In der Kombination ist die

45

enthalten
In diesem Fall gibt es genauso viele Möglichkeiten, wie es Kombinationen ohne aufeinanderfolgende Zahlen in

(\begin{matrix} [43] \\ 5 \end{matrix})

gibt.

Fall 2: In der Kombination ist die

45

nicht enthalten
In diesem Fall gibt es genauso viele Möglichkeiten, wie es Kombinationen ohne aufeinanderfolgende Zahlen in

(\begin{matrix} [44] \\ 6 \end{matrix})

gibt.

Diese Fälle kann man weiter in analoge Unterfälle gliedern ("analoge Unterfälle" bezieht sich darauf, dass immer die letzte Stelle betrachtet wird) und diese wieder in weitere, analoge Unterfälle und

. .

. und da sich die Summe der beiden Zahlen in dem modifizierten Binomialkoeffizientensymbol immer verkleinert, kommt man irgendwann zu einer Menge an Kombinationen, die man notfalls einzeln aufzählen kann bzw. die trivial sind, wie

z . B

(\begin{matrix} [11] \\ 6 \end{matrix})

enthält genau eine Möglichkeit ohne aufeinanderfolgende Zahlen oder

(\begin{matrix} [n] \\ 1 \end{matrix})

enthält genau

(n - 1)

Möglichkeiten. Das muß man dann alles Rückwärts zusammenzählen und man sollte letztendlich auch auf

(\begin{matrix} 40 \\ 6 \end{matrix})

kommen. Dürfte aber recht aufwändig sein und benötigt sicher viel Rechnen mit Fakultäten. Da ziehe ich die zwei Bijektionen (aus der Ursprungsaufgabe und die mit den Kugeln) vor...

Clemensum aktiv_icon

10:47 Uhr, 02.10.2012

Oh, wow, danke für deinen alternativen Lösungsvorschlag.^^ Ich wusste nicht, dass deine Analogie wirklich ein derartiges Anwendungspotenzial hat!

Nun zu einer Erklärung meiner Notation. Mit

T_{1, 2}

meine ich z.B. die Menge aller 6-Tupel, sodass die Zahl, welche an der 2. Stelle dieses Tupels steht um genau 1 größer ist als die Zahl die an der 1. Stelle des Tupels steht. Also ist das Tupel von der Gestalt

(a_{1}, a_{1} + 1, a_{3}, a_{4}, a_{5}, a_{6})

mit

1 \leq a_{1} < a_{3} < a_{4} < a_{5} < a_{6} \leq 45 .

Für meinen Ansatz ist es daher nun wichtig

∣ {(a_{1}, a_{1} + 1, a_{3}, \dots, a_{6}) : (1 \leq a_{1} < a_{3} < a_{4} < a_{5} < a_{6} \leq 45)} ∣

(wobei man in diesem Falle natürlich ungeordnete Tupel zu betrachten hat) zu bestimmen. Ich behaupte, diese Mächtigkeit beträgt

44 (\binom{43}{4}) .

Inklusion-Exklusion schien mir auf diese Art eine mächtige Methode zu sein, die sich darauf gewinnbringend anwenden lässt. Siehst du das genauso?

Bummerang

12:23 Uhr, 02.10.2012

Hallo,

da sind aber die Indizes bei

T

doppelt gemoppelt, der zweite Index ist immer um eins größer als der erste. Das macht die Sache unübersichtlicher! Aber was auf alle Fälle fehlt ist

T_{2,3},

und

T_{4,5}

und die entsprechenden Durchschnitte (wobei das eine Vereinigungszeichen bei Dir hoffentlich nur ein Schreibfehler ist). Aber ich denke, dass die Ermittlung Deiner Werte sehr aufwändig ist, zu aufwändig für meinen Geschmack. Natürlich kann man mittels In- und Exklusionen das Problem erschlagen, aber wenn die Komplexität für die Ermittlung der einzelnen Werte noch zunimmt, dann erschließt sich für mich nicht der Sinn, diesen Weg weiterzuverfolgen...

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1033070

1031745

	Status: nicht eingeloggt	Noch nicht registriert?