Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Binomialkoeffizient teilbarkeit

Binomialkoeffizient teilbarkeit

Schüler

Tags: Binomialkoeffizient, Teilbarkeit

sirius22 aktiv_icon

20:00 Uhr, 19.11.2013

Guten Abend zusammen,

Ich habe eine Definition die folgendermassen lautet:

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) * \frac{n}{k}

Ich soll beweisen, wieso die rechte Seite auch wirklich durch k teilbar ist, also nicht wieso diese Definition stimmt.

Liebe Grüsse

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

prodomo aktiv_icon

09:03 Uhr, 20.11.2013

Benutze

(\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! \cdot (n - k)!}

. Spalte

\frac{n}{k}

als Faktor ab und berücksichtige

(n - k) = [(n - 1) - (k - 1)]

. Wende dann die obige Beziehung auf

(n - 1)

und

(k - 1)

an !

sirius22 aktiv_icon

11:53 Uhr, 20.11.2013

Danke für die Antwort. Genau so bin ich auch vorgegangen, doch am Schluss verifiziere ich somit nur, dass das Gleichheitszeichen auch wirklich stimmt. Ich will jedoch beweisen, wieso die rechte Seite durch dieses k teilbar ist und nicht ob diese Definition stimmt.

Liebe Grüsse

pwmeyer aktiv_icon

12:11 Uhr, 20.11.2013

Hallo,

die rechte Seite ist nicht durch

k

teilbar: Für

n = 7

und

k = 2

ist

(\begin{matrix} 7 \\ 2 \end{matrix}) = \frac{7 \cdot 6}{1 \cdot 2} = 21

und das ist nicht durch

k = 2

teilbar.

Was meinst Du also genau?

Gruß pwm

sirius22 aktiv_icon

12:44 Uhr, 20.11.2013

mit n=7 und k = 2 ist die rechte Seite;

(\binom{7 - 1}{2 - 1})

= 6

6*7 = 42

42 / 2 = 6

Das heisst dieser Term mit

(\binom{n - 1}{k - 1})

* n ist durch k teilbar.

Aber wieso ist er durch k teilbar? Das will ich beweisen (oder widerlegen).

Liebe Grüsse

prodomo aktiv_icon

13:31 Uhr, 20.11.2013

Wenn die "rechte Seite" durch

k

teilbar sein soll, dann heißt das also

k | (\begin{matrix} n - 1 \\ k - 1 \end{matrix}) \cdot \frac{n}{k}

?
Dann ist das Beispiel von pwmeyer als Gegenbeweis geeignet. Mit

n = 7

und

k = 3

folgt

(\begin{matrix} 6 \\ 2 \end{matrix}) \cdot \frac{7}{3} = 35

. Das ist nicht durch 3 teilbar. Mir scheint, dir ist nicht klar, was du wirklich beweisen sollst.

pwmeyer aktiv_icon

13:36 Uhr, 20.11.2013

Hallo,

in der Tat: Was willst Du eigentlich beweisen? Es ist bekannt, dass binomialkoeffizienten natürliche Zahlen sind - das folgt

u . a

. aus dem Pascal-Dreieick

-,

also ist klar, dass aufgrund der am Anfang angegebenen Gleichung links und rechts natürliche Zahlen stehen, also beteiligte Brüche "aufgehen".

Gruß pwm

sirius22 aktiv_icon

13:40 Uhr, 20.11.2013

Nein es ist mir schon klar, ich konnte es lediglich nicht gut erklären, tut mit Leid. Mit durch k teilbar sein, meine ich das k, welches schon auf der rechten Seite vorhanden ist. Es ist also nicht ein neues k durch welches wir teilen sollen, sondern dieses k welches schon als Nenner beim Bruch vorhanden ist.

Stimmt es, dass k ;

((\binom{n - 1}{k - 1}) * n)

ganzzahlig teilt oder stimmt das nicht immer?

Edddi aktiv_icon

14:10 Uhr, 20.11.2013

. .

. dies scheint wohl per der von dir gegebenen Definition so zu sein.

Du kannst es testen:

k | (\begin{matrix} n - 1 \\ k - 1 \end{matrix}) \cdot n

weil

(\begin{matrix} n - 1 \\ k - 1 \end{matrix}) \cdot n = \frac{(n - 1)!}{(k - 1)! \cdot (n - k)!} \cdot n = [\frac{(n - 1)!}{(k)! \cdot (n - k)!} \cdot n] \cdot k

und ist somit durch

k

teilbar!

;-)

sirius22 aktiv_icon

14:50 Uhr, 20.11.2013

Danke für eure Mühe. Ist einleutend :-)

Matlog aktiv_icon

14:56 Uhr, 20.11.2013

Hm, das ist aber alles sehr merkwürdig!

Ich habe das Problem auch so wie Edddi verstanden.
Sein Beweis ist aber erst vollständig, wenn gezeigt ist, dass

\frac{(n - 1)!}{k! \cdot (n - k)!} \cdot n

ganzzahlig ist.
Da dieser Ausdruck aber gleich

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

ist, stimmt dies, wenn man die bekannten Binomialkoeffizienten meint, wie pwm schon gesagt hat.

Vielleicht soll das aber eine komplett neue Definition sein?!
Für mich ist das in der Aufgabenstellung aber gar keine vollständige Definition!
Das ist eine rekursive Beschreibung ohne jeglichen Anfang.

sirius22 aktiv_icon

21:20 Uhr, 20.11.2013

Bei der Aufgabenstellung ging es gar nicht darum, die Teilbarkeit durch k zu beweisen. Es ist eine Informatikaufgabe, bei der es um das Programmieren von rekursiven Funktionen geht. Ist also normal, dass dir das merkwürdig vorkommt :-)

1127765

1127435

	Status: nicht eingeloggt	Noch nicht registriert?