Mengenbeweis/Kombinatorik

08.11.2017, 20:16

Fragewurm

Mengenbeweis/Kombinatorik

Hallo,

wie beweist man, dass folgendes gilt?

# $\begin{eqnarray*} \left\{ (a, b, c): a, b, c\in \mathbb N , 1\leq a<b<c\leq n\right\} = n \end{eqnarray*}$ über $\begin{eqnarray*} 3 \end{eqnarray*}$

# $\begin{eqnarray*} \left\{ (a, b, c): a, b, c\in \mathbb N , 1\leq a\leq b\leq c\leq n\right\} = n+2 \end{eqnarray*}$ über $\begin{eqnarray*} 3 \end{eqnarray*}$

Habe bereits versucht die Gleichheit mittels Fakultäten zu zeigen, aber offensichtlich ist das verkehrt. Wie geht man hierbei vor?

Gruß

08.11.2017, 21:49

sibelius84

Auf diesen Beitrag antworten »

Hallo Fragewurm,

hast du es schon mal induktiv bzw. rekursiv versucht? Also sagen wir mal, für die erste Menge, du würdest nun deren Mächtigkeit a_n für ein n aus |N bereits kennen, könntest du dann argumentieren, wie man daraus a_(n+1) bekommen kann?

Wenn du zeigen kannst, dass a_n die selben Start- und Rekursionsbedingungen erfüllt wie (n über 3), dann hast du die geforderte Gleichheit gezeigt.

LG
sibelius84

09.11.2017, 18:30

Fragewurm

Auf diesen Beitrag antworten »

Danke für den Hinweis, mit der Induktion habe ich für $\begin{eqnarray*} n = 3 \end{eqnarray*}$ gezeigt, dass für beides eine Möglichkeit existiert, also eine Gleichheit besteht.

Ich finde aber keinen Weg, wie ich es für n+1, also
# $\begin{eqnarray*} \left\{ (a, b, c): a, b, c\in \mathbb N , 1\leq a<b<c\leq n+1\right\} = n + 1 \end{eqnarray*}$ über $\begin{eqnarray*} 3 \end{eqnarray*}$
zeigen kann.

09.11.2017, 19:12

HAL 9000

Auf diesen Beitrag antworten »

Wenn man die kombinatorischen Grundformeln für "Kombinationen von k aus n Elementen mit/ohne Zurücklegen" kennt und benutzen darf, dann ist das hier die direkte Anwendung für k=3.

09.11.2017, 20:08

sibelius84

Auf diesen Beitrag antworten »

Zitat:

Original von Fragewurm
Danke für den Hinweis, mit der Induktion habe ich für $\begin{eqnarray*} n = 3 \end{eqnarray*}$ gezeigt, dass für beides eine Möglichkeit existiert, also eine Gleichheit besteht.

Ich finde aber keinen Weg, wie ich es für n+1, also
# $\begin{eqnarray*} \left\{ (a, b, c): a, b, c\in \mathbb N , 1\leq a<b<c\leq n+1\right\} = n + 1 \end{eqnarray*}$ über $\begin{eqnarray*} 3 \end{eqnarray*}$
zeigen kann.

Wenn du dir jetzt überlegst, wie du von n=3 auf n+1=4 kommst, dann stellst du mit den 'naiv' ermittelbaren möglichen Kombinationen (1,2,3), (1,2,4), (1,3,4), (2,3,4) fest: Du hast n+1=4 Möglichkeiten, "wo die Lücke reinkommt". In diesem Schritt scheint es also so zu sein, dass die bereits vorhandenen Möglichkeiten einfach mit n+1 multipliziert werden.

Nun sei n=4, also n+1=5. Am nächsten Schritt kann man die Hypothese testen, ob das hinkommt mit der "Multiplikation mit (n+1)".
(1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5) <- alle mit 1 vorne
(2,3,4), (2,3,5), (2,4,5) <- alle mit 2 vorne
(3,4,5) <- alle mit 3 vorne
=> 10 Stück.
Da aber 4·5=20 und nicht 10, schlägt die Hypothese also fehl. Aber es ist genau die Hälfte, soo weit weg wars also anscheinend nicht. Die Multiplikation mit (n+1)/2 kann es aber auch nicht sein, denn dann könnte man nicht sicher sein, immer etwas Ganzzahliges zu bekommen.

Nun - schummeln wir ein wenig und betrachten $\begin{eqnarray*} a_n:=\begin{pmatrix}n\\ 3\end{pmatrix},n\geq 3 \end{eqnarray*}$ . Hier ist

$\begin{eqnarray*} a_{n+1}=\frac{(n+1)!}{3!(n-2)!} = \frac{(n+1)n(n-1)}{6} \end{eqnarray*}$ .

(Man sieht übrigens sehr schön, dass das ganzzahlig ist, weil ja von den drei Zahlen n-1, n, n+1 genau eine durch 3 teilbar, und mindestens eine gerade ist.)

Entweder man erkennt daraus jetzt schon was und macht, wie HAL 9000 vorschlug, ohne Induktion / Rekursion weiter. Oder man berechnet

$\begin{eqnarray*} \frac{a_{n+1}}{a_n}= \frac{\frac{(n+1)n(n-1)}{6}}{\frac{n(n-1)(n-2)}{6}} = \frac{n+1}{n-2} = 1+\frac{3}{n-2} \end{eqnarray*}$ .

Das sieht nicht schön aus und wird wohl kaum praktisch auf unsere Menge mit den (a,b,c)'s anwendbar sein, so dass wir vielleicht lieber probieren

$\begin{eqnarray*} a_{n+1}-a_n = \frac{(n+1)n(n-1)}{6}-\frac{n(n-1)(n-2)}{6} = \frac{1}{6}n(n-1)((n+2)-(n-1)) = \frac{1}{2}n(n-1) = \begin{pmatrix}n\\ 2\end{pmatrix} \end{eqnarray*}$ .

Also im Schritt von n auf n+1 sollen immer "n über 2" Elemente dazukommen. Das heißt, dass es genau "n über 2" Elemente geben soll, die ein "n+1" als letztes Element haben.
(...oder eben 0,5n(n-1), falls dir das lieber ist.)

Wenn du in einem Dreiertupel (a,b,c) den letzten Eintrag c fixierst als n+1, welche Möglichkeiten hast du dann für (a,b)?

LG
sibelius84

PS: Das Ganze mag dir etwas umständlich erscheinen - ich habe mich aber bewusst entschieden, den Post so zu schreiben und insbesondere auch alle Irrwege miteinzubeziehen, die immer mit dazugehören und oft lehrreicher sind als der eigentliche Beweis. Man weiß am Anfang halt noch nicht, in welche Richtung man gehen soll, man tappt im Dunkeln und muss verschiedene Sachen mal probieren, bis man etwas hat, das funktioniert.

11.11.2017, 19:42

Fragewurm

Auf diesen Beitrag antworten »

Danke für die ganzen Hinweise! Es stimmt, dass es zunächst nicht sehr offensichtlich ist und man manchmal einiges probieren muss.

Bin mir aber nicht ganz sicher, wie das mit dem Tripel ist.

Wenn ich $\begin{eqnarray*} c \end{eqnarray*}$ durch $\begin{eqnarray*} n+1 \end{eqnarray*}$ ersetze wäre: $\begin{eqnarray*} \left(a, b, n+1\right) \end{eqnarray*}$

Soll es so sein oder ist es anders gemeint?

11.11.2017, 19:54

sibelius84

Auf diesen Beitrag antworten »

Nein, das ist nur eine von vielen Möglichkeiten. Es könnte auch a=1 und b=n sein. Oder a=1 und b=2. Oder...

Da ja b < c = n+1 sein muss, muss also b <= n sein. Das heißt, im Prinzip hast du nun folgendes Problem vor dir: Bestimme

$\begin{eqnarray*} \lvert \{(a,b) \,\mid\,a,b\in\mathbb{N},1\leq a <b\leq n\}\rvert \end{eqnarray*}$ .

Das ist immerhin schon mal einer weniger als vorher. Du hast deine originale Behauptung gezeigt, wenn du zeigen kannst, dass die oben angegebene Mächtigkeit gleich "n über 2" ist. Du könntest dafür analog vorgehen wie ich bei deiner originalen Behauptung. (Vielleicht nicht mit so vielen Irrwegen, sondern diesmal direkt den Ansatz weiterverfolgen, der uns einen Schritt weiter zum Ziel bringt.)

12.11.2017, 16:11

Fragewurm

Auf diesen Beitrag antworten »

Wenn ich die Schritte so wie bei der originalen Behauptung mache:

$\begin{eqnarray*} a_{n} := \begin{pmatrix} n \\ 2 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} a_{n+1} = \frac{(n+1)!}{2!(n-1)!} \end{eqnarray*}$

Aber ich bekomme dann

$\begin{eqnarray*} a_{n+1} - a_{n} = n \end{eqnarray*}$ raus.

$\begin{eqnarray*} \begin{pmatrix} n \\ 2 \end{pmatrix} \end{eqnarray*}$ erhalte ich nicht.

Neue Frage »

Antworten »

Mengenbeweis/Kombinatorik

Verwandte Themen